arXiv CS open access

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

Henry Bourne et al. · arxiv_cs

arXiv CS · Papers

deep-learning machine-learning neural-networks

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 ever

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Preprint. Under review.

F ROM P IXELS TO P RIVACY-S ENSITIVE F EATURES : A N I NFORMATION -T HEORETIC F RAMEWORK FOR R ECONSTRUCTION B OUNDS

arXiv:2610.13768v1 [stat.ML] 9 Oct 2026

Henry Bourne, Robert F. Allison Department of Mathematics The University of Bristol Beacon House, Queens Road, Bristol, BS8 1QU, United Kingdom {jd18380,marfa}@bristol.ac.uk

A BSTRACT What can an adversary recover from a model trained with DP-SGD? Its (ε, δ) 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 highdimensional 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.

I NTRODUCTION

Models trained on sensitive data can reveal individual training examples through gradients, model parameters, or query access (Zhu et al., 2019; Geiping et al., 2020; Haim et al., 2022; Carlini et al., 2021). The standard defence is differentially private stochastic gradient descent (DP-SGD), which 1. Mechanism

2. Leakage

3. Source entropy

4. Rate–distortion

Guarantee

Per-example leakage

Held-out data through Ψ T mapped through

Rate–distortion converse combines γi and h̄LB (k) and hLB (Ψ(x)) via the Shannon lower bound

Lower bound on expected reconstruction error of every attack relative to the best prior-only guess

LPIPS (perceptual similarity)

Other representations (task-specific features)

DP-SGD schedule sampling rates qt , noise multipliers σt

γi =I(xi ; θ0:T |X −i )

Representation Representation Ψ T (what to protect)

Pixels (pixel-wise error)

upper-bounded from qt , σt only

lower bound + Entropy h̄LB (k), with hLB (Ψ(x)), with finite sample confidence

Coarse or partial features (downsampling, frequency truncation, coordinates)

Figure 1: Modular information-theoretic framework. Mechanism leakage and a held-out entropy bound in a chosen representation Ψ combine through rate–distortion into a lower bound on every attack; each module can be tightened or replaced independently. 1

Preprint. Under review.

clips per-example gradients, adds Gaussian noise, and reports its guarantee through (ε, δ) (Abadi et al., 2016). These parameters provide a general privacy guarantee, but they do not directly answer the operational question considered here: How accurately could an adversary reconstruct a training example? This question is especially relevant when participation in the training set is already known but the content of an individual record remains sensitive, or when useful model accuracy requires a large privacy budget, ε. For orientation we use the tiers of Ponomareva et al. (2023): strong (ε ≤ 1), reasonable (1 < ε ≤ 10) and weak (ε > 10); the upper two are justified by common practice and empirical attacks rather than by a guarantee. Reconstruction difficulty depends partly on what can be inferred from the training-data distribution before the trained model and its trajectory are observed. Even without seeing the training mechanism, an adversary who knows the training-data distribution can mount an effective guessing attack when that distribution has low entropy. We therefore measure reconstruction error relative to the best prior-only reconstruction. The resulting reconstruction ratio equals one when training reveals nothing useful beyond the training-data distribution and decreases in value as more accurate reconstruction becomes possible.

0.8

0.9

0.6

0.8

0.4

0.7

0.2

0.6

0.0

test accuracy

Our framework separates the problem into a mechanism-side bound on the information revealed by training and a source-side bound on the uncertainty already present in the population trainingdata distribution. Rate–distortion theory combines them into a lower bound on the expected error of every reconstruction rule, biased or not; Figure 1 summarises this modular construction. For DP-SGD, the mechanism-side bound is computed before training from the sampling rates and noise multipliers, without using a reported (ε, δ) guarantee or analysing a trained model; it depends on neither the architecture nor the parameter count and can be added across training runs. The source-side entropy is lower-bounded from a finite sample with explicit confidence. The representation Ψ determines which reconstruction differences matter: the identity map gives pixel-space error, LPIPS features give perceptual error, and other representations can target coarse, partial, or task-specific recovery. An orthogonal block construction extends the calculation to high-dimensional representations while preserving squared reconstruction error exactly.

1.0

(bound)

We consider an adversary who observes the noisy parameter trajectory during training, knows every other training record, knows the population distribution from which the training records are drawn, and may use any, possibly randomised, reconstruction rule.

10 1

100

(

pixel LPIPS

101

= n 1.1)

102

0.5

test accuracy non-private

Figure 2: CelebA: 95%-confidence reconstruction bounds and accuracy. Pixel and LPIPS bounds ρ⋆ (left axis) and test accuracy (mean ± s.d. over three seeds; right axis), against ε at δ = n−1.1 train . The ratio ρ⋆ measures reconstruction error relative to the optimal prior-only guess: larger is more protective, and ρ⋆ = 1 means no improvement over that guess. Shading marks the privacy tiers of Ponomareva et al. (2023); other datasets in Figure 5.

Our contributions include: A modular information-theoretic framework. We combine mechanism leakage, source uncertainty, and an information-to-distortion converse to bound every attack under a strong informedadversary model (Theorem 3.6); each component can be tightened or replaced independently. Knowledge of training-data distribution. We assume that the adversary has complete knowledge of the population training-data distribution and can sample from it. In our bound it enters through a differential entropy that a finite sample-set can be used to bound from below with explicit confidence (Theorem 5.1). Finite-sample, representation-flexible DP-SGD bounds. The mechanism-side input is computable before training; the source-side input is controlled from finite reference data. Choosing Ψ adapts the guarantee to different reconstruction harms; with LPIPS, this gives, to our knowledge, the first reconstruction lower bound measured directly by LPIPS. A priori and retrospective analysis. The framework can select a DP-SGD noise multiplier to meet a prescribed reconstruction-error bound, or analyse the reconstruction-privacy of a published training process retrospectively from its reported schedule and a source sample. 2

Preprint. Under review.

Experiments and slack analysis. Across MNIST, CIFAR-10, CelebA and ImageNette, the bounds remain active in ‘reasonable’ and ‘weak’ (ε > 10) privacy levels. We compare attack performance with our lower bound and diagnose the gap between guaranteed and achieved reconstruction error.

R ELATED W ORK

Reconstruction robustness. Balle et al. (2022) bound the probability that an informed adversary reconstructs a target within distortion η; subsequent work sharpens the accounting and extends it to settings including multiple targets (Hayes et al., 2023; Kaissis et al., 2023; Kulynych et al., 2026; Swanberg et al., 2025; Guerra-Balboa et al., 2026). Existing instantiations specify the required prior-only success probability analytically or estimate it without finite-sample coverage. We instead estimate a source-entropy term with explicit confidence. Threshold guarantees suit secrets for which near-exact recovery is the harm, whereas our expected distortion captures harmful partial reconstruction of images. Further comparison appears in Table 1, Section A. Expected-error bounds. Estimation-theoretic work lower-bounds reconstruction error using Fisher information and related inequalities (Hannun et al., 2021; Guo et al., 2022; Chaudhuri et al., 2024; Maeng et al., 2023). The deployable Cramér–Rao and Hammersley–Chapman–Robbins bounds in this line apply to unbiased reconstructors and therefore exclude attacks exploiting the source prior. Our bound covers arbitrary reconstructors and is normalised by the optimal prior-only error; see Section A for a detailed comparison. Information-theoretic antecedents. Conditional mutual information has been used to quantify information about individual samples revealed by learning algorithms (Raginsky et al., 2016; Feldman & Steinke, 2018; Cuff & Yu, 2016), including through sequential decompositions for noisy iterative algorithms (Pensia et al., 2018). Distortion-based secrecy originates in rate–distortion theory (Schieler & Cuff, 2013). Tan et al. (2024) consider the ambient entropy-power inequality (related to Theorem 3.6) using it as motivation for minimising one of the terms it contains. This is geared toward a defence against (rather than lower bound for) reconstruction in federated learning, and neither estimates the entropy nor addresses its looseness in high dimension.

M ETHOD

Our framework has three components. We first specify the reconstruction adversary and the representation in which error is measured. We then convert an upper bound on per-record information leakage into a lower bound on reconstruction distortion. Finally, we derive a blockwise form that remains useful when the chosen representation is high-dimensional. 3.1

S ETTING AND THREAT MODEL

We first formalise what the adversary observes, what side information it possesses, and how reconstruction quality is measured. Let X = (x1 , . . . , xn ) be a training dataset of n samples in Rd , write X −i for X with the i-th row removed, and let A be a possibly stochastic training algorithm producing the full released parameter trajectory θ := θ0:T = (θ0 , . . . , θT ) from X. Our running instance is DP-SGD (Abadi et al., 2016), but the bound sees the mechanism only through the scalar γi of Theorem 3.3; DP-SGD enters solely in Section 4. Assumption 3.1 (Finite-precision data). Each training sample xi takes values in a finite subset Q ⊂ Rd , obtained by representing each of the d components at bx bits of precision. Concretely, each component takes values in a set of at most 2bx levels with spacing ∆ = 2−bx · c for some scale parameter c > 0. Assumption 3.2 (I.I.D. source). The rows of X are drawn i.i.d. from a per-sample distribution Px on Q, so the dataset has law PX = Px⊗n . These are all the reconstruction bound requires. The accountant (Section 4) and entropy estimator (Section 5) state any additional assumptions where they arise. Theorem 3.2 is violated by preprocessing computed across the training set and then applied back to it; see Section F. 3

Preprint. Under review.

Threat model. We adopt the adversary against which DP-SGD’s own guarantee is proved (Abadi et al., 2016). The adversary knows the architecture, A and its hyperparameters, every non-target training record X −i , the training set size n, and the population distribution Px from which training records are drawn. It observes the full released parameter trajectory θ0:T , including every intermediate noisy update, and may exploit all of this information through a measurable, possibly randomised reconstruction rule x̂i = g(θ0:T , X −i ). A bound against it also covers weaker adversaries, such as one observing only θT or lacking X −i . Expectations are over X ∼ Px⊗n and all randomness of training, reconstruction and dither, so the guarantee is averaged over the source, as in existing reconstruction guarantees formulated relative to a prior. Definition 3.3 (Per-sample CMI). The information (which we measure in bits) about the target revealed by the full released parameter trajectory, conditional on all non-target records, is γi := I(xi ; θ0:T | X −i ). The quantity γi measures what the trajectory carries about xi once the rest of the dataset is known. Under Theorem 3.2, the joint distribution of (xi , θ0:T , X −i ) is the same for every i. Because DPSGD treats every index alike under Poisson subsampling, γi does not depend on i; we write γ for the common value and retain the index only in per-sample statements. Lemma 3.4 (Per-sample leakage chain). Under Theorem 3.2, fix m ≥ 1 and let ûi = g(θ0:T , X −i ) ∈ Rm for a measurable, possibly randomised g whose internal randomness is independent of xi given (θ0:T , X −i ). Then I(xi ; ûi ) ≤ I(xi ; θ0:T , X −i ) = I(xi ; θ0:T | X −i ) =: γi . Proof sketch. The inequality is the data-processing inequality along xi → (θ0:T , X −i ) → ûi . The equality follows from the chain rule I(xi ; θ0:T , X −i ) = I(xi ; X −i ) + I(xi ; θ0:T | X −i ), whose first term vanishes under Theorem 3.2. Full proof in Section B.1. Hence any reconstruction carries at most γi bits of mutual information about the target. 3.2

F ROM INFORMATION LEAKAGE TO DISTORTION

We now convert the information budget γi into unavoidable reconstruction error. The private object is xi , the representation Ψ(xi ) specifies the aspect of that record whose reconstruction is to be controlled, and a dithered version of Ψ(xi ) is an analytical device that permits a differential-entropy bound for finite-precision data. The rate–distortion bound requires a continuous source entropy, whereas Theorem 3.1 makes xi discrete. We therefore add independent dither after applying Ψ. This makes differential entropy well defined, and the dither’s contribution to squared error can later be subtracted exactly. The construction is internal to the analysis: the model trains on the raw X, and neither Ψ nor the dither is applied to the training data or observed by the adversary. Definition 3.5 (Dithered representation). Call Ψ : Rd → Rm admissible if, when random, its randomness is independent of X, of A, and of the attack, with statements then holding conditionally on its draw; deterministic maps qualify. Fix a dither scale s > 0. The dithered representation of xi under Ψ is (m) (m) iid ziΨ := Ψ(xi ), z̃iΨ := ziΨ + Wi , Wi ∼ N (0, s2 Im ), (1) (m)

where the Wi are drawn independently across i and of everything above. Thus ziΨ , z̃iΨ , and ẑiΨ denote respectively the target representation, its dithered form, and the adversary’s output, all in Rm ; the ambient case Ψ = id is written x̃i and x̂i . The bound holds for every s > 0. The dither contribution is removed exactly at a cost that grows with s, while larger s reduces the bias of the entropy estimator supporting the bound; see Section E.1. For every Ψ, the dithered representation has a density and finite entropy (Section B.2). Write ΣΨ := Cov(Ψ(xi )), and abbreviate Σ := Cov(xi ). 4

Preprint. Under review.

Distortion–rate function. For an Rm -valued source Y under squared error, the distortion–rate function, DY (R), satisfies the following Shannon lower bound (SLB) (Koch, 2016): m 2(h(Y )−R)/m DY (R) := inf{E∥Y − Ŷ ∥2 : I(Y ; Ŷ ) ≤ R} ≥ 2 . (2) 2πe Equality holds at every R when Y is isotropic Gaussian (Cover & Thomas, 2006). The reconstruction ratio. Absolute error is difficult to compare across datasets and representations. We therefore normalise by the optimal reconstruction that ignores the released parameter trajectory and uses only the source distribution. For a constant guess a ∈ Rm , E∥Ψ(xi ) − a∥2 = tr ΣΨ + ∥EΨ(xi ) − a∥2 , so the optimal prior-only reconstruction is the prior mean a = EΨ(xi ), with error tr ΣΨ . We report each guarantee through the reconstruction ratio p p ms2 E∥ziΨ − ẑiΨ ∥2 2 ρΨ (g) := νΨ := , RMSEprior (Ψ) := tr ΣΨ , , (3) RMSEprior (Ψ) tr ΣΨ dropping the subscript Ψ in the ambient case. Since the prior mean is always available, inf g ρΨ (g) ≤ 1, and a valid bound never exceeds one (Theorem C.2). Choosing the representation. The map Ψ specifies which aspects of the record are treated as privacy-sensitive. Taking Ψ = id measures pixel-space reconstruction; a coordinate selection measures recovery of a region, channel, or attribute; and downsampling or frequency truncation measures coarse-scale recovery. Taking Ψ = ΨLPIPS , the concatenated unit-normalised weighted feature maps of LPIPS (Zhang et al., 2018), makes ∥ziΨ − ẑiΨ ∥2 the perceptual distortion itself. More generally, any measurable map fixed independently of the protected data and training run, including a frozen learned encoder, is admissible. The leakage bound does not change with Ψ; only the source entropy and prior-only reconstruction error in the chosen representation must be recomputed. We can now combine any valid leakage bound with the source entropy in the chosen representation. Theorem 3.6 (Reconstruction lower bound under a representation). Let Assumptions 3.1–3.2 hold, let Ψ : Rd → Rm be admissible, and let s > 0. Every possibly randomised ẑiΨ = g(θ0:T , X −i ) taking values in Rm satisfies m 2(h(z̃ Ψ )−γi )/m i 2 − ms2 , (4) E ∥ziΨ − ẑiΨ ∥2 ≥ 2πe + equivalently, on the ratio scale of equation 3, m 2 2(h(z̃iΨ )−γi )/m 2 ρΨ (g) ≥ 2 − νΨ , 2πe tr ΣΨ +

2 νΨ :=

ms2 . tr ΣΨ

(5)

The lower bound increases with uncertainty in the represented source and decreases with the information revealed by training. Proof sketch. By Theorem 3.4 and the data-processing inequality along z̃iΨ → xi → ẑiΨ , I(z̃iΨ ; ẑiΨ ) ≤ γi . The dithered representation, unlike the discrete source, has a density and finite entropy, so the SLB controls E∥z̃iΨ − ẑiΨ ∥2 at rate γi . Because the dither is centred and independent of ziΨ − ẑiΨ , its error ms2 can then be subtracted exactly. Full proof in Section B. 3.3

O RTHOGONAL BLOCK TIGHTENING

Theorem 3.6 is valid in any dimension, but can be weak and difficult to estimate for highdimensional, non-Gaussian image sources. We therefore rotate the chosen representation and partition it into low-dimensional orthogonal blocks. Squared reconstruction error is preserved exactly, while each entropy calculation is performed in only k dimensions. k×m Let U ∈ Rm×m be orthogonal, select block b ∈ √ let Nk := m/k for k | m, let Pb ∈ R {1, . . . , Nk }, and set Πb := Nk Pb U . Each block carries independent dither of scale s as in

Preprint. Under review.

Theorem 3.5, so the entropies below depend on s as well as k; we suppress s in the notation. Define the block-averaged entropy h̄U (k) :=

Nk 1 X h z̃iΠb Ψ , Nk

(k)

z̃iΠb Ψ := Πb Ψ(xi ) + Wi,b .

(6)

b=1

Block size introduces a trade-off: smaller blocks tend to carry more entropy per coordinate but each pays the full leakage γi , a factor 2−2γi /k , while larger blocks dilute this charge at the cost of lower entropy. The following corollary optimises k over a pre-specified grid. Corollary 3.7 (Orthogonal-block instantiation). Let Assumptions 3.1–3.2 hold, let Ψ : Rd → Rm be admissible with tr ΣΨ > 0, let k divide m, and let U ∈ Rm×m be orthogonal, with Πb and h̄U (k) as in equation 6. For every s > 0 and every possibly randomised ẑiΨ = g(θ0:T , X −i ) ∈ Rm , 2 writing now νΨ := ks2 / tr ΣΨ , k 2 ρΨ (g)2 ≥ 22(h̄U (k)−γi )/k − νΨ , (7) 2πe tr ΣΨ + 2 and hence, over any grid G of pairs (k, νΨ ) with k | m, 1/2 k 2(h̄U (k)−γi )/k 2 . 2 − ν ρΨ (g) ≥ ρ⋆Ψ := max Ψ 2 )∈G 2πe tr ΣΨ (k,νΨ +

(8)

The ambient case Ψ = id and m = d gives the pixel bound ρ⋆ ; taking Ψ = ΨLPIPS gives the perceptual bound ρ⋆ΨLPIPS . Proof sketch. Each Πb ◦ Ψ is admissible, so Theorem 3.6 applies blockwise to Πb ẑiΨ . The maps Πb preserve squared norm on average, so averaging the Nk block bounds returns the error in Rm . Jensen’s inequality for convex t 7→ 22t/k replaces the average of block exponentials by the exponen2 ) tial of h̄U (k), while the dither, removed exactly per block, contributes ks2 once. Each pair (k, νΨ is separately valid, hence so is the maximum over the pre-specified grid. Proof in Section C. We take U = m−1/2 Hm V ⊤ , where V is an eigenbasis of ΣΨ and Hm is a Hadamard matrix, so that every block carries the same variance tr ΣΨ and every coordinate mixes all eigendirections equally; see Theorem C.1. Halving k typically raises the entropy per coordinate but doubles the leakage charge γ/k; doubling k has the opposite effect. The grid therefore selects the scale at which the entropy gain outweighs the per-coordinate leakage penalty, and the dither cost ν 2 is optimised jointly with k.

T HE A PRIORI ACCOUNTANT

We next supply the mechanism-side input to Theorem 3.6. For Poisson-subsampled DP-SGD, the schedule (qt , σt )Tt=1 upper-bounds the per-sample leakage γ = I(xi ; θ0:T | X −i ). The calculation uses neither the trained parameters nor the realised gradients, and does not take a reported (ε, δ) guarantee as input. It is independent of the parameter dimension p in value and cost. At step t of DP-SGD (Abadi et al., 2016), a Poisson-subsampled minibatch Bt includes each index independently with probability qt . Per-sample gradients are clipped to L2 -norm C, C ḡt (xj ) := ∇θ ℓ(θt−1 ; xj ) min 1, , ∥∇θ ℓ(θt−1 ; xj )∥ and, with learning rate ηt , noise multiplier σt , and expected batch size bt = qt n, the released parameter trajectory evolves as   ηt  X ḡt (xj ) + σt C ξt  , ξt ∼ N (0, Ip ). (9) θt = θt−1 − bt j∈Bt

We write Ht−1 := θ0:t−1 . We take C = 1 throughout: rescaling the update by C leaves mutual information invariant, so the bound, which depends only on (qt , σt ), holds for any clipping norm. 6

Preprint. Under review.

Theorem 4.1 (Dominating-pair leakage bound). For DP-SGD with updates equation 9, hyperparameters (qt , σt )Tt=1 , and data-independent initialisation, γ≤ where

(1)

Pt (1)

T 1 X PRV K , ln 2 t=1 t

(1)

∥ Qt

(1)

:= N (0, σt2 ).

KtPRV := DKL Pt

:= (1 − qt ) N (0, σt2 ) + qt N (1, σt2 ),

(1)

(10)

(1)

The pair (Pt , Qt ) is the standard one-dimensional dominating pair for the Poisson-subsampled Gaussian mechanism with sampling rate qt , noise multiplier σt , and unit sensitivity (Mironov et al., (1) 2019; Zhu et al., 2022). Moreover, KtPRV is the expectation under Pt of the privacy-loss random (1) (1) variable ln(dPt /dQt ) used by the PRV accountant (Gopi et al., 2021). Proof sketch. The chain rule decomposes trajectory leakage into per-step conditional mutual informations. Conditional on the past and non-target records, each update is a Bernoulli-gated Gaussian channel whose divergence is bounded by the standard one-dimensional dominating pair. Summing these bounds and converting nats to bits gives equation 10; see Section D. Thus the reconstruction analysis consumes DP-SGD through a single scalar information budget, obtained by summing schedule-dependent per-step charges. The factor 1/ ln 2 converts the KL divergences in equation 10 from nats to the bits used in Theorem 3.6. Each KtPRV is a one-dimensional integral, evaluated to an error negligible relative to the finite-sample margins of Section 5 (Section G.4). The accountant can therefore be computed before training, or retrospectively from reported sampling rates and noise multipliers.

A CONFIDENCE BOUND ON THE REPRESENTATION ENTROPY

Section 4 supplies the mechanism-side leakage bound. We now obtain the source-side entropy bound required by Theorem 3.7 from finite reference data. Because equation 7 is increasing in the entropy it uses, a lower confidence bound on h̄U (k) gives a valid, conservative reconstruction bound. By Theorem 3.5, each z̃iΠb Ψ is a finitely supported source convolved with Gaussian dither of a chosen scale s. We use the plug-in estimator of Goldfeld et al. (2020), namely the entropy of the empirical mixture. For a sample x1:n , define n 1X ϕs y − Πb Ψ(xj ) , fˆn (y; Πb ) := n j=1

ĥn (Πb ) := h fˆn (·; Πb ) ,

ĥn :=

k 1 X ĥn (Πb ), Nk

b=1

(11) where ϕs is the k-dimensional dither density. We evaluate this entropy using the Monte Carlo integrator of Goldfeld et al. (2020) with nMC dither replicates per centre and denote the result by ĥn,MC . The estimator is minimax rate-optimal for this estimand, and its bias is downward (Goldfeld et al., 2020, Eq. (70)), which is the conservative direction required here. The finite-sample margins below are new. Throughout, n denotes the size of the sample used for entropy estimation, which need not be the training set (see Section F). The confidence statement is simultaneous over the candidate block sizes and dither scales, so the final pair may be selected after estimation without invalidating coverage. Proposition 5.1 (Confidence bound on the representation entropy). Let Assumptions 3.1–3.2 hold. Fix α ∈ (0, 1), an admissible Ψ : Rd → Rm with tr ΣΨ > 0, and the grid G of equation 8. Let U and the reference trace tr Σ̂Ψ be fixed using held-out data, independently of the estimation 1 sample x1:n , as is Ψ, and for each (k, ν 2 ) ∈ G set s = ν(tr Σ̂Ψ /k) 2 . For the closed-form margins tMC , tMD > 0 defined in Section E.3, and ĥn,MC , tMC and h̄U (k) evaluated at the dither scale s of each pair, with probability at least 1 − α over the i.i.d. estimation sample x1:n ∼ Px and Monte Carlo noise, given D⊥ , h̄LB (k) := ĥn,MC − tMC − tMD ≤ h̄U (k) 7

for all (k, ν 2 ) ∈ G.

(12)

Preprint. Under review.

CelebA, pixel

CelebA, LPIPS

1.0

0.8

0.6

0.4

0.2

0.0

10 1

100

lower bound point estimate

(bits)

101

per-block blk prior ( = 1)

0.0

102 realizable prior codebook

10 1

single step subsampled

100

(bits)

101

102

dashed: inverted to image (LPIPS)

Figure 3: CelebA: bounds, attacks and slack decomposition. Pixel (left) and LPIPS (right) reconstruction ratios at leakage γ. The bound ρ⋆ , block-specific bound ρblk , achieved codebook-release error ρcb , and attack errors against a single full-batch noisy-gradient release and a 100-step subsampled DP-SGD trajectory are shown. The large ρ⋆ -to-ρblk gap is caused by charging every block the full leakage; the close ρblk -to-ρcb match shows that little slack remains in the rate–distortion step. Details are in Section G.6. On the same event, every reconstruction admitted by the threat model in Section 3.1 satisfies k 2(h̄LB (k)−γ)/k 2 E ∥ziΨ − ẑiΨ ∥2 ≥ max 2 − ks , 2πe (k,ν 2 )∈G +

(13)

and, if in addition tr Σ̂Ψ ≥ tr ΣΨ , ρΨ (g) ≥ max 2

(k,ν )∈G

k 2πe tr Σ̂Ψ

22(h̄LB (k)−γ)/k − ν 2

1/2 .

(14)

Proof sketch. Cantelli’s inequality controls the Monte Carlo error, McDiarmid’s inequality controls the sampling error, and the downward plug-in bias requires no margin. A union bound over G permits post-estimation selection of (k, ν 2 ); see Section E. Both entropy margins are finite-sample (Section E.3). For normalisation we replace tr Σ by its heldout estimate tr Σ̂; dividing instead by its finite-sample upper confidence bound lowers ρ⋆ by at most 0.03, except on ImageNette, whose D⊥ is small (Table 3). The underlying absolute-distortion bound does not involve tr Σ and keeps its finite-sample coverage.

E XPERIMENTS

We ask two questions: what reconstruction protection does a realistic DP-SGD run guarantee at a given utility cost, and what explains the gap between this guarantee and a strong reconstruction attack? Figure 1 gives the conceptual framework; the pipeline below shows how we compute its components in both experiments. Computing the bound. Account (qt , σt )Tt=1 7→ γ

Calibrate −→ D⊥ 7→ U, ν, tr Σ̂Ψ −→

Theorem 4.1

Section F

Estimate Dest 7→ h̄LB (k) for all (k, ν 2 ) ∈ G Theorem 5.1

Optimise −→ maximise over G equation 14

Datasets and representations. We evaluate equation 14, the finite-sample instantiation of Theorem 3.7 obtained using Theorem 5.1. The main text reports representative pixel-space and LPIPS results, while the appendix extends the evaluation across MNIST, CIFAR-10, CelebA and ImageNette 8

Preprint. Under review.

(Sections G.1 and G.3). Both representations use the same schedule leakage γ; only their source entropy and prior-only error differ. Deployment results are reported against (ε, δ), with δ = n−1.1 train . Further experimental and data-handling details appear in Sections F and G. Protection and utility. For each target ε, we calibrate σ, compute the resulting leakage γ and bound ρ⋆Ψ , and train a model under the same DP-SGD schedule. We denote the pixel and LPIPS bounds by ρ⋆px and ρ⋆ΨLPIPS . Thus Figures 2 and 5 pair the reconstruction bound computable before training with the test accuracy subsequently achieved by each schedule. On CelebA, ρ⋆px remains above 0.5 up to ε = 16 (ρ⋆px = 0.513), where accuracy is 96.1 ± 0.3%, one point below the nonprivate baseline; ρ⋆ΨLPIPS is higher there (ρ⋆ΨLPIPS = 0.588). At ε = 8, ρ⋆px lies between 0.68 and 0.75 across all four datasets. The bounds remain non-trivial for ε > 10, but weaken as leakage approaches the source uncertainty certifiable from finite data. We report against ε for familiarity; equal (ε, δ) does not imply equal γ or equal reconstruction protection. Attack comparison. We use a single reconstruction attack throughout: the prior-aware attack of Hayes et al. (2023), applied to the linear model of Schwethelm et al. (2024), whose per-example gradient is the input (Section G.5). The attack uses all non-target records and released updates and estimates the source prior from a shadow sample excluding the target. At matched leakage γ, we apply the attack to a one-step full-batch release, (q, T ) = (1, 1), and a 100-step subsampled trajectory, (q, T ) = (0.02, 100). These are the one-step and multi-step series in Figures 3 and 7. Both mean errors remain above the same bound; the subsampled release is harder to exploit because target participation is hidden. Individual targets may fall below the bound because it bounds population-average expected error (Figure 6). Numerical results appear in Table 6. Where does the slack arise? Figure 3 gives a clear answer: the principal identifiable looseness comes from charging every block the full leakage, while little comes from the rate–distortion step. To show this, at leakage R = γ we compare DP-SGD with a reconstruction-optimised codebook release that indexes the nearest of 2R representative points; each bit released by this codebook is much more helpful for reconstruction than bits leaked from DP-SGD. We need two codebooks, one for rates above one bit and one for sub-bit rates (Section G.6). We evaluate the chain: ρ⋆ ≤ ρblk ≤ ρcb ≤ ρdpsgd . Here ρ⋆ is the bound, ρblk charges each block only its actual leakage, and ρcb and ρdpsgd are attack errors against the codebook and DP-SGD releases. The first gap is 0.10–0.33 in ρ, whereas the second is at most 0.03, showing that the rate–distortion step is close to tight after correcting the block charge. The remaining gap is mechanism-specific, though it may also include accountant and attack looseness. Separately, we also introduce some slack by taking a confidence bound; what we lose by not using the entropy point estimate is shown in Figure 3. See Section G.6 for details.

C ONCLUSION

We introduced a modular framework that lower-bounds population-average reconstruction error under an informed adversary. For DP-SGD it combines a schedule-level leakage bound with a finitesample source-entropy bound in an analyst-chosen representation. Across the image datasets studied, the pixel and LPIPS bounds remain non-trivial across commonly used privacy regimes, including settings with ε > 10. Limitations. The guarantee is in expectation under the source and does not preclude more accurate reconstruction of particular records or subpopulations. The bound has looseness, nearly all looseness can be attributed to the full leakage penalty being charged to every block and not accounting for the fact that some released bits are more helpful for reconstruction than others. Observing the full noisy trajectory directly covers trajectory-exposing settings but is conservative when only the final model is released. The theory also excludes cross-record preprocessing and auxiliary information beyond the stated threat model. Future work. The modular construction allows mechanism-specific leakage bounds, sourcespecific converses, other distortion measures, and representations targeting particular harms. Conditioning leakage and source uncertainty on auxiliary information could model better-informed adversaries, while joint source and leakage terms may yield group-reconstruction guarantees. Finally, using unreleased iterates or model-specific gradient structure could tighten a deployment-specific guarantee at the cost of architecture independence. 9

Preprint. Under review.

AI USE STATEMENT In this work, we only used generative AI tools (LLM-based chat and coding assistants) for the following tasks: assisting with the mathematical development, providing feedback on research methodology, as a writing aid and writing and running code. The mathematical assistance consisted of checking proofs for errors, suggesting intermediate steps in proofs, making proofs more formal, keeping notation consistent and general brainstorming. All mathematical statements were thoroughly checked multiple times and line-by-line by the authors. As a writing aid it was used to help shorten text and increase clarity. We used AI to help write much of the code. The authors checked the code by eye and employed sanity checks, plots and tests during development to make sure that the code is valid. We take responsibility for the final content of this work, including text, claims or artifacts produced with the aid of generative AI. E THICS STATEMENT This work is intended as a tool to help practitioners choose and assess privacy protections, by bounding how accurately a training record can be reconstructed from a model trained with DP-SGD. To test the bound we run reconstruction attacks, adapted from the prior-aware attack of Hayes et al. (2023), against a deliberately simple model on public benchmark datasets. R EPRODUCIBILITY STATEMENT Algorithm 1 gives the full procedure for computing the bound, and Section F specifies the data splits it uses. Section G gives all remaining experimental details: dataset preprocessing, the parameter grid and estimator settings, the architectures, hyperparameters and noise calibration for the DP-SGD runs, and the construction of the attack and the codebook mechanism. All datasets are public. Code for all experiments is available at https://github.com/h-0-0/info_ reconstruction_bound. ACKNOWLEDGMENTS We would like to thank His Majesty’s Government for contributing toward Robert F. Allison’s and Henry Bourne’s funding during the course of this work. We also thank the EPSRC Centre for Doctoral Training in Computational Statistics and Data Science (COMPASS) for funding Henry Bourne’s PhD studentship. This work was carried out using the computational facilities of the Advanced Computing Research Centre, University of Bristol - http://www.bristol.ac.uk/acrc/.

R EFERENCES Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308–318, 2016. Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP), pp. 1138–1156. IEEE, 2022. Thomas B. Berrett, Richard J. Samworth, and Ming Yuan. Efficient multivariate entropy estimation via k-nearest neighbour distances. The Annals of Statistics, 47(1):288–318, 2019. doi: 10.1214/ 18-AOS1688. Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. Protection against reconstruction and its applications in private federated learning. arXiv preprint arXiv:1812.00984, 2018. Christopher M. Bishop. Pattern recognition and machine learning. Springer, 2006. Nicholas Carlini, Florian Tramèr, Eric Wallace, Matthew Jagielski, Ariel Herbert-Voss, Katherine Lee, Adam Roberts, Tom B. Brown, Dawn Xiaodong Song, Úlfar Erlingsson, Alina Oprea, and Colin Raffel. Extracting training data from large language models. In 30th USENIX Security Symposium (USENIX Security 21), 2021. 10

Preprint. Under review.

Kamalika Chaudhuri, Chuan Guo, Laurens van der Maaten, Saeed Mahloujifar, and Mark Tygert. Guarantees of confidentiality via Hammersley–Chapman–Robbins bounds. Transactions on Machine Learning Research, 2024. Thomas M Cover and Joy A Thomas. Elements of Information Theory. Wiley, 2nd edition, 2006. Paul W. Cuff and Lanqing Yu. Differential privacy as a mutual information constraint. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016. Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle. Unlocking high-accuracy differentially private image classification through scale. arXiv preprint arXiv:2204.13650, 2022. Persi Diaconis and David Freedman. Asymptotics of graphical projection pursuit. The Annals of Statistics, 12(3):793–815, 1984. doi: 10.1214/aos/1176346703. Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference on Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 535–544. PMLR, 2018. URL https://proceedings.mlr.press/v75/feldman18a.html. Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients – how easy is it to break privacy in federated learning? Advances in Neural Information Processing Systems, 33, 2020. Ziv Goldfeld, Kristjan Greenewald, Jonathan Niles-Weed, and Yury Polyanskiy. Convergence of smoothed empirical measures with applications to entropy estimation. IEEE Transactions on Information Theory, 66(7):4368–4391, 2020. Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. Numerical composition of differential privacy. Advances in Neural Information Processing Systems, 34:11631–11642, 2021. Patricia Guerra-Balboa, Annika Sauer, Héber H Arcolezi, and Thorsten Strufe. Understanding disclosure risk in differential privacy with applications to noise calibration and auditing (extended version). arXiv preprint arXiv:2603.12142, 2026. 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, pp. 8056–8071. PMLR, 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, pp. 11998–12011. PMLR, 2023. Niv Haim, Gal Vardi, Gilad Yehudai, Ohad Shamir, and Michal Irani. Reconstructing training data from trained neural networks. Advances in Neural Information Processing Systems, 35:22911– 22924, 2022. Awni Y. Hannun, Chuan Guo, and Laurens van der Maaten. Measuring data leakage in machinelearning models with Fisher information. In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, volume 161 of Proceedings of Machine Learning Research, pp. 760–770. PMLR, 2021. Jamie Hayes, Borja Balle, and Saeed Mahloujifar. Bounding training data reconstruction in DPSGD. Advances in neural information processing systems, 36:78696–78722, 2023. Georgios Kaissis, Jamie Hayes, Alexander Ziller, and Daniel Rueckert. Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy. arXiv preprint arXiv:2307.03928, 2023. Tobias Koch. The Shannon lower bound is asymptotically tight. IEEE Transactions on Information Theory, 62(11):6155–6161, 2016. 11

Preprint. Under review.

L. F. Kozachenko and N. N. Leonenko. Sample estimate of the entropy of a random vector. Problems of Information Transmission, 23(2):95–101, 1987. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. ImageNet classification with deep convolutional neural networks. Advances in neural information processing systems, 25, 2012. Bogdan Kulynych, Juan Gomez, Georgios Kaissis, Jamie Hayes, Borja Balle, Flavio Calmon, and Jean Raisaro. Unifying re-identification, attribute inference, and data reconstruction risks in differential privacy. Advances in Neural Information Processing Systems, 38:111967–112003, 2026. Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):2278–2324, 1998. Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015. Kiwan Maeng, Chuan Guo, Sanjay Kariyappa, and G Edward Suh. Bounding the invertibility of privacy-preserving instance encoding using Fisher information. Advances in Neural Information Processing Systems, 36:51904–51925, 2023. Mikko I Malinen and Pasi Fränti. Balanced k-means for clustering. In Joint IAPR international workshops on statistical techniques in pattern recognition (SPR) and structural and syntactic pattern recognition (SSPR), pp. 32–41. Springer, 2014. Tudor Manole and Aaditya Ramdas. Martingale methods for sequential estimation of convex functionals and divergences. IEEE Transactions on Information Theory, 69(7):4641–4658, 2023. Andreas Maurer and Massimiliano Pontil. Empirical Bernstein bounds and sample variance penalization. In Proceedings of the 22nd Annual Conference on Learning Theory (COLT), 2009. Colin McDiarmid. On the method of bounded differences. Surveys in combinatorics, 141(1):148– 188, 1989. Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled Gaussian mechanism. arXiv preprint arXiv:1908.10530, 2019. Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546–550. IEEE, 2018. Yury Polyanskiy and Yihong Wu. Information theory: From coding to learning. Cambridge University Press, 2025. Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy ML: A practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113–1201, 2023. Maxim Raginsky, Alexander Rakhlin, Matthew Tsao, Yihong Wu, and Aolin Xu. Informationtheoretic analysis of stability and bias of learning algorithms. In 2016 IEEE Information Theory Workshop (ITW), pp. 26–30. IEEE, 2016. Curt Schieler and Paul W. Cuff. Rate-distortion theory for secrecy systems. In 2013 IEEE International Symposium on Information Theory, pp. 2219–2223, 2013. Kristian Schwethelm, Johannes Kaiser, Moritz Knolle, Sarah Lockfisch, Daniel Rueckert, and Alexander Ziller. Visual privacy auditing with diffusion models. arXiv preprint arXiv:2403.07588, 2024. Marika Swanberg, Meenatchi Sundaram Muthu Selva Annamalai, Jamie Hayes, Borja Balle, and Adam Smith. Beyond the worst case: Extending differential privacy guarantees to realistic adversaries. arXiv preprint arXiv:2507.08158, 2025. 12

Preprint. Under review.

Qi Tan, Qi Li, Yi Zhao, Zhuotao Liu, Xiaobing Guo, and Ke Xu. Defending against data reconstruction attacks in federated learning: An information theory approach. In 33rd USENIX security symposium (USENIX security 24), pp. 325–342, 2024. Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pp. 3–19, 2018. Hanshen Xiao and Srinivas Devadas. PAC privacy: Automatic privacy measurement and control of data processing. In Annual International Cryptology Conference, pp. 611–644. Springer, 2023. Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109.12298, 2021. Richard Zhang, Phillip Isola, Alexei A Efros, Eli Shechtman, and Oliver Wang. The unreasonable effectiveness of deep features as a perceptual metric. In 2018 IEEE/CVF conference on computer vision and pattern recognition, pp. 586–595. IEEE, 2018. Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, 2019. Yuqing Zhu, Jinshuo Dong, and Yu-Xiang Wang. Optimal accounting of differential privacy via characteristic function. In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), volume 151 of Proceedings of Machine Learning Research, pp. 4782–4817. PMLR, 2022. URL https://proceedings.mlr.press/v151/zhu22c. html.

E XTENDED RELATED WORK

Here we provide further details on related reconstruction bound work, this literature is helpfully summarized by Table 1 which organises each distinct lineage (ReRo and expected distortion) in order of publication date. The information quantities in the ReRo literature. Two threshold entries consume an information quantity, and neither is γi . Xiao & Devadas (2023) consume the dataset-level I(X; M(X)), computed after the fact by simulating the mechanism, and in their individual form a conditional mutual information given one other user’s record rather than the leave-one-out conditioning on all of X −i that the informed adversary requires. Guo et al. (2023) consume the Rényi mutual information Iα (X; Y ) bounded by the RDP parameter, together with the Shannon entropy of a supplied probability vector, spent through a generalised Fano inequality on the probability of exact recovery rather than on distortion. Expected-error bounds. Both bounds ofP Guo et al. (2022) carry an explicit bias-variance trade2 ε off, but their deployable forms, MSE ≥ i diami (Z) /(4d(e − 1)) from RDP, and MSE ≥ d/ tr Ih (z) from Fisher information, are the unbiased case, and the consequences of this assumption are visible in their own experiments. On [0, 1]784 an adversary that ignores the model and predicts the midpoint of each coordinate attains MSE ≤ 1/4, well inside the MSE = 1 line they draw as “perfect privacy”. Their per-sample Fisher bounds all exceed 1, so the accounting assures every training sample as safe. Conversely, the informed-adversary attack of Balle et al. (2022) falls below the Fisher bound on some samples, which they attribute to the attack incurring “a high bias when the sample is hard to reconstruct”. The van Trees bound of Maeng et al. (2023) is the closest in form to ours as its prior distribution is estimated from a sample, and it needs a smooth density, so they perturb the images with Gaussian noise before score matching. The differences are in the direction of the estimate and where the smoothing lives. Theirs is a point estimate, which they note “can be incorrect” and should be read “as a guideline”, and which is breached by their own attack when that perturbation is small, whereas ours is a one-sided confidence bound whose estimator is biased in the safe direction. Their perturbation is applied to the inputs themselves, where our dither is internal to the analysis and removed exactly (Theorem 3.6). 13

Preprint. Under review.

P ROOF OF THE RECONSTRUCTION LOWER BOUND

B.1

P ROOF OF T HEOREM 3.4

Proof. The first inequality is the Data Processing Inequality (DPI) on xi → (θ, X −i ) → ûi , valid since ûi depends on xi only through (θ, X −i ) and randomness independent of xi given it. For the equality, recall the chain rule for mutual information (Cover & Thomas, 2006, Theorem 2.5.2): for any random variables A, B, C we have I(A; B, C) = I(A; C) + I(A; B | C). Applying this with A = xi , B = θ, and C = X −i gives I(xi ; θ, X −i ) = I(xi ; X −i ) + I(xi ; θ | X −i ), and I(xi ; X −i ) = 0 under Theorem 3.2 leaves I(xi ; θ, X −i ) = I(xi ; θ | X −i ) =: γi . B.2

R EGULARITY OF THE DITHERED REPRESENTATION

Lemma B.1 (Regularity of the dithered representation). Let Theorem 3.1 hold, let Ψ : Rd → Rm be (m) admissible (conditioning on its draw where Ψ is random), let s > 0, and let z̃iΨ = Ψ(xi ) + Wi 2 be as in Theorem 3.5. Write ϕs for the N (0, s Im ) density. Then P (i) z̃iΨ has density fΨ (y) = v∈Q Pr(xi = v) ϕs y − Ψ(v) , a finite Gaussian mixture; (ii) Cov(z̃iΨ ) = ΣΨ + s2 Im , and E∥z̃iΨ ∥2 < ∞; 2 (iii) h(z̃iΨ ) is finite and h(z̃iΨ ) = h(W (m) ) + I Ψ(xi ); z̃iΨ ≥ h(W (m) ) = m 2 log2 (2πes ). (m)

Proof. (i). With probability Pr(xi = v) the representation is Ψ(v) + Wi ϕs (· − Ψ(v)), so z̃iΨ has the mixture density fΨ .

, whose density is

(m)

(ii). Covariances of independent summands add, and Cov(Wi ) = s2 Im . Expanding (m) (m) E∥Ψ(xi ) + Wi ∥2 , the cross term vanishes since Wi is centred and independent of Ψ(xi ), (m) 2 2 2 and E∥Wi ∥ = ms ; E∥Ψ(xi )∥ is finite as Ψ(xi ) takes finitely many values. (iii). Each ϕs (· − Ψ(v)) is at most (2πs2 )−m/2 and the weights in (i) sum to one, so fΨ ≤ 2 Ψ (2πs2 )−m/2 everywhere; hence − log2 fΨ ≥ m 2 log2 (2πs ) wherever fΨ > 0 and h(z̃i ) ≥ m 2 2 log2 (2πs ) > −∞. Gaussian maximum entropy at the covariance of (ii) (Cover & Thomas, (m) 2006, Thm. 8.6.5) gives h(z̃iΨ ) < ∞. Since Ψ(xi ) is discrete and Wi is Gaussian and indepenΨ (m) Ψ dent of it, h(z̃i ) = h(W ) + I(Ψ(xi ); z̃i ) (Goldfeld et al., 2020, eq. (53)), and the inequality follows from non-negativity of mutual information. B.3

P ROOF OF T HEOREM 3.6 Proof of theorem 3.6. If E ∥ziΨ − ẑiΨ ∥2 = ∞ the bound holds trivially, so assume throughout that it is finite. Since ziΨ = Ψ(xi ) is bounded (Q is finite by Theorem 3.1), this gives E∥ẑiΨ ∥2 < ∞, and hence E∥ziΨ − ẑiΨ ∥ < ∞ by Cauchy–Schwarz. Fix an index i ∈ {1, . . . , n} and, where Ψ is random, work conditionally on its draw. Step 1: Rate bound. For any (possibly randomised) reconstruction ẑiΨ = g(θ, X −i ), applying Theorem 3.4 at ûi = ẑiΨ gives I(xi ; ẑiΨ ) ≤ γi . (15) (m)

Step 2: Markov chain through the dithered representation. Recall z̃iΨ = Ψ(xi ) + Wi (The(m) Ψ orem 3.5). Conditionally on xi , the variable z̃i is a function of Wi alone (working, where Ψ is random, conditionally on its draw, which admissibility permits since that draw is independent of the data, of A, and of the attack), while ẑiΨ = g(θ, X −i ) is a function of (θ, X −i ) and the attack’s inter(m) nal randomness. By Theorem 3.5 the dither Wi is drawn independently of all of these jointly, so 14

Preprint. Under review.

⊥ z̃iΨ | xi , i.e. z̃iΨ → xi → ẑiΨ is a Markov chain, and the data-processing inequality (Cover ẑiΨ ⊥ & Thomas, 2006, Theorem 2.8.1) with equation 15 gives I(z̃iΨ ; ẑiΨ ) ≤ I(xi ; ẑiΨ ) ≤ γi .

(16)

Now we have bounded the mutual information between the two terms whose expected MSE we would like to bound, we can use the distortion-rate bound from equation 2, (17) E ∥z̃iΨ − ẑiΨ ∥2 ≥ Dz̃iΨ (γi ). Step 3: Shannon lower bound. By Theorem B.1, z̃iΨ is absolutely continuous on Rm with finite differential entropy and finite second moment, so the SLB applies at rate R = γi : m 2(h(z̃iΨ )−γi )/m Dz̃iΨ (γi ) ≥ 2 . (18) 2πe (m)

Step 4: Exact removal of the dither. Since z̃iΨ − ẑiΨ = (ziΨ − ẑiΨ ) + Wi , expanding the square gives (m) (m) E ∥z̃iΨ − ẑiΨ ∥2 = E ∥ziΨ − ẑiΨ ∥2 + 2 E ⟨ziΨ − ẑiΨ , Wi ⟩ + E ∥Wi ∥2 . (m)

By Theorem 3.5 the dither Wi is independent of ziΨ − ẑiΨ and has zero mean. So, expanding Pm (m) (m) coordinatewise gives E⟨ziΨ − ẑiΨ , Wi ⟩ = j=1 E[(ziΨ − ẑiΨ )j ] E[Wi,j ] = 0, the factorisation valid since E∥ziΨ − ẑiΨ ∥ < ∞ by the assumption at the start of the proof. The last term is ms2 exactly. Hence E ∥ziΨ − ẑiΨ ∥2 = E ∥z̃iΨ − ẑiΨ ∥2 − ms2 , (19) Substituting equation 17 and equation 18 into equation 19, and noting the left-hand side is nonnegative, proves equation 4. Ratio form. Assume tr ΣΨ > 0, i.e. Ψ(xi ) is not a.s. constant, so that ρΨ of equation 3 is defined. Dividing the inequality of Step 4 — before the positive part is taken — through by 2 = ms2 / tr ΣΨ from equation 3 gives RMSEprior (Ψ)2 = tr ΣΨ > 0 and using νΨ ρΨ (g)2 ≥

Ψ m 2 2 2(h(z̃i )−γi )/m − νΨ , 2πe tr ΣΨ

the left-hand side being ρΨ (g)2 by equation 3 and the reduction at the start of the proof. Since ρΨ (g)2 ≥ 0, the two combine to give the positive part in equation 5.

P ROOF OF T HEOREM 3.7

2 Proof of Theorem 3.7. Fix an orthogonal matrix U . Fix a pair (k, νΨ ) ∈ G, where k divides m, and p let s = νΨ tr ΣΨ /k be the corresponding dither scale.

Step 1: Per-block bound. Given any reconstruction ẑiΨ = g(θ, X −i ) ∈ Rm , the induced block estimate ẑiΠb Ψ := Πb ẑiΨ relies only on (θ, X −i ) and the attack’s internal randomness. The composite Πb ◦ Ψ : Rd → Rk is admissible in the sense of Theorem 3.5: Πb is deterministic, so the only randomness in Πb ◦ Ψ is that of Ψ, which admissibility of Ψ already places independent of X, of A and of the attack. Theorem 3.6 therefore applies at the representation Πb ◦ Ψ with m replaced by k, at the same leakage γi : k 2(h(z̃iΠb Ψ )−γi )/k (k) 2 − ks2 , z̃iΠb Ψ = Πb Ψ(xi ) + Wi,b . (20) 2πe These are Nk separate applications of the theorem, each block picking fresh i.i.d. dither, so no joint (k) condition across the Wi,b is required. They are combined below by summation alone. E ∥Πb (Ψ(xi ) − ẑiΨ )∥2 ≥

Preprint. Under review.

Step 2: Transfer to Rm . The Pb group the m rows of U into Nk disjoint blocks of k, so by P Pythagoras b ∥Pb u∥2 = ∥u∥2 for every u ∈ Rm . Taking u = U v and using ∥U v∥ = ∥v∥, as U is orthogonal, Nk Nk X 1 X ∥Πb v∥2 = ∥Pb U v∥2 = ∥v∥2 for every v ∈ Rm , (21) Nk b=1 b=1 √ the factor Nk in Πb = Nk Pb U being what turns the partition sum into an average. Applying equation 21 at v = Ψ(xi ) − ẑiΨ and taking expectations,

E ∥Ψ(xi ) − ẑiΨ ∥2 =

Nk 1 X E ∥Πb (Ψ(xi ) − ẑiΨ )∥2 . Nk

(22)

b=1

Step 3: Averaging the block bounds. Substituting equation 20 into equation 22 and pulling out the factors common to all blocks, N

E ∥Ψ(xi ) − ẑiΨ ∥2 ≥

k Πb Ψ k 2(h̄U (k)−γi )/k k −2γi /k 1 X 2 2h(z̃i )/k − ks2 ≥ 2 2 − ks2 , 2πe Nk 2πe

b=1

the last step by Jensen on the convex map t 7→ 22t/k applied to the uniform average over blocks, h̄U (k) by equation 6. 2 = ks2 / tr ΣΨ gives Step 4: Ratio form. Dividing by RMSEprior (Ψ)2 = tr ΣΨ and using νΨ

ρΨ (g)2 ≥

k 2 2 2(h̄U (k)−γi )/k − νΨ , 2πe tr ΣΨ

and since ρΨ (g)2 ≥ 0 as well, the two combine to give the positive part in equation 7. The pair 2 ) was arbitrary and is chosen by us, not the adversary: g is fixed first, so every pair in G (k, νΨ bounds the same ρΨ (g)2 and the largest of those bounds holds too, proving equation 8. Remark C.1 (Choosing the rotation). Every orthogonal U is valid; the choice affects only h̄U (k), hence tightness. We write Ψ = id; for general Ψ replace d, Σ by m, ΣΨ . By equation 21 the block variances vb := tr ΣΠb average to tr Σ for every U , and Gaussian maximum entropy (Cover & Thomas, 2006, Thm. 8.6.5) caps each block entropy by f (vb ) := k2 log2 2πe (vb + ks2 )/k . Since P P f is concave, Jensen’s inequality gives Nk−1 b f (vb ) ≤ f Nk−1 b vb = f (tr Σ), with equality exactly when every vb = tr Σ. We take U := d−1/2 Hd V ⊤ . By the spectral theorem for real symmetric matrices, Σ = V ΛV ⊤ with V orthogonal and Λ = diag(λ1 , . . . , λd ), so V ⊤ xi has uncorrelated coordinates with variances λ1 , . . . , λd . The Hadamard matrix Hd satisfies Hd Hd⊤ = dId with every entry ±1, so d−1/2 Hd is orthogonal and mixes the uncorrelated coordinates with equal weight 1/d, giving every output coordinate variance tr Σ/d and hence every block vb = tr Σ, for every k | d at once. The equal-weight mixing also places each coordinate in the regime where projections of a high-dimensional source are near-Gaussian (Diaconis & Freedman, 1984), which the SLB rewards; we measure rather than assume this, through the saturation value of Theorem C.2. V is computed on data held out from the estimation sample, as Theorem 5.1 requires. In our experiments V is the eigenbasis for the MNIST, CIFAR-10 and CelebA pixel bounds. For the ImageNette pixel bound (|D⊥ | = 1,000 < d) and for every LPIPS bound we take instead V ⊤ = D, a fixed random diagonal sign flip, which needs no data; the block variances then equal tr Σ only on average over the signs. Hadamard matrices exist only at orders 1, 2 and multiples of 4, and are known at every such order we use, by Sylvester’s doubling, Paley’s construction and Kronecker products of these (Section G.2). If no Hadamard matrix of order d is available we zero-pad to the nearest order at which one is: the padded coordinates are deterministically zero, so a bound for the padded representation transfers to the original, at a cost in tightness set by the padding fraction. Remark C.2 (The bound never exceeds the prior baseline). Theorem 3.7 holds for every reconstruction g, and the prior-mean guess is one with ρΨ (g) = 1 by equation 3, so ρ⋆Ψ ≤ 1 for every U , k and s: the bound never claims more protection than releasing nothing affords, and the same holds for the reported bound when it is normalised by an upper bound on tr Σ, since h̄LB (k) ≤ h̄U (k) 16

Preprint. Under review.

only lowers it. Equality at γ = 0 requires 22h̄U (k)/k = 2πe (tr Σ + ks2 )/k, which by Gaussian maximum entropy (Cover & Thomas, 2006, Thm. 8.6.5) holds only when every block is isotropic Gaussian with variance tr Σ; the saturation value below 1 in Figures 2 and 5 (0.87–0.91 in pixel space across the four datasets and 0.92–0.96 in LPIPS space across the three, at γ = 0) is what the source’s departure from that ideal costs, together with the dither and the estimation margins.

P ROOFS FOR THE A PRIORI ACCOUNTANT

The proof of Theorem 4.1 has three ingredients, presented in the order they are used: the chain rule splits γ over steps (Section D.1); each step is reduced to a Bernoulli-gated Gaussian channel (Section D.2); and the channel’s leakage is bounded by the one-dimensional reduction of Mironov et al. (2019). Section D.3 assembles them into the final result. D.1

T RAJECTORY CHAIN RULE

Lemma D.1 (Trajectory chain rule). With data-independent initialisation, the per-sample CMI decomposes exactly as T X γi = I(xi ; θt | Ht−1 , X −i ). (23) t=1

Proof. Applying the chain rule for mutual information to θ = θ0:T one iterate at a time, γi = I(xi ; θ0:T | X −i ) = I(xi ; θ0 | X −i ) +

T X

I(xi ; θt | Ht−1 , X −i ).

t=1

The first term vanishes because θ0 is drawn independently of X, hence of xi given X −i . D.2

P ER - STEP CHANNEL REDUCTION

Lemma D.2 (Per-step channel reduction). Fix a step t with ηt ̸= 0 and let Ω := (Ht−1 , X −i , Bt \ {i}) collect the past, the other records, and the other minibatch indices. Let G := ḡt (xi ) be the target’s clipped gradient and Y := 1t G + σt ξt ,

1t := 1[i ∈ Bt ] ∼ Bernoulli(qt ), ξt ∼ N (0, Ip ),

(24)

the Bernoulli-gated Gaussian channel with input G. Then I(xi ; θt | Ht−1 , X −i ) ≤ I(xi ; θt | Ω) = I(G; Y | Ω).

(25)

Proof. Equality. Given Ω, the iterate θt−1 and the other members’ gradient sum S := P j∈Bt \{i} ḡt (xj ) are determined, so the update of equation 9 reads θt = θt−1 − ηbtt Y + S , equivalently Y = − ηbtt θt − θt−1 − S, so θt is a function of (Y, Ω) and Y a function of (θt , Ω). Expanding I(xi ; Y, θt | Ω) by the chain rule (Cover & Thomas, 2006, Thm. 2.5.2) in both orders, I(xi ; θt | Ω) + I(xi ; Y | θt , Ω) = I(xi ; Y | Ω) + I(xi ; θt | Y, Ω), {z } {z } | | =0

each conditional term vanishing because the variable it measures is determined by its conditioning. Hence I(xi ; θt | Ω) = I(xi ; Y | Ω). Next, G = ḡt (xi ) is a function of (xi , Ω), the gradient being evaluated at θt−1 , so I(xi ; Y | Ω) = I(xi , G; Y | Ω) = I(G; Y | Ω) + I(xi ; Y | G, Ω), and the last term vanishes: Y = 1t G + σt ξt with (1t , ξt ) drawn independently of (xi , Ω), so given (G, Ω) it is independent of xi . 17

Preprint. Under review.

Inequality. Poisson subsampling draws the inclusion indicators independently of the data and the past, so Bt \ {i} ⊥ xi | (Ht−1 , X −i ). Expanding I(xi ; θt , Bt \ {i} | Ht−1 , X −i ) by the chain rule in both orders, I(xi ; Bt \ {i} | Ht−1 , X −i ) +I(xi ; θt | Ω) | {z } =0

= I(xi ; θt | Ht−1 , X −i ) + I(xi ; Bt \ {i} | θt , Ht−1 , X −i ), {z } | ≥0

which is the inequality in equation 25. D.3

P ROOF OF T HEOREM 4.1

Proof. By Theorems D.1 and D.2, γ =

T X

I(xi ; θt | Ht−1 , X −i ) ≤

t=1

T X

I(Gt ; Yt | Ωt ),

t=1

so it suffices to show I(Gt ; Yt | Ωt ) ≤ KtPRV at each step, with KtPRV as defined in equation 10. Fix t and drop it from the subscripts of G, Y and Ω. Per-input output distribution. Recall PY |z = (1 − qt )P0 + qt Pz from equation 10. Conditionally on G = z and Ω = ω, the only randomness remaining in Y = 1t G + σt ξt is the gate and the noise, which are independent of (xi , Ω) — Poisson subsampling draws 1t independently of the data, the past and the other indices, and ξt is fresh — so PY |G=z, Ω=ω = PY |z

for every z and ω :

with probability 1 − qt the target is excluded and Y is pure noise, P0 ; with probability qt it is included and Y is noise about the clipped gradient, Pz . The input G is a function of (xi , Ω) and so is correlated with Ω, but the channel from G to Y is not: only the input distribution varies with ω. In particular P0 is the distribution of Y when the target is not sampled. Dropping the conditioning. Since PY |G,Ω = PY |G , we have Y ⊥ Ω | G, so expanding I(G, Ω; Y ) by the chain rule in both orders, I(G; Y ) + I(Ω; Y | G) = I(G; Y | Ω) + I(Ω; Y ), {z } | {z } | ≥0

hence I(G; Y | Ω) ≤ I(G; Y ): the right-hand side is the mutual information of the channel equation 24 at input distribution PG , the marginal distribution of the target’s clipped gradient, and conditioning on Ω only removes what Y already reveals about Ω. Golden formula. For distributions PX , PY |X , QY , write DKL (PY |X ∥ QY | PX ) := Ex∼PX DKL (PY |X=x ∥ QY ) for the conditional divergence. By the golden formula (Polyanskiy & Wu, 2025, Thm. 4.1), for any QY , DKL (PY |G ∥ QY | PG ) = I(G; Y ) + DKL (PY ∥ QY ) ≥ I(G; Y ).

(26)

(27) the last step because every value G can take has norm at most one (equation 9). Worst case over clipped inputs. Write M for the Poisson-subsampled Gaussian mechanism at rate qt , noise σt and unit sensitivity. Mironov et al. (2019, Thm. 4) show that for every dataset S, every record x with ∥ḡt (x)∥ ≤ 1, and every order α ≥ 1, (1) (1) Dα M(S ∪ {x}) M(S) ≤ Dα Pt Qt , 18

Preprint. Under review.

the one-dimensional pair of equation 10.1 Take S = ∅ and x with clipped gradient z: M(∅) is pure noise, P0 , and M({x}) includes the record with probability qt , giving PY |z . The other records of the actual training set do not appear because Theorem D.2 has already conditioned them away through Ω. At α = 1 the right-hand side is KtPRV , so the supremum in equation 27 is at most KtPRV , hence I(G; Y | Ω) ≤ I(G; Y ) ≤ KtPRV , (28) with both sides in nats; dividing by ln 2 to convert to bits and summing over t completes the proof.

D ETAILS ON THE REPRESENTATION ENTROPY CONFIDENCE BOUND

Section E.1 sets out what the bound needs from an entropy estimator and why the plug-in is the only candidate that supplies it; Sections E.2 and E.3 then verify each requirement in turn, and Section E.4 chains them into Theorem 5.1. E.1

W HAT THE BOUND NEEDS FROM THE ENTROPY ESTIMATOR

Theorem 3.7 consumes h̄U (k) through the exponent 2 2(h̄U (k)−γ)/k , maximised over a pair (k, ν 2 ) chosen from G after the data is seen. We supply it through a lower confidence bound h̄LB (k) ≤ h̄U (k), and the bound pays for the shortfall h̄U (k) − h̄LB (k) exactly as it pays for leakage, since a shortfall of t bits costs the bounded ratio a factor 2−2t/k . The shortfall has two parts, whatever the point estimate is biased by and whatever is subtracted from it to make the bound hold at the stated confidence. What the bound needs is that both be controlled in a single one-sided, finite-sample statement, namely that h̄LB (k) ≤ h̄U (k) for every (k, ν 2 ) ∈ G with probability at least 1 − α. Only the lower side is used, and the union bound over G in Theorem 5.1 needs a per-pair tail probability at the n we have rather than in the limit. Most entropy estimators do not supply this. Nearest-neighbour estimators (Kozachenko & Leonenko, 1987; Berrett et al., 2019) have a bias depending on the unknown density, so no finite-sample statement is available in either direction, and variational estimators of the mutual information into which h(z̃ Πb ) decomposes (Theorem B.1(iii)) are lower bounds in expectation only. The finitesample error bounds that do exist for the smoothed setting, the risk bound of Goldfeld et al. (2020, Thm. 2) and the confidence sequence of Manole & Ramdas (2023, Cor. 21), are two-sided, and a two-sided bound must control the estimator’s bias, which costs a prefactor exponential in the dimension and makes the bound vacuous at our sample sizes. We need only a lower bound, and the plug-in’s bias is downward, so it needs no control at all; what remains is the fluctuation, which Theorem E.6 bounds at a constant that does not grow with the dimension. The plug-in of Goldfeld et al. (2020) meets the requirement. Its error about h̄U (k) splits into a bias and a fluctuation. The bias is downward at every n (Goldfeld et al., 2020, eq. (70)), so it needs no margin, and this is what places the plug-in outside the two-sided barrier above, since it is onesided by construction. The fluctuation is a function of the n independent samples, the rotation and dither scale having been fixed on disjoint data (Section F), and changing one sample moves it by at most Hb (1/n) regardless of k (Theorem E.3), so McDiarmid gives a finite-sample margin of Õ(n−1/2 ) bits carrying no k (Theorem E.6). The Monte Carlo integrator we evaluate it with has known conditional mean and variance given the sample (Theorem E.4), so its error is given a margin the same way (Theorem E.5). It is capped, however: ĥn ≤ h(W (k) ) + log2 n by Theorem E.1. E.2

B OUNDED DIFFERENCES FOR THE PLUG - IN

Goldfeld et al. (2020) do not provide a lower confidence bound, they bound E[ĥn ] and have no reason to control its fluctuation about that mean. Here we derive the constant needed for McDiarmid’s 1 Theorem 4 of Mironov et al. (2019) bounds the Rényi divergence in both directions, Dα (M(S) ∥ M(S ∪ {x})) and Dα (M(S ∪ {x}) ∥ M(S)); we need only the latter. The theorem is stated for Rényi order α, and the KL divergence is the case α = 1, which their Definition 1 includes by taking the limit α → 1; nothing in their proof requires α > 1.

Preprint. Under review.

inequality. It rests on a standard result about mixtures which we will re-derive here first for the reader’s benefit. Lemma E.1 (Entropy of a finite mixture). Let f1 , . . . , fr be densities on Rk with finite differential entropy, and let λ be a probability vector on {1, . . . , r}. Then r X

λi h(fi ) ≤ h

i=1

with H(λ) := −

r X

λi fi

≤

i=1

r X

λi h(fi ) + H(λ),

(29)

i=1

i λi log2 λi the Shannon entropy of the weights.

Proof. P Let A ∼ λ and, given A = i, let B ∼ fi , so that B has the mixture density and h(B | A) = i λi h(fi ). The left inequality is h(B | A) ≤ h(B), conditioning reducing entropy (Cover & Thomas, 2006, Thm. 8.6.1). For the right, h(B) = h(B | A) + I(B; A) and I(B; A) ≤ H(A) = H(λ). That is, knowing which component a draw came from saves at most H(λ) bits. Lemma E.2 (Bounded differences under one relocation). Fix s > 0 and Π : Rd → Rk . Let x1:n and x′1:n be two samples that agree except at one index j, and let fˆn and fˆn′ be the corresponding mixtures equation 11: each is the equal-weight average of the n Gaussians ϕs (·−Πxi ), respectively ϕs (· − Πx′i ). Then h(fˆn ) − h(fˆn′ ) ≤ Hb (1/n), with Hb (p) := −p log2 p − (1 − p) log2 (1 − p) the binary entropy in bits. 1 Proof. Let g := n−1 share. Then

i̸=j ϕs (· − Πxi ) be the equal-weight mixture of the n − 1 Gaussians the two

1 fˆn = n−1 n g + n ϕs (· − Πxj ),

′ 1 fˆn′ = n−1 n g + n ϕs (· − Πxj ),

1 two-component mixtures with the same first component and the same weights λ = ( n−1 n , n ). Since ′ a Gaussian’s entropy depends only on its covariance, h(ϕs (·−Πxj )) = h(ϕs (·−Πxj )) = h(W (k) ), P so the weighted component entropies coincide for the two mixtures, i λi h(fi ) = n−1 n h(g) + 1 (k) ′ ˆ ˆ ) =: L in both cases. Theorem E.1 then places both h(fn ) and h(fn ) in [L, L + H(λ)], n h(W and H(λ) = Hb (1/n).

Corollary E.3 (Bounded differences for the block average). Fix s > 0 and a finite family Π1 , . . . , ΠNk of maps Rd → Rk , all independent of x1:n . The map x1:n 7→ ĥn of equation 11 satisfies the bounded-differences condition with constant Hb (1/n) in each coordinate: for every j and every x′j ∈ Q, ĥn (x1 , . . . , xj , . . . , xn ) − ĥn (x1 , . . . , x′j , . . . , xn ) ≤ Hb (1/n). The constant does not depend on k, Nk , s, or the Πb . Proof. Changing xj relocates exactly one centre of every fˆn (· ; Πb ), so by Theorem E.2 each ĥn (Πb ) moves by at most Hb (1/n), and an average of quantities each moving by at most c moves by at most c. E.3

T HE TWO MARGINS

p Fix (k, ν 2 ) ∈ G, which fixes s = ν tr Σ/k. Establishing equation 12 involves three quantities: the target h̄U (k), a fixed property of the source; the plug-in ĥn of equation 11, the exact blockaveraged entropy of the empirical mixtures, which is random through the sample x1:n and has no closed form; and ĥn,MC , the Monte Carlo approximation to ĥn that we actually compute, which is random through the sample and through the Monte Carlo noise. Writing ĥn,MC − h̄U (k) = ĥn,MC − ĥn + ĥn − E[ĥn ] + E[ĥn ] − h̄U (k) , (30) the third term is a deterministic quantity and is non-positive for every n: it is the downward bias of the plug-in (Goldfeld et al., 2020, eq. (70)), averaged over blocks. The first two are random and 20

Preprint. Under review.

each is given a margin, tMC and tMD , that it exceeds with probability at most α1 /|G| and α2 /|G| respectively, where α1 + α2 = α. The two are separated by conditioning on the sample: with x1:n fixed, ĥn is a constant and the first term is pure integration error, whose conditional mean and variance are known (Theorem E.4). Since a conditional probability bounded by α1 /|G| for every sample averages to an unconditional probability bounded by α1 /|G|, the two margins combine by a union bound (Section E.4). The rotation U and the scale s are computed from the held-out sample D⊥ and treated as fixed constants throughout; every probability below is over the estimation sample and the Monte Carlo noise only. This is what makes ĥn a function of the independent x1 , . . . , xn alone, as Theorem E.6 requires. The integrator. Write yb,i := Πb xi for the projected sample points, so fˆn (· ; Πb ) is the equalweight mixture of the Gaussians ϕs (· − yb,i ), i ∈ [n]. A draw from it is yb,J + W with J ∼ Unif[n] and W ∼ N (0, s2 Ik ) independent, so h(fˆn (· ; Πb )) = −

n 1X E log2 fˆn (yb,i + W ; Πb ) , n i=1

and we estimate each of the n expectations by nMC independent draws of W : ĥn,MC (Πb ) := −

n nMC 1 XX log2 fˆn yb,i + Wij,b ; Πb , n nMC i=1 j=1

iid

Wij,b ∼ N (0, s2 Ik ),

(31)

P with the Wij,b independent of each other and of the sample, and ĥn,MC := Nk−1 b ĥn,MC (Πb ). This is the integrator of Goldfeld et al. (2020, eqs. (36a)–(36b)), which uses natural logarithms; equation 31 is their estimator divided by ln 2. Lemma E.4 (Integrator: conditional mean and variance). Conditionally on the sample x1:n , (i) E[ĥn,MC (Πb ) | x1:n ] = h(fˆn (· ; Πb )) for every b, and hence E[ĥn,MC | x1:n ] = ĥn ; (ii) for every b, cMC (Πb ) bits2 , (32) Var[ĥn,MC (Πb ) | x1:n ] ≤ (ln 2)2 n nMC P n where, with m̂b := n1 i=1 ∥yb,i ∥2 the mean squared norm of the component means, √ √ √ 9ks2 + 8 2 + s k m̂b + 3 11s k + 1 m̂b ; (33) cMC (Πb ) := s2 N

k X 1 (iii) Var[ĥn,MC | x1:n ] ≤ cMC (Πb ) bits2 . 2 (ln 2)2 Nk n nMC

b=1

Proof. Given the sample, fˆn (· ; Πb ) is a fixed Gaussian mixture with component means yb,1 , . . . , yb,n , the setting of Goldfeld et al. (2020, Sec. III-D). Their eq. (77) is the unbiasedness of their estimator; ours is theirs divided by ln 2, so (i) holds for it too. Their Theorem 5(ii) bounds the mean squared error of their estimator about h(fˆn (· ; Πb )) by cMC (Πb )/(n nMC ) in nats2 , where their m is the mean squared norm of the component means, here m̂b . Mean squared error is variance plus squared bias, and the bias is zero by (i), so this bounds the variance; dividing by (ln 2)2 converts it to bits2 for our estimator, giving (ii). For (iii), the noise Wij,b is drawn independently for each block, so given the sample the Nk terms ĥn,MC (Πb ) are independent; the variance of their average P is Nk−2 b Var[ĥn,MC (Πb ) | x1:n ], and (ii) bounds each summand. 2 Lemma E.5 (Monte Carlo margin). Let σMC denote the right-hand side of Theorem E.4(iii). Conditionally on the sample, for every t > 0,

Pr ĥn,MC > ĥn + t x1:n ≤

2 σMC . 2 σMC + t2

Preprint. Under review.

In particular, with tMC := σMC

p |G|/α1 − 1,

(34)

the value of t at which the bound equals α1 /|G|, we have ĥn,MC ≤ ĥn + tMC with probability at least 1 − α1 /|G|. 2 Proof. Given the sample, ĥn,MC has mean ĥn and variance at most σMC by Theorem E.4. Cantelli’s 2 inequality, Pr[X − EX > t] ≤ VarX/(VarX + t ), gives the tail bound; its right-hand side is increasing in VarX, so the variance may be replaced by its upper bound. Setting it equal to α1 /|G| and solving for t gives equation 34. Writing A := {ĥn,MC > ĥn + tMC }, we have shown Pr[A | x1:n ] ≤ α1 /|G| for every realisation of the sample, and Pr[A] = E[Pr[A | x1:n ]], so Pr[A] ≤ α1 /|G| as well. Note that tMC depends on the sample through m̂b , which is why we condition.

Lemma E.6 (Sampling margin). For every t > 0, Pr ĥn > E[ĥn ] + t ≤ exp −

2t2 . n Hb (1/n)2

In particular, with q tMD := Hb (1/n) n2 ln(|G|/α2 ),

(35)

the value of t at which the bound equals α2 /|G|, we have ĥn ≤ E[ĥn ] + tMD with probability at least 1 − α2 /|G|. Proof. The xi are independent (Theorem 3.2) and changing any one of them moves ĥn by at most c := Hb (1/n) (Theorem E.3), the Πb and s being fixed independently of the sample. McDiarmid’s inequality (McDiarmid, 1989) gives Pr[ĥn − Eĥn > t] ≤ exp(−2t2 /(nc2 )); setting this equal to α2 /|G| and solving gives equation 35. E.4

P ROOF OF T HEOREM 5.1

Proof. Fix a pair (k, ν 2 ) ∈ G. By Theorems E.5 and E.6 the events {ĥn,MC > ĥn + tMC } and {ĥn > E[ĥn ] + tMD } have probability at most α1 /|G| and α2 /|G| respectively, so with probability at least 1 − (α1 + α2 )/|G| neither occurs, and then h̄LB (k) = ĥn,MC − tMC − tMD ≤ ĥn − tMD ≤ E ĥn ≤ h̄U (k). The last inequality is deterministic and holds for every n: it is the downward bias of the plug-in, E[ĥn (Πb )] ≤ h(z̃ Πb ) (Goldfeld et al., 2020, eq. (70)), applied to each block and averaged. A union bound over the grid gives h i X α1 α2 + = α, Pr ∃ (k, ν 2 ) ∈ G : h̄LB (k) > h̄U (k) ≤ |G| |G| 2 (k,ν )∈G

so equation 12 holds simultaneously for every pair with probability at least 1 − α, over the sample and the Monte Carlo noise, conditionally on D⊥ . The union bound over G is necessary: equation 8 selects the pair (k, ν 2 ) that gives the largest bound, and that selection depends on the data through h̄LB (k). A guarantee holding at any single pre-specified pair with probability 1 − α would not cover the pair chosen afterwards, whereas equation 12 holding for every pair at once does, whichever is selected. The bound equation 13 follows since the absolute form of equation 7 (Step 3 of the proof of Theorem 3.7) is nondecreasing in the entropy, so substituting h̄LB (k) can only lower it; dividing by tr Σ̂Ψ ≥ tr ΣΨ and using ks2 / tr Σ̂Ψ = ν 2 gives equation 14.

DATA HANDLING

The bound consumes four inputs. • The leakage, γ, read from the DP-SGD hyperparameters. 22

Preprint. Under review.

• The block rotation, U , and the dither scale, s, which we fix from a covariance estimate. • The entropy confidence bound, h̄LB , on the representation. The attack experiment adds the components an adversary fits. Each has its own conditions on the data it may use, Section F.1 lists those conditions. Section F.2 turns them into labelled partitions (Table 2) and Section F.3 gives the layout we recommend to a practitioner, which is also the setup we use for the privacy-spectrum experiments. Section F.4 gives the layout of the attack experiment. Figure 4 draws both and Algorithm 1 gives the order of computation. F.1

W HAT EACH QUANTITY REQUIRES

The protected records. Write Dtrain for the records DP-SGD is run on. These are the X of Section 3.1. Two conditions follow from the assumptions. Req 1. Dtrain is an i.i.d. sample from Px (Theorem 3.2), which Theorem 3.4 uses to discharge I(xi ; X −i ). Any preprocessing computed across Dtrain and applied back to it (a dataset mean, a whitening transform, deduplication, class rebalancing, a fitted encoder) couples xi to X −i and breaks the argument at its first step. Per-sample maps, per-example augmentation, and any transform whose constants are fixed on data disjoint from Dtrain preserve it. Req 2. Every trajectory computed on Dtrain that the adversary may observe composes into γ (Theorem D.1). A hyperparameter search of k runs on the protected records is therefore charged the leakage of k runs, not one; since γ reads only (qt , σt ), the search is simply one longer trajectory. Alternatively the search is run on records outside the protected set, in which case we aren’t required to account its leakage. The leakage γ. Needs no data. Theorem 4.1 requires Poisson subsampling and a data-independent initialisation, together with Req 2. The rotation U . We take U = d−1/2 Hd V ⊤ (Theorem C.1). The Hadamard factor is a fixed matrix, so the only part of U that touches data is the eigenbasis V of Σ, which we estimate. Theorem 3.7 holds for every orthogonal U , so U may be computed from any data, but Theorem E.2 requires the Πb to be fixed independently of the estimation sample, so: Req 3. the sample on which V is estimated is disjoint from the estimation sample. V buys tightness, not validity: every orthogonal U is admissible (Theorem 3.7), so where no such sample can be spared one takes V = Id , giving U = d−1/2 Hd requiring no data. We use the datafree variant U = d−1/2 Hd D, with D a fixed random diagonal sign flip, for the ImageNette pixel bound and for every LPIPS bound (Theorem C.1). The dither scale q and the reference scale. bandwidth s = ν

The estimator convolves the sample with a Gaussian of

tr Σ̂/k, so s is set by an estimate of tr Σ.

Req 4. The sample on which tr Σ is estimated is disjoint from the estimation sample. Theorem E.6 treats s as a constant and lets one record of the estimation sample move; if s were computed from that sample, moving one record would also move the bandwidth, and the boundeddifferences constant of Theorem E.2 no longer applies. The same estimate is the reference scale RMSE2prior = tr Σ of ρ. The guarantee is the absolute bound equation 4, in which tr Σ does not appear and the ratio only rescales it - so a point estimate suffices. The attack-bound comparison of Figures 3 and 7 is unaffected in any case, both sides being divided by the same number. A practitioner who wants a confidence bound on ρ⋆ , and so provably at most one, divides instead by a one-sided upper confidence bound on tr Σ (for example using empirical-Bernstein (Section G.2)). 23

Preprint. Under review.

The entropy bound h̄LB . h̄U (k) is a property of the source Px , and Theorem 5.1 lower-bounds it from any i.i.d. sample of Px on which U and s were not computed. Req 5. The estimation sample is i.i.d. from Px and disjoint from the sample of Req 3. Both margins scale as n−1/2 (Section E.3), so the sample should be as large as possible. Nothing requires the estimation sample to be disjoint from Dtrain . Under Req 1 the training set is itself an i.i.d. sample of Px , and using it estimates the entropy of exactly the source the protected records are drawn from, with the most data. Coverage is then over the random draw of the training set, not conditional on the realised one. Any other sample must be a draw from Px as well, since Theorem 5.1 bounds the entropy of whatever distribution the sample comes from. Validation and test.

Neither is an input to any estimand.

Req 6. As is ordinarily practiced, one can’t use the same data to both train a model and evaluate its performance. Req 7. Records on which accuracy is reported are disjoint from both data used to train the model and data used to evaluate the model in order to for example pick hyperparameters. Neither set is trained on, so neither carries γ and the bound makes no claim about it. The attack. The bound quantifies over reconstructions g(θ, X −i ) with internal randomness and knowledge of Px (Section 3.1); an experiment testing it must keep the attack inside that class. Req 8. Everything the attack fits or draws from — here the candidate set and the centring mean — excludes the target. An attack that has seen its target is not a function of (θ, X −i ) and can fall below the bound without the bound being wrong. X −i itself is known to the adversary, so the shadow pool may include it. Req 9. The attacked architecture, including the centring mean of its input (Section G.5), is fixed on records disjoint from the attacked set X = X −i ∪ {xi }. The bound holds for every architecture at a given (q, σ, T ), so a fixed input map is on the same footing as the linear layer itself; but one fit on the attacked records is preprocessing across X and violates Req 1. Req 10. The targets are i.i.d. from Px , so that the mean error over them estimates the expectation the bound controls, and are disjoint from the sample U is computed on (Req 3, admissibility) and from the shadow pool (Req 8). They need not be disjoint from the estimation sample. Theorem 5.1 is a statement about the population entropy h̄U (k), holding on an event of probability 1−α over the estimation sample. On that event the bound holds for the expected error of every g, whichever records the targets are. The attack’s mean error over the targets is an estimate of that expectation, and its expectation does not depend on whether the targets also appear in the estimation sample. Overlap makes the two random quantities dependent, but changes neither the probability of the coverage event nor the expected attack error, so the comparison in Figures 3 and 7 is valid either way. F.2

T HE PARTITIONS

Table 2 names a partition for each role above and records, for each, what it supplies, the requirement that constrains it, which partitions it must be disjoint from, and the property its size must have. A ⋆ marks a disjointness the guarantee or the threat model requires. The rest are kept for a clean joint statement and could be relaxed. Two partitions are shared by both experiments: D⊥ , which fixes U and s, and Dest , which supplies the entropy bound. F.3

D EPLOYMENT, AND THE PRIVACY- SPECTRUM RUNS

A practitioner makes two splits of the available data, independently of each other. For the bound, they draw a sample D⊥ of at least d records, on which they compute the covariance Σ̂, whose eigenvectors give V and whose trace gives tr Σ̂, and a disjoint estimation sample Dest , as large as possible. For training, they split the data into Dtrain , Dval and Dtest as in any training pipeline. Only 24

Preprint. Under review.

(a) Deployment, and the privacy-spectrum runs of Figure 5 available data, i.i.d. Px D⊥

Dest Dval

Dtrain

Dtest

(b) The attack experiment of Figure 3 Dest , unchanged from (a): entropy estimated on all of it

D⊥

Dshadow ⊆ Dest

Dtargets

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⊥ and Dest (top row) and the training split (bottom row) are drawn independently and may overlap; only D⊥ and Dest must be disjoint. D⊥ and Dest 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. Algorithm 1 Reconstruction lower bound for a DP-SGD deployment. Require: (qt , σt )Tt=1 for every run charged to Dtrain ; samples D⊥ and Dest (i.i.d. from Px ; Dest may be Dtrain ); grid G; confidence α P PT ▷ Theorem 4.1; Req 2 1: γ ← ln12 runs t=1 KtPRV 2: On D⊥ : fix, for each Ψ, U = m−1/2 Hm V ⊤ , the dither scales sk,ν , and tr Σ̂Ψ ▷ Req 3, Req 4 3: for Ψ ∈ {id, ΨLPIPS } and (k, ν 2 ) ∈ G do 4: On Dest : h̄LB (k) ← ĥn,MC − tMC − tMD ▷ Theorem 5.1; Req 5 5: end for 6: ρ⋆Ψ ← equation 14 7: Train by Poisson-subsampled DP-SGD on Dtrain ; to target a given ρ⋆ , invert steps 1 and 6 for σ

D⊥ and Dest must be disjoint (Req 3, Req 4). Dval is used to evaluate performance during training for purposes such as hyperparameter selection and Dtest is used to report final utility achieved. The hyperparameter search is either charged through γ (by summing Theorem 4.1 over every run), moved onto records outside the protected set, or done privately (such as on trusted private compute). The learning rate and architecture do not enter γ, so a search over them at fixed (qt , σt ) adds one trajectory’s leakage per run and nothing more. This layout is also that of the privacy-spectrum runs (Figure 5), so Figure 4(a) is both the recommendation and what we do: D⊥ and Dest are the splits of the attack experiment (Section F.4), drawn independently of the utility runs’ split into Dtrain , Dval and Dtest . As is common in the literature (Ponomareva et al., 2023), and to keep the experimental results simple to interpret, we assume hyperparameter selection leaks nothing. Where no D⊥ can be spared, U is taken data-free and tr Σ is replaced by a declared upper bound, at a cost in tightness alone.2 F.4

T HE ATTACK EXPERIMENT

The attack experiment reuses the rotation, the dither scales and the entropy bounds of (a) unchanged, so the two experiments differ only in the leakage their mechanism incurs. It uses two further sets. Dshadow ⊆ Dest is the attack’s candidate set and supplies its centring mean (Req 8, Req 9). Dtargets is 100 records from a held-out slice disjoint from Dshadow , Dest and D⊥ (Req 10). 2 Any declared value keeps the absolute bound equation 4 valid, since the dither scale it sets may be any positive number; the ratio bound stays valid provided the declared value is an upper bound on tr Σ, since dividing by a larger number can only lower it. For 8-bit pixels, tr Σ ≤ d · 2552 /4 always.

Preprint. Under review.

E XPERIMENTAL DETAILS

Sections G.1 to G.3 apply to both experiments; Section G.4 to Figures 2 and 5; Sections G.5 to G.7 to Figures 3 and 7. G.1

DATASETS Dataset MNIST CIFAR-10 CelebA ImageNette

C ×H ×W 1×28×28 3×32×32 3×64×64 3×128×128

d 784 3072 12,288 49,152

tr Σ

√ RMSEprior / d

nest

|D⊥ |

66.2 63.6 69.3 70.7

59k 49k 44k 10k

10k 10k 117k 1k

3.43×10 1.24×107 5.91×107 2.46×108

The deployment runs span d = 784 to 49,152, greyscale and color. The CelebA dataset serves as a particularly interesting dataset as recovery where one is able to ascertain the identity of the individual in the samples constitutes a natural privacy threat that one can validate with their own eyes. We deploy our bound and evaluate the utility achieved by DP-SGD across all the datasets above. For ImageNette, D⊥ supplies only tr Σ̂; no eigenbasis is estimated on it (Theorem C.1). The attack experiment uses MNIST and CelebA, a low-dimensional greyscale source and a colour face source. On CelebA, recovering a recognisable face is the natural privacy harm, so it is the case in which the perceptual bound is the one that matters. Each configuration is attacked on the same 100 held-out targets at every leakage (Section F.4). CelebA (Liu et al., 2015) uses the binary Male attribute as its label. Networks consume images rescaled to [0, 1] (CIFAR-10 utility training additionally standardises by fixed, public per-channel constants); entropy is computed on the raw 8-bit grid, so Theorem 3.1 holds with bx = 8, c = 256 and ∆ = 1. No preprocessing couples samples: every normalisation uses constants fixed independently of X, so Theorem 3.2 holds (Section F). G.2

T HE ENTROPY BOUND

The splits are those of Section F.3, with sizes in Section G.1. Reference scale. We normalise ρ by the point estimate tr Σ̂Ψ from D⊥ (Table 3). This does not affect the guarantee: the absolute bound equation 4 does not involve tr ΣΨ , and any other normaliser c simply rescales ρ⋆ by (tr Σ̂Ψ /c)1/2 . To gauge the estimation error we also give a 95% upper confidence bound from the empirical Bernstein inequality of Maurer & Pontil (2009), which requires i.i.d. variables with mean tr ΣΨ and a range fixed in advance. Pairing the records of D⊥ at random supplies these: for independent x, x′ ∼ Px , Y := 21 ∥Ψ(x) − Ψ(x′ )∥2 has mean exactly tr ΣΨ and, unlike ∥Ψ(x) − EΨ(x)∥2 , needs no estimate of the mean. Its range is [0, B/2], with B the largest possible value of ∥Ψ(x) − Ψ(x′ )∥2 . In pixel space B = 2552 d. In LPIPS space this squared P distance is the LPIPS distance, a sum over layers ℓ of the spatial average of c wℓc (ac −bc )2 , where wℓc ≥ 0 is the learned LPIPS weight on channel c of layer ℓ and a, b are the two images’ normalised 2 features at one location. These features are nonnegative Pwith norm at most one, so ∥a − b∥ ≤ 2, each layer contributes at most 2 maxc wℓc , and B = 2 √ ℓ maxc wℓc . Empirical Bernstein is much tighter here than Hoeffding, whose width scales as B/ m for m pairs: B is attained only by two opposite-extreme records, so Y varies far less than its range, and empirical Bernstein uses the sample variance of Y and pays for B only at rate B/m. The resulting bound exceeds the point estimate by at most 5.8% on MNIST, CIFAR-10 and CelebA, and by 16.6% on ImageNette, where |D⊥ | is small. Normalising by it instead would lower every reported bound by at most 0.026, or 0.064 on ImageNette, and the bound would then hold with probability at least 90% by a union bound with Theorem 5.1. Grid. We take G = K × N , with block sizes K the divisors of d up to 32 in pixel space ({1, 2, 4, 7, 8, 14, 16, 28} on MNIST, {1, 2, 3, 4, 6, 8, 12, 16, 24, 32} on the others) and K = {1, 2, 4, 8, 16, 32} in LPIPS space, and dither levels N = {0.2, 0.4, 0.8, 1.6, 3.2, 6.4}, so |G| = 48 26

Preprint. Under review.

(MNIST pixel), 60 (other pixel) and 36 (LPIPS), both fixed before any entropy is estimated, as Section E.4 requires. In pixel space K contains only divisors of d, and in LPIPS space only divisors of the padded dimension 32,768 (see Blocks below). The selected pair often lies on the boundary of the grid (Table 5): k ⋆ = max K at ε ≥ 8 in pixel space on MNIST, CIFAR-10 and ImageNette (and at ε = 16 on CelebA), and at almost every leakage in LPIPS space; ν 2⋆ reaches an end of N in a few places (CelebA pixel: 0.2 at ε ≤ 1 and ε = 32; CelebA LPIPS: 6.4 at ε ≤ 0.5; MNIST LPIPS: 6.4 at ε = 2). Blocks. We never store the rotation as a dense matrix. Instead we keep the Hadamard factor as a Kronecker product of small Hadamard matrices, so applying U costs one small matrix product per factor. In pixel space we use H784 = H28 ⊗ H28 , H3072 = H12 ⊗ H64 ⊗ H4 , H12288 = H12 ⊗ H64 ⊗ H16 and H49152 = H12 ⊗ H64 ⊗ H64 , with the power-of-two factors from Sylvester’s doubling and the others from Paley’s construction. These are Hadamard matrices of order exactly d, so no zero-padding is needed; padding adds dimensions that carry no entropy and loosens the bound. In LPIPS space we zero-pad the m = 31,872 features to 32,768 = 215 and rotate by U = 32768−1/2 H32768 D, with H32768 = H64 ⊗ H64 ⊗ H8 and D a fixed random diagonal sign flip, so no eigenbasis is estimated. The padded coordinates are deterministically zero, so by Theorem C.1 the bound transfers to the unpadded features, at a cost in tightness set by the padding fraction (2.7%), and the block variances equal tr ΣΨLPIPS only on average over the signs. Estimator and margins. The plug-in evaluates log2 fˆn at each Monte Carlo point exactly, summing over all nest centres with a numerically stable log-sum-exp. We draw nMC = 2 dither replicates per centre at k = 1 and nMC = max(k, 4) at block size k ≥ 2. We set α = 0.05, split it evenly between the two margins, and divide each by |G|, separately for each representation. Each bound therefore holds at confidence 1 − α on its own, and the pixel and LPIPS bounds hold jointly at 1 − 2α. Both margins are in bits of the block entropy h̄U (k), the entropy of one k-dimensional block averaged over the blocks, so neither grows with d. Their cost to the final bound is the gap between ρ⋆ and its point-estimate version (thin dashed in Figures 3 and 7), which drops both margins and maximises over G again: at most 0.075 in pixel space and 0.047 in LPIPS space at ε = 1 (0.083 in pixel space on ImageNette), and 0.01–0.035 at ε = 8 and 16 (up to 0.046 at ε = 32, where ρ⋆ itself is only 0.13–0.19). The selected pairs (k ⋆ , ν 2⋆ ) are listed in Table 5. G.3

T HE LPIPS REPRESENTATION

ΨLPIPS is the frozen LPIPS network (Zhang et al., 2018) with its AlexNet backbone (Krizhevsky et al., 2012). We concatenate its normalised feature maps, each rescaled by the square root of the LPIPS weights and the spatial size, so that ∥ΨLPIPS (x) − ΨLPIPS (x′ )∥2 is the LPIPS distance, giving m = 31,872 coordinates. Images are resized to 64 × 64 first, so the perceptual bound measures LPIPS at that resolution. ΨLPIPS is a fixed public map, so it is admissible (Theorem 3.5) provided its training images are disjoint from the records we protect. We do not report an LPIPS bound on ImageNette, whose images are drawn from the ImageNet training set on which the LPIPS features were trained. The data-blind baseline. The prior mean E[ΨLPIPS (x)] is the best data-blind guess in feature space, but it is not the feature vector of any image, so an attacker who must output an image cannot return it. For any image x̂ chosen without seeing the release, E∥ΨLPIPS (x) − ΨLPIPS (x̂)∥2 = tr ΣΨLPIPS + ∥ΨLPIPS (x̂) − EΨLPIPS (x)∥2 . The first term does not depend on x̂, so the optimal data-blind image is the one whose features lie closest to the prior mean. We find it by searching over images directly. Because the objective is not convex, we run the search from 16 different starting images, drawn from Dshadow , and keep the best result. From each, we run 400 steps of Adam on the pixels of x̂ to minimise ∥ΨLPIPS (x̂)−µ̂ΨLPIPS ∥2 plus a total-variation penalty of weight 10−4 , and we keep the final image whose features are closest to µ̂ΨLPIPS . Here µ̂ΨLPIPS is the mean feature vector over 2,000 images of Dshadow , and the pixels are kept in the valid range by the reparametrisation x̂ = 21 (tanh u + 1). The gradient passes through the frozen network, so each step moves the image towards features closer to the mean. Descent may stop at a local minimum, so the error we report may slightly exceed that of the optimal data-blind image. 27

Preprint. Under review.

Because the second term error above tr ΣΨLPIPS . We p is positive for every image, this baseline has ⋆ ⋆ normalise ρΨLPIPS by tr ΣΨLPIPS , as in equation 3, which keeps ρ ≤ 1. On that scale the image baseline sits slightly above 1 (1.131 on MNIST and 1.045 on CelebA), and we draw it as the grey dashed line in the LPIPS panels of Figures 3 and 7. G.4

T HE PRIVACY- SPECTRUM EXPERIMENT

The bound. We report results against ε, the quantity practitioners compare, rather than σ or γ. For each target ε we calibrate the noise multiplier σ with the PRV accountant (Gopi et al., 2021; Yousefpour et al., 2021) at δ = n−1.1 train , with ntrain the training-set size. Since q and σ are constant, every step has the same charge K PRV in Theorem 4.1, so γ = T K PRV / ln 2 needs a single onedimensional integral per configuration, which we evaluate with a 256-node quadrature rule. Against a reference adaptive quadrature its error is at most 6.7 × 10−9 bits in γ over all configurations, six orders of magnitude below the smallest entropy margin per dimension (0.0054 bits), so it has no visible effect on ρ⋆ . Configuration. Our configuration follows common DP-SGD practice (Ponomareva et al., 2023; De et al., 2022) in its main ingredients: large Poisson-subsampled batches trained for many steps, GroupNorm, augmentation multiplicity and weight averaging (below). Hyperparameters are not tuned per privacy level: expected batch size b = 1024 for 100 epochs, giving T = 4,900 steps at q = 0.0204 (MNIST), T = 4,400 at q = 0.0227 (CIFAR-10, CelebA) and T = 1,000 at q = 0.1 (ImageNette), with a data-independent initialisation as Theorem D.1 requires. We clip at C = 1 on every dataset; neither γ nor ρ⋆ depends on C (Section 4). Utility. We train a LeNet-5 (LeCun et al., 1998) on MNIST (∼62K parameters), a Wide-ResNet16-4 on CIFAR-10 (∼2.7M) and a ResNet-18 on CelebA and ImageNette (∼11M). All use GroupNorm (Wu & He, 2018) rather than BatchNorm, which would make each record’s gradient depend on the others in its batch and break Theorem D.2. Training uses Opacus (Yousefpour et al., 2021) at the configuration above, with SGD at momentum 0.9 and cross-entropy loss. We use augmentation multiplicity 4 on CIFAR-10, CelebA and ImageNette (1, i.e. none, on MNIST) (De et al., 2022; Ponomareva et al., 2023), meaning that four augmentations of each example are drawn and their gradients averaged before clipping, so every record still contributes a single clipped gradient. We also keep an exponential moving average of the iterates during training (decay 0.999) and use those averaged weights when measuring accuracy, while training itself continues from the raw iterates (De et al., 2022; Ponomareva et al., 2023). Averaging cancels much of the noise DP-SGD injects, since that noise is independent across steps, and it is post-processing of released iterates, so it costs no privacy. The learning rate is fixed per dataset (0.5 on MNIST, 1.0 on CIFAR-10, 0.25 on CelebA and ImageNette) and reused at every privacy level, so the accuracies we report are attainable but not tuned per level. Every privacy level is trained with 3 seeds and we report the mean and standard deviation of test accuracy. The non-private baseline is the same architecture and optimiser trained without clipping or noise, with a single seed and its own learning rate, selected on Dval (0.05 on MNIST, CIFAR-10 and ImageNette, 0.1 on CelebA), and accuracy is reported on Dtest . Hyperparameter tuning. Any search over the clip norm or the learning rate reads the training data, so strictly their leakage composes with that of the final run (Theorem D.1) (assuming that an adversary can observe the noisy trajectories of these training runs). As is standard in the DP-SGD literature (Ponomareva et al., 2023), we do not include it, and the reported ε and ρ⋆ are those of the final run alone. Including it requires no new theory. Since γ reads only the schedule (qt , σt ), a search of k runs is simply a longer trajectory and adds the leakage of k runs, so a practitioner can either sum Theorem 4.1 over every run or move the search onto data outside the protected set (Section F.3). G.5

T HE ATTACK ON DP-SGD

Model. We attack the model of Schwethelm et al. (2024): a single linear layer whose scalar output is the loss, ℓ(W ; u) = W u, so that the per-example gradient is the input u itself, whatever the value of W . Nothing of the record is lost to the architecture, and since Theorem 4.1 holds for every model and loss at a given (qt , σt ), it is the model on which an attack can come closest to the bound. The 28

Preprint. Under review.

0.6 0.4 0.2 0.0

10 1

101 100 (training config, = n 1.1)

(bound) no-DP ceiling

102

CIFAR10

1.0

pixel MSE (wrn16_4_gn)

0.8

test accuracy (bound)

(bound)

0.8

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

0.6 0.4 0.2 0.0

10 1

101 100 (training config, = n 1.1)

(bound) no-DP ceiling

utility (test acc)

1.0

LPIPS (lenet5)

0.6 0.4 0.2 0.0

10 1

101 100 (training config, = n 1.1)

(bound) no-DP ceiling

102

IMAGENETTE

0.8 0.7

0.8

0.6

0.5

0.4

0.4 0.3

0.2 0.0

0.2 10 1

101 100 (training config, = n 1.1)

(bound) no-DP ceiling

CIFAR10

102

0.1

utility (test acc)

LPIPS (wrn16_4_gn)

0.8 0.6 0.4 0.2 0.0

10 1

101 100 (training config, = n 1.1)

(bound) no-DP ceiling

utility (test acc)

pixel MSE (resnet18gn)

LPIPS 1.0

test accuracy (bound)

(bound)

0.8

1.0 0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

102

1.0

utility (test acc)

Bound vs utility MNIST

0.9 0.8 0.7 0.6 0.5 0.4 0.3 0.2 0.1

test accuracy

pixel MSE (lenet5)

test accuracy (bound)

MNIST

1.0

MSE

test accuracy

Bound vs utility

102

utility (test acc)

Figure 5: What a deployed DP-SGD run guarantees across the privacy spectrum, on MNIST, CIFAR10 and ImageNette (CelebA is in Figure 2). At each target ε (expected batch 1024, 100 epochs, C = 1, δ = n−1.1 train ): 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 ± standard deviation over 3 seeds; non-private baseline as the dotted horizontal line). Shaded: the ε ≤ 1 (dark) and 1 < ε ≤ 10 (light) regimes of Ponomareva et al. (2023); ε > 10 is unshaded.

Preprint. Under review.

input is centred with a mean fixed on Dshadow : u = x − x̄ in pixel space and u = ΨLPIPS (x) − Ψ̄ in feature space, where the frozen feature map of Section G.3 is placed before the layer so that the attack estimates the features directly. The informed adversary knows the other records and which of them were sampled, so it subtracts their clipped gradients from the released sum. What remains of step t is Yt = 1t a(u) u + σC ξt , (36) the target’s clipped gradient a(u)u, with a(u) = min{1, C/∥u∥} the clip factor, present or absent according to the target’s participation 1t ∼ Bernoulli(q), plus the mechanism’s noise σC ξt with ξt ∼ N (0, I). The adversary does not observe 1t (1t ≡ 1 at q = 1). We take C = 0.3, small enough that every gradient is clipped, as Hayes et al. (2023) do for the same reason (their App. K.1). Attack. We use the prior-aware attack of Hayes et al. (2023), in the likelihood form of their Appendix G. The adversary holds candidates z1 , . . . , zn and, for each, computes the probability of the releases if the target were zj . Under that hypothesis each release is either cj = a(zj )zj plus noise, if the target was sampled at that step, or noise alone, so the probability is a product over steps of two-way mixtures, T h i Y 2⟨Yt , cj ⟩ − ∥cj ∥2 p(Y1:T | zj ) ∝ (1 − q) + q eLtj , Ltj = , (37) 2σ 2 C 2 t=1 which is their score sz with a general clip norm in place of their C = 1. Participation is integrated out exactly, step by step, and the clip factor of every candidate is known, so the score is in closed form for any q. We depart from Hayes et al. (2023) in two ways. Their adversary is given a shortlist that contains the target (their Section 3.4); ours holds the shadow sample Dshadow (58,000 records on MNIST, 44,000 on CelebA), which does not, so it knows the source only through a sample of it and is weaker than the adversary of Section 3.1. And where they report the candidate with the largest score (their Appendix G), we report the posterior mean n X p(Y1:T | zj ) wj zj , wj = Pn û = , (38) k=1 p(Y1:T | zk ) j=1 the candidates averaged by how well each explains the releases, since the bound controls squared error and the posterior mean minimises it under the candidate prior. The reconstruction is x̄ + û in pixel space and Ψ̄ + û in feature space, and costs one matrix product per target. Evaluation. Both configurations, (q, T ) = (1, 1) and (0.02, 100), are run on the same 100 heldout targets (Section F.4), each attacked once, with σ solved so that Theorem 4.1 charges the target γ. A marker p is the ratio equation 3 with the expectation replaced by the mean over targets, divided by the tr Σ̂ of Table 3, the same scale as the bound; in the LPIPS panels it is a feature-space error, which is what the bound controls, and the dashed lines show, for both configurations, the error after inverting û to an image by gradient descent on ∥ΨLPIPS (x̂) − ẑ∥2 . Two features of Figures 3 and 7 are worth stating. Subsampling weakens the attack at matched γ by up to 0.08 in ρ (paired differences −0.03 to +0.08; it is slightly stronger only on CelebA LPIPS at 72 bits), the cost of not knowing when the target participated, as Hayes et al. (2023) also observe. And at 72 bits the CelebA markers stop at 0.71–0.73 (pixel) and 0.91–0.93 (LPIPS), over the two configurations. The attack can only output a weighted average of shadow records, so it can get no closer to a held-out face than such an average can, and Dshadow holds no near duplicate of a held-out face. This limits the attack, not the bound, which depends on the source’s entropy rather than on any sample of it, and is zero at that leakage in any case. G.6

T IGHTNESS AT FIXED LEAKAGE

The bound equation 14 sees the mechanism only through γ, so it holds for every release that leaks at most γ bits about the record, whether or not that release is a model. It can therefore be tight at a given γ only against the release whose bits buy the most reconstruction, which is not DP-SGD. We construct one that is close to it, a vector quantiser, and use it to locate the slack of the bound. At each leakage we compute ρ⋆ ≤ ρblk ≤ ρcb ≤ ρdpsgd , (39) |{z} |{z} | {z } Theorem G.1

attack on the quantiser

attack on DP-SGD

Preprint. Under review.

MNIST

1.6

pixel

1.4

1.2

1.0

0.8

0.6

0.4

0.2

0.0

100

(bits)

CelebA

1.6

101

0.0

102

pixel

1.4

1.2

1.0

0.8

0.6

0.4

0.2

0.2 100 certified floor

(bits)

101

100

0.0

102

single step (q=1, T=1): mean, 10 90% band, targets

100

LPIPS

(bits)

CelebA

1.6

1.4

0.0

MNIST

1.6

101

102

LPIPS

(bits)

101

102

subsampled (q=0.02, T=100)

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–90th 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% at γ ≤ 0.72 bits, 1–11% at 2.89 bits, at most 3% at 8.01 bits), which the bound permits.

Preprint. Under review.

where ρblk relaxes the bound while remaining a lower bound on every attack of the quantiser (Table 7). Across the four panels of Figures 3 and 7 the first gap is 0.10–0.33 in ρ and the second at most 0.03. The codebook mechanism. The distortion–rate function is the least expected squared error that a release of R bits permits. It is approached by quantisers, which release the index of the codeword nearest to the record and so spend every released bit on reducing squared error (Cover & Thomas, 2006, Ch. 10). We use a single-record quantiser of this kind. No model is trained: the mechanism releases the index Q ∈ {1, . . . , M } of the codeword nearest to Ψ(xi ), among M = 2R codewords in the space of Ψ. The codewords are built in two steps. First, k-means on Dshadow gives M centroids. Second, we assign Dest to these centroids with at most ⌈nest /M ⌉ records per cell (a single balanced step in the spirit of Malinen & Fränti (2014)), and take the cell means as the codewords. The size cap spreads the codewords so that every cell stays populated, which estimating the per-block leakage below requires. The codebook is fixed independently of the held-out targets and is known to the adversary; for LPIPS the same construction is applied to ΨLPIPS (x). Every bound below holds for any codebook, and a worse codebook only widens the measured gaps, so its optimality is not at issue. Since Q is a deterministic function of xi with M values, independent of X −i , the release leaks I(xi ; Q | X −i ) = H(Q) ≤ R bits. We charge γ = R, which slightly overstates the leakage (the realised H(Q) is within 0.07 bits of R) and so only lowers ρ⋆ . Below one bit, which a deterministic codebook cannot reach, we take the two-cell codebook and pass Q through a binary symmetric channel: the release Y equals Q with probability p ∈ [ 12 , 1] and the other index otherwise, independently of everything else. Because Y depends on xi only through Q, it leaks exactly γ = I(Q; Y ) = Hb f0 p + f1 (1 − p) − Hb (p) bits (Cover & Thomas, 2006, Ch. 7), where f0 , f1 are the cell frequencies, and every γ ∈ (0, Hb (f0 )] is reached by choice of p. The codebook attack. The adversary sees the release Z (Z = Q for the deterministic codebook, Z = Y for the randomised one) and the mechanism does not involve X −i , so its reconstruction is a function g(Z). Under squared error the optimal g is the conditional mean E[Ψ(xi ) | Z] (Bishop, 2006). For the deterministic codebook this is the mean of the released cell, and for the randomised codebook it is the average of the two cell means, each weighted by the probability that it is the true cell given the release. We estimate the cell means and frequencies on Dest and report the error on targets held out from Dshadow and Dest . The estimate is a function of the release and of records disjoint from the target, so it is a valid reconstruction of Section 3.1, and estimation error can only raise its error above the optimum, which widens rather than narrows the measured gap. The bounds. In the proof of Theorem 3.7 the mechanism enters in exactly one place: the rate at which each block’s Shannon lower bound is taken, every block being charged the whole of γ. Write −i z̃b for the dithered block z̃iΠb Ψ and γP b := I(z̃b ; θ | X ) for the leakage block b receives, which for the quantiser is I(z̃b ; Q) = h(z̃b ) − c Pr(Q = c) h(z̃b | Q = c). Both bounds in equation 39 have the form Nk 1 X k 2 · F (b) − ν 2 , (40) ρ ≥ 2πe tr ΣΨ Nk b=1

with Fcert = 2 2(h(z̃b )−γ)/k the bound before its Jensen step and Fblk = 2 2(h(z̃b )−γb )/k charging each block only the leakage it received. The difference is the per-block charge. Proposition G.1 (Per-block bound). In the setting of Theorem 3.7, γb ≤ γi for every b, and equation 40 holds with Fblk . In particular Fcert ≤ Fblk at any common (k, ν 2 ). Proof. z̃b → xi → (θ, X −i ) is a Markov chain (Theorem 3.5), so γb ≤ γi by data processing, and Fcert ≤ Fblk follows. The proof of Theorem 3.6 at the representation Πb ◦ Ψ uses the leakage only in Step 1, as I(z̃b ; Πb ẑiΨ ) ≤ γi , and data processing along z̃b → (θ, X −i ) → Πb ẑiΨ gives the k 22(h(z̃b )−γb )/k − ks2 sharper I(z̃b ; Πb ẑiΨ ) ≤ γb . Steps 2–4 then give E∥Πb (Ψ(xi ) − ẑiΨ )∥2 ≥ 2πe for every block, and averaging over b by equation 21 and dividing by tr ΣΨ gives equation 40 with Fblk . Why the relaxed bounds use k = 1. The per-block bound is evaluated at k = 1. Its exponent carries γb rather than P γ, so nothing pushes it towards large k, and one-dimensional plug-ins suffice for γb = h(z̃b ) − c Pr(Q = c) h(z̃b | Q = c), which is why every cell must hold enough records. 32

Preprint. Under review.

Interpretation. The chain splits the distance from the bound to the DP-SGD attack into three gaps. The first, from ρ⋆ to ρblk , is 0.10–0.33 across the four panels of Figures 3 and 7. It is the cost of charging every block the full γ. Removing it would require either a per-block leakage bound for the mechanism or a lower bound on the entropy of the whole record, and the plug-in caps the latter at log2 n bits above the dither entropy (Section E.1). The second, from ρblk to ρcb , is at most 0.03 (Table 8, last column), and slightly negative, within standard error, on CelebA pixels at R = 3–5. Since ρblk lower-bounds every attack on the codebook, this small gap means both that the Shannon lower bound is close to tight for these sources and that our codebook attack is close to optimal. The third, from ρcb to ρdpsgd (Tables 6 and 8), is specific to DP-SGD. The leakage γ fixes how many bits are released, not which: the codebook spends its bits on a cell index chosen for reconstruction, whereas DP-SGD spends them on a noisy clipped gradient spread over every direction, so the same γ buys far less reconstruction. This gap is the margin by which Figures 2 and 5 are conservative for DP-SGD. It may also include slack in the accountant, since γ upper-bounds DP-SGD’s true leakage, and the suboptimality of our attack, neither of which the chain can separate from the mechanism.

MNIST, pixel

MNIST, LPIPS

1.0

0.8

0.6

0.4

0.2

0.0

10 1 lower bound point estimate

100

(bits)

101

per-block blk prior ( = 1)

102 realizable prior codebook

0.0

10 1

single step subsampled

100

(bits)

101

102

dashed: inverted to image (LPIPS)

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. ρblk is drawn while every codebook cell holds 20 estimation records. Dotted: the prior at ρ = 1. On MNIST the attack reaches lower ρ than on CelebA at high leakage because the shadow sample contains near-duplicates of many held-out digits (Figures 8 and 9).

Preprint. Under review.

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 (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 κπ = PrZ,Z ′ ∼π [Z = Z ′ ], which coincides with a baseline success only under a uniform prior. ∆ 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, Rényi, and f -differential privacy), CMI (conditional mutual information), LCB (lower confidence bound), HCRB (Hammersley–Chapman– Robbins bound), CRB (Cramér–Rao bound), FIL (Fisher information leakage), dFIL (diagonal FIL), RR (randomized response). 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

ε-LDP: eε scaling Pr[error ≤ η]

Baseline success p

Analytic: Uniform/Zipfian

MNIST, CIFAR-10, Flickr, Reddit: Accuracy gap

Balle et al. (2022)

Informed, final release

RDP/ε-DP: eε scaling

Pr[error ≤ η]

Baseline success κ

Analytic: NA Uniform/Gaussian

Xiao & Devadas (2023)

Uninformed, final release

PAC Privacy: I(X; M(X) + B)

Pr[error ≤ η]

Baseline success δ Analytic: Uniform population

CIFAR-10, MNIST: Noise magnitude

Guo et al. (2023)

Informed, final release

RDP + Fano: Generalized Fano

Pr[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[exact]

Baseline success κ

Analytic: Uniform shortlist

MNIST, CIFAR-10: Success probability

Kaissis et al. (2023)

Informed, final release

f -DP: Closed-form / Edgeworth

Pr[exact]

Baseline success κ

Analytic: Uniform 1/n prior

Numerical: success bound vs. κ at published DP-SGD hyperparameters

Swanberg et al. (2025)

Informed (n targets), final release

Pure/f -DP: eε tail

Pr[count of hits]

Baseline success π

Analytic: Product LLM canaries, distribution tabular: D1 ⊗ · · · ⊗ Dn Advantage, Success

Kulynych et al. (2026)

Informed, final release

f -DP: Trade-off (Thm. 3.1); TV (Thm. 3.3)

Pr[attack success] Baseline success base

Analytic: Scalar worst-case

US Census, GPT-2: Advantage, Accuracy

Guerra-Balboa et al. (2026)

Target-informed, final release

TV (Thm. 4.2); density difference (Thm. 4.3)

∆ Pr[error ≤ η]

Collision probability κπ

Uniform/Dataestimated frequencies

MNIST, Adult, Porto: RAD

Guo et al. (2022)

Informed, final release

RDP: HCRB (Thm. 1); FIL: CRB (Thm. 2)

E[MSE]

No prior; domain geometry / Fisher info

Analytic: bounded Z; regularity; non-vacuous only for unbiased attacks

MNIST, CIFAR-10: MSE lower bound; dFIL vs. reconstruction

This paper

Informed, all iterates

CMI: KL of dominating pair

E[MSE]

Differential entropy

Empirical: LCB from sample

MNIST– ImageNette: MSE, LPIPS

Preprint. Under review.

Table 2: The partitions of Figure 4, and what constrains each. The requirement column refers to Section F.1; ⋆ marks a disjointness the guarantee or the threat model requires, the rest are kept for a clean joint statement and could be relaxed. Split

Supplies

Requirement Disjoint from

Size and property

shared — the source side, computed once per dataset ⋆ ⋆ D⊥ U = d−1/2 Hd V ⊤ , tr Σ̂, Req 3, Req 4 Dest , Dtargets dither scales

Dest

h̄LB

≳ d, for a full-rank Σ̂; may be replaced by a data-free U and a declared tr Σ largest available; i.i.d. from Px ; margins ∝ n−1/2

⋆ D⊥

Req 5

(a) deployment, and the privacy-spectrum runs Dtrain every charged DP-SGD Req 1, Req 2 Dval , Dtest run

Dval Dtest

selection among runs reported accuracy

(b) the attack experiment Dshadow candidate set, centring mean Dtargets the reconstructed records

i.i.d. from Px ; no cross-record preprocessing; may overlap D⊥ and Dest small small

Dtrain Dtrain , Dval

Req 6 Req 7

⋆ Req 8, Req 9 Dtargets

most of Dest

⋆ ⋆ D⊥ , Dshadow

Req 10

100; i.i.d. from Px ; enough for the standard error of the mean; may lie in Dest

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⊥ (sizes in Section G.1). RMSEprior / d is the per-coordinate root-mean-squared error of the prior-mean guess, in grey levels for pixels and feature units for ΨLPIPS (m = 31,872). pixel (Ψ = id)

perceptual (Ψ = ΨLPIPS ) √ √ tr Σ UCB margin RMSEprior / d tr ΣΨLPIPS UCB margin RMSEprior / m

Dataset MNIST CIFAR-10 CelebA ImageNette

3.43 × 106 1.24 × 107 5.91 × 107 2.46 × 108

2.5% 3.2% 0.5% 16.6%

66.2 63.6 69.3 70.7

0.1338 0.2463 0.1445 —

5.8% 3.3% 0.6% —

2.05 × 10−3 2.78 × 10−3 2.13 × 10−3 —

Table 4: Values behind Figures 2 and 5: test accuracy (mean over 3 seeds) and the pixel and perceptual bounds at each target ε, each a 95% lower bound. †: the ε > 10 band of Ponomareva et al. (2023). MNIST

CIFAR-10

CelebA

ImageNette

ρ⋆px

ρ⋆ΨLPIPS

acc.

ρ⋆px

ρ⋆ΨLPIPS

acc.

ρ⋆px

ρ⋆ΨLPIPS

acc.

1 0.313 0.907 2 0.865 0.892 4 0.953 0.845 8 0.970 0.754 16† 0.971 0.556 32† 0.972 0.131 64† 0.976 0.000

0.908 0.886 0.831 0.726 0.536 0.169 0.000

0.187 0.887 0.373 0.867 0.564 0.815 0.655 0.711 0.703 0.523 0.739 0.131 0.765 0.000

0.952 0.940 0.901 0.822 0.612 0.188 0.000

0.923 0.888 0.946 0.861 0.954 0.805 0.957 0.696 0.961 0.513 0.967 0.131 0.963 0.000

0.944 0.931 0.892 0.801 0.588 0.174 0.000

0.122 0.865 0.239 0.845 0.440 0.795 0.603 0.683 0.662 0.445 0.702 0.000 0.723 0.000

—

0.905

—

0.971

—

0.779

acc.

non-priv. 0.989

—

ρ⋆px

—

Preprint. Under review.

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 ⋆ grows with γ overall up to single grid steps on CelebA. k⋆ (pix / ΨLPIPS )

ν 2⋆ (pix / ΨLPIPS )

5.574 3.028 1.741 1.110 0.796 0.617 0.497

14 16 16 28 28 28 –

16 32 32 32 32 32 –

1.6 1.6 1.6 1.6 0.8 0.4 –

3.2 6.4 3.2 1.6 0.8 0.4 –

0.049 0.171 0.577 1.806 5.108 13.317 33.222

5.838 3.167 1.815 1.147 0.816 0.629 0.504

6 6 12 32 32 32 –

16 32 32 32 32 32 –

0.8 0.4 0.8 1.6 0.8 0.4 –

1.6 3.2 3.2 1.6 0.8 0.4 –

1 2 4 8 16 32 64

0.049 0.171 0.577 1.806 5.108 13.317 33.222

5.838 3.167 1.815 1.147 0.816 0.629 0.504

3 6 8 16 32 24 –

16 32 32 32 32 32 –

0.2 0.4 0.4 0.8 0.8 0.2 –

1.6 3.2 3.2 1.6 0.8 0.4 –

1 2 4 8 16 32 64

0.060 0.207 0.682 2.111 6.010 15.682 38.345

10.969 5.941 3.313 1.948 1.242 0.863 0.639

24 24 32 32 32 – –

n/a n/a n/a n/a n/a – –

3.2 3.2 3.2 1.6 0.8 – –

n/a n/a n/a n/a n/a – –

Dataset

γ (bits)

MNIST

1 2 4 8 16 32 64

0.048 0.169 0.570 1.785 5.042 13.150 32.883

CIFAR-10

1 2 4 8 16 32 64

CelebA

ImageNette

Table 6: The attack against the bound: ρ over the 100 targets, bootstrap standard errors between 0.013 and 0.024. γ (bits)

0.72

2.89

8.01

72.13

MNIST, pixel

q=1 (q, T ) = (0.02, 100) bound

0.987 1.006 0.831

0.948 0.984 0.673

0.848 0.921 0.397

0.620 0.690 0

MNIST, LPIPS

q=1 (q, T ) = (0.02, 100) bound

0.999 1.001 0.816

0.922 0.964 0.653

0.845 0.926 0.396

0.636 0.681 0

CelebA, pixel

q=1 (q, T ) = (0.02, 100) bound

0.920 0.970 0.789

0.884 0.941 0.628

0.768 0.840 0.373

0.707 0.725 0

CelebA, LPIPS

q=1 (q, T ) = (0.02, 100) bound

0.983 0.991 0.878

0.963 0.992 0.734

0.911 0.975 0.459

0.933 0.906 0

Preprint. Under review.

Table 7: The chain equation 39: what each term is, how it is evaluated, and what the gap between consecutive terms measures. F (b) in equation 40

Lower-bounds

How evaluated

Gap to the row above —

ρ⋆

Fcert = 2 2(h(z̃b )−γ)/k every attack on every release leaking ≤ γ

Theorem 5.1 at γ = R, with its grid and margins

ρblk

Fblk = 2 2(h(z̃b )−γb )/k every attack on this release

k = 1, ν 2 = 0.2, per-block charge one-dimensional plug-ins equation 31 on Dest for h(z̃b ) and each h(z̃b | Q = c); point estimate; every cell must hold 20 records, so R ≤ 8 (pixel) and R ≤ 7 (LPIPS)

ρcb

—

cell-mean decoder; error residual slack of the on held-out targets, Shannon lower bound at bootstrap standard error rate γb , plus sampling error of the targets

ρdpsgd —

—

posterior mean under what DP-SGD fails to the empirical shadow convert into prior (Section G.5) on reconstruction one full-batch step, at γ = 1/(2 ln 2 σ 2 ) bits, and on T = 100 steps at q = 0.02

Preprint. Under review.

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

ρcb (SE)

ρblk − ρ⋆

ρcb − ρblk

MNIST, pixel 1 0.809 0.951 2 0.739 0.908 3 0.665 0.859 4 0.606 0.811 5 0.558 0.765 6 0.507 0.728 7 0.454 0.692 8 0.397 0.658

0.975 (0.005) 0.931 (0.005) 0.882 (0.005) 0.834 (0.005) 0.790 (0.005) 0.754 (0.005) 0.721 (0.005) 0.691 (0.005)

0.142 0.169 0.194 0.205 0.207 0.220 0.238 0.261

0.023 0.023 0.023 0.023 0.026 0.027 0.029 0.032

CelebA, pixel 1 0.760 0.858 2 0.682 0.809 3 0.622 0.772 4 0.566 0.737 5 0.518 0.711 6 0.472 0.687 7 0.424 0.662 8 0.374 0.641

0.862 (0.006) 0.810 (0.005) 0.770 (0.005) 0.737 (0.005) 0.709 (0.005) 0.687 (0.005) 0.667 (0.005) 0.651 (0.004)

0.098 0.127 0.149 0.171 0.193 0.215 0.239 0.267

0.004 0.001 −0.002 0.000 −0.002 0.000 0.005 0.010

MNIST, LPIPS 1 0.787 0.920 2 0.712 0.871 3 0.646 0.815 4 0.581 0.765 5 0.538 0.725 6 0.493 0.688 7 0.446 0.657

0.932 (0.004) 0.886 (0.004) 0.828 (0.005) 0.778 (0.005) 0.740 (0.005) 0.706 (0.004) 0.678 (0.004)

0.133 0.159 0.169 0.184 0.186 0.195 0.211

0.012 0.015 0.013 0.013 0.015 0.017 0.021

CelebA, LPIPS 1 0.851 0.962 2 0.789 0.939 3 0.727 0.917 4 0.662 0.898 5 0.593 0.878 6 0.550 0.857 7 0.506 0.839

0.980 (0.005) 0.955 (0.005) 0.933 (0.005) 0.912 (0.005) 0.895 (0.005) 0.878 (0.005) 0.862 (0.005)

0.112 0.150 0.190 0.235 0.285 0.307 0.333

0.017 0.016 0.016 0.015 0.017 0.020 0.023

ρ⋆

Preprint. Under review.

G.7

A DDITIONAL FIGURES CelebA target

=0.98 =0.2

=0.92 =0.72

=0.88 =2.89

target

=0.99 =0.2

=0.98 =0.72

=0.96 =2.89

CelebA

pixel =0.77 =8.01

=0.71 =30

=0.71 =72.13

=0.74 =500

=0.91 =8.01

=0.90 =30

=0.93 =72.13

=0.93 =500

LPIPS

Figure 8: Attack reconstructions at each leakage, CelebA. As Figure 9, for CelebA in pixel space (top) and LPIPS space (bottom). Dshadow holds no near duplicate of a held-out face, so the pixel ρ levels off near 0.71 beyond γ ≈ 70 bits.

Preprint. Under review.

MNIST target

=1.00 =0.2

=0.99 =0.72

=0.95 =2.89

target

=1.00 =0.2

=1.00 =0.72

=0.92 =2.89

MNIST

pixel =0.85 =8.01

=0.65 =30

=0.62 =72.13

=0.62 =500

=0.84 =8.01

=0.66 =30

=0.64 =72.13

=0.61 =500

LPIPS

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, γ ∈ {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 ρ 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 ρ, 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 ρ. In pixel space most reconstructed digits are wrong at ρ = 0.85 (γ = 8 bits) and all six are right at ρ = 0.65 (γ = 30 bits). The attack outputs a weighted mix of shadow images, none of them close to a held-out target, so ρ levels off near 0.62 beyond γ ≈ 30 bits.

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

Analyze & explore related research in Conceptio

Related documents