acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
differential privacy, DP-SGD, reconstruction attacks, data reconstruction, privacy guarantees, information theory, rate-distortion theory, privacy accounting, perceptual metrics

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.67 over 3 reviews, above 99% of the others.
Reviewer_NAhCOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper provides information theoretic lower-bounds that guarantee a minimum reconstruction error for the DP-SGD mechanism. These offer an operational interpretation and alternative to the (epsilon, delta) privacy metrics of DP. The bounds are generally in terms of the reconstruction ratio (RMSE compared to the prior-only reconstruction) of a representation of the target data. The essential theoretical steps involve utilizing the Shannon lower bound on distortion given an upper limit on the mutual information between the reconstruction and the target (as applied in Theorem 3.6), showing (via Theorem 4.1) an upper bound of this mutual information for the DP-SGD mechanism, and computing a lower confidence bound on the representation entropy (in Section 5), which is another key quantity needed for the distortion bound. Another key step is demonstrating how to tighten the bound via block orthogonalization in Section 3.3. The main contributions of the paper are theoretical, but they also provide experiments that apply these bounds when training classifiers for some standard image datasets (MNIST, CIFAR-10, CelebA, ImageNette).

Critical strengths

The theoretical development seems pretty solid and I could not find any flaws with the mathematical derivations. I think that translating from DP epsilon to an information-theoretic reconstruction loss guarantee provides a compelling operational interpretation to understand what a particular epsilon value for DP-SGD implies. It seems that the work was able to apply these bounds with actual experiments, in order demonstrate (in Figure 2) that there appears to be a meaningful region where both model accuracy and the reconstruction lower bound is reasonably high (even though epsilon is outside of the "strong" regime, i.e., >1). The results shown in Figure 3 compares these bounds against actual attacks.

Critical weaknesses

Overall, the presentation is poor, making it difficult to follow everything, especially the experimental details. Given that the authors acknowledge extensive use of AI across many tasks, including writing, coding, and mathematical development, and based on my recent experiences with reviewing many papers that have substantial amounts of AI-generated content, I have the impression that a lot of these presentation issues are due to over-reliance on AI in preparing and polishing the manuscript. Frankly, I would prefer clearer, more concise writing that states things more directly in plainer language, even if there are some minor grammatical/spelling issues. However, AI seems to often over-polish things at the expense of clarity and effective communication.

On the theory-side, the presentation seems mainly okay, but there are some minor issues that I will note below, and overall, I feel the presentation of theory is not so elegantly handled. However, on the experimental side, there are many practical details that are not sufficiently or confusingly explained. A lot of details get pushed into related Appendices, however these are particularly poorly presented and organized. In these experimental appendices, it especially feels like AI-generated writing that is overly verbose and unclear.

The first displayed equation (which unnumbered, but appears at Line 145 at the beginning of Section 3.1) defines the shorthand notation θ:=θ0:T=(θ0,…,θT)\theta := \theta_{0:T} = (\theta_0, \ldots, \theta_T). However, I recommend that the authors avoid using just plain θ\theta (without subscripts) to denote the trajectory as it could be confused with just a single instance of the model parameters, and I recommend replacing the equation with θ0:T:=(θ0,…,θT)\theta_{0:T} := (\theta_0, \ldots, \theta_T). For the most part, the paper does already avoid using θ\theta and typically just uses θ0:T\theta_{0:T}. However, there are some places in the Appendix, where θ\theta is used, seemingly with the intention to refer to the trajectory, but it could be easy for the reader to forget this intention. In one case, at the beginning of the proof of Lemma D.1, θ=θ0:T\theta = \theta_{0:T} is explicitly mentioned, but then the θ\theta shorthand is not even used for the proof nor the rest of Appendix D. Overall, I recommend to avoid defining notation that is unnecessary or shorthands like this that may cause confusion.

Assumption 3.1 assumes that the data is finite precision and hence technically supported on a finite discrete alphabet, which is reasonable given that all digital data represented with finite precision. However, this overly technical treatment requires the theoretical development to later massage the data distribution back into a continuous by introducing a dithering noise, which has a scale s that affects various bounds. While the authors do manage to isolate this dithering affect, the overall theory is made more cumbersome by this technical assumption, when alternative it could also be reasonable to just assume that the data has a continuous distribution with a finite differential entropy. Further, assumption 3.1 also makes imposes fixed quantization spacing of Δ\Delta, which does not appear to be later used nor necessary for the theoretical developments. Technically, floating point representations of numbers would not have fixed spacing, so this assumption is not technically true for many common forms of data that the paper may wish to consider. Of course, images with a fixed bit depth per channel would meet this assumption, but either way, this assumption seems a bit unnecessary.

Lines 174 states that the joint distribution (xi,θ0:T,X−ix_i, \theta_{0:T}, X^{-i}) is identical for all ii, solely as a consequence of Assumption 3.2. However, this is not technically true in general, since nothing (at this point) has constrained the training mechanism to treat all data samples equally. However, this statement can be easily resolved by merging it with the next sentence, which clarifies that it is "because DP-SGD treats every index alike under Poisson subsampling".

It seems a bit awkward to define νΨ2\nu_\Psi^2 twice (in both Equations 3 and 5 on the same page). Since it feels a bit out of place and unnecessary in Equation 3, and is only used later in Theorem 3.6 (where Equation 5) appears, I recommend removing the first instance, and keeping only the second.

Line 315 defines Ht−1:=θ0:t−1H_{t-1} := \theta_{0:t-1} (note: HH should be in the mathcal font here in this comment, but this review form does not seem to handle the mathcal font properly), but this is not used until much later in Appendix D. It should either be moved to the Appendix to clarify this later usage, or maybe just avoid defining it altogether, since just using θ0:t−1\theta_{0:t-1} is already compact enough and is clearer as it avoids using more notation.

In Section 5, nn, which was previously used to denote the overall training set size, is explicitly redefined (Line 357) to denote the size of the samples used to estimate the data entropy. I recommend not reusing nn for this as it could cause confusion about the dataset is split across training/validation/test as well as between performing different estimates that are required for the bounds. Actually, this is still not entirely clear to me as the main body of the paper leaves it quite ambiguous with the Appendix F not helping to clarify.

Confusingly, Figure 4 (in Appendix F, page 25) seems to show DestD_\text{est} overlapping with part of the train, and all of the validation and test splits? However, this seems problematic as estimates calculated via DestD_\text{est} will seem to affect parameters chosen for training as specified in Algorithm 1 (page 25), i.e., to ultimately set σ\sigma for a given target ρ\rho.

Algorithm 1 also has other issues:

  1. It specifies σt\sigma_t as a required input, but then at the last step suggests inverting the calculations of some steps to set σ\sigma to target a given ρ∗\rho^*. It seems that this is offered as an alternative, but this procedure should be better clarified.
  2. Inverting steps 1 and 6 do not seem so obviously straightforward. These should be elaborated upon.
  3. This algorithm also introduces the concept of multiple runs, which introduces an additional layer of summation to step 1, differing from the analysis presented for the related Theorem 4.1. This concept should be further clarified, or maybe removed.

The conceptual figures (Figure 1 and the unnumbered/uncaptioned figure at the beginning of Section 6) do not really help to explain. Since they rely on notation and concepts that are only elaborated upon in the text, looking at these first does not really offer any sense of understanding. Figure 1 is placed quite early in the paper, on page 1, as a sort of teaser, but reading it at this point does not really offer more than presenting some keywords. Maybe it helps a bit to remind of some notation after reading the paper, but checking it first does not help the reader to understand the message of the paper better. Further, the latter conceptual figure (unnumbered in Section 6), firstly, should really have a caption and number to conform with the paper formatting requirements, and secondly, it uses the notation DestD_\text{est}, which seems to not be used until later in the Appendix.

The presentation of the experimental results is very unclear. In particular, for Figure 3, I haven't been able to understand what the curves "point estimate", "realizable prior", "inverted to image (LPIPS)" curves are exactly. It seems that lower-bound ρ∗\rho^* is their main lower-bound that is calculated via the method of the main body of the paper, including using the block orthogonalization of Section 3.3 and Corollary 3.7. However, there is also a "per-block ρblk\rho_\text{blk}" curve that seems to only be presented later in Appendix G.6 and related to Proposition G.1, which seems to possibly be a further generalization and strengthening of the bound? I think this per-block ρblk\rho_\text{blk} should be explained further in the main paper, and perhaps be merged into Section 3.3, if possible to manage in a reasonable manner. I think the distinction between these bounds needs to be better clarified and explained.

It seems that the codebook curves provide an interesting comparative analysis, but I think it's worth explaining these a bit more in the main paper, rather than pushing the nearly all of the details into the Appendix, where it gets buried among many pages of material. It seems quite interesting that these coincide quite closely with the ρblk\rho_\text{blk} curve, but aren't these curves extended to higher γ\gamma? It would be interesting to see if they trend further down to zero or stay closer to the attack curves at higher γ\gamma.

Questions for authors

For the block orthogonalization trick, is kk divides mm strictly needed? If mm is already prime, does that severely limit the ability utilize this block orthogonalization trick? Would it not work for non-uniformly sized blocks?

In Figure 3, why do some curves ("per-block ρblk\rho_\text{blk}" and "codebook") not continue for larger γ\gamma?

What are the "point estimate", "realizable prior", "inverted to image (LPIPS)" curves shown in Figure 3?

What is the corresponding range of epsilons and accuracies swept over for the range of γ\gamma considered in Figure 3?

4 comments
AuthorsOpenReview ↗

Response - Part 1

We thank the reviewer for their time and effort spent on this detailed review. A number of useful points are raised which should go towards making it a better manuscript, we hope you will see that we have given serious attention to addressing your comments and concerns (detailed below and to be included in the paper). We will be providing an updated pdf as soon as possible incorporating all reviewers comments. Once this is done we will update you with pointers to each individual reviewer showing where their comments have resulted in changes to the paper.

(Presentation - Use of AI.) We did use AI tools as disclosed, however, the use was targeted and heavily supervised and modified by us and we take the presentational issues as ours. Purposefully, some less important content had to be shifted to the appendix in order to meet space requirements. Now we have some extra space we will pull the more important details into the main text (as discussed below) which should greatly aid readability and we think was probably a large contributor to your issue with the presentation.

(Presentation - Trajectory notation.) We agree that this extra notation wasn’t necessary. We now write θ0:T\theta_{0:T} throughout.

(Methodology - Assumption 3.1.) If we were simply to set Ψ=id\Psi=id (the identity) and just use the expected MSE on the data source, then we agree that the theory would be simpler in the continuous case if we were to ignore the fact that digital computers only have finite (even if large) precision. Although we feel this would be at the expense of a degree of rigour. However, we wish to allow for the flexibility of using a freely chosen representation Ψ\Psi. After applying Ψ\Psi the resulting distribution could place positive probability on a set of zero volume in Rm\mathbb{R}^m, for example a lower-dimensional surface or isolated points. The Shannon lower bound uses differential entropy (which is defined relative to Lebesgue measure) and for such a distribution it is −∞-\infty (or undefined), so the conditions required by our bound are not met. We must therefore either add dither after applying Ψ\Psi, or take the entropy relative to a different reference measure adapted to the support of the distribution, which is not straightforward and would make the theory more involved. So, a continuous source wouldn’t simplify the overall presentation of the paper.

(Presentation - Δ\Delta) As you have correctly identified the fixed spacing Δ\Delta is not required. Accordingly, we will drop Δ\Delta.

(Presentation - Line 174.) Agreed, the sentences should be merged as suggested and we will implement it.

(Presentation - Duplicate definition of νΨ2\nu_{\Psi}^{2}.) Agreed, the first instance will be removed.

(Presentation - Removing Ht−1H_{t-1} on line 315.) Agreed, the notation will be removed.

(Presentation - Overloading nn.) Agreed, we will amend the paper to use sub-scripted nn's which we already use in part of the paper so ntrainn_{\mathrm{train}} is now reserved for the training set and nestn_{\mathrm{est}} for the estimation sample size.

(Methodology - Data splits and Algorithm 1.) First, to be clear, none of our experimental results use DestD_{\mathrm{est}} to choose any of the hyper-parameters; they are run after training has been carried out. We agree that Algorithm 1 is unclear in places and we will revise it to make it totally unambiguous in terms of input, output and the steps involved. We will also add a separate algorithm detailing the 'inverted process' (ρ∗→(q,σ)\rho^{*} \rightarrow (q, \sigma)). If one wants to use the second (inverted process) algorithm then one must use a different data partition than the one currently given in the paper as this can leak information that wouldn't be covered by our bound. We will add text making this clear and describing how one should partition data if using this ('inverted') algorithm and if using our bound during tuning or in some other part of the design process. This is subtle but important and we thank the reviewer for bringing this to our attention.

(Presentation - Conceptual figures.) We respectfully disagree that Figure 1 isn't useful and think it provides an important aid as to the structure of the methodology. However, we concede that it could be made more friendly to the first-time reader. We will change the caption of the figure to explain the notation in Figure 1. We will add a caption and introductory sentence to the figure at the top of section 6. We will also replace the x1:nx_{1:n} notation in Section 5 which should be DestD_{est} which will also make the figure in section 6 clearer. In its caption we will also refer the reader to the (corrected) Algorithm 1 (or replace the entire figure with the corrected Algorithm 1 if we have enough free space in the main text).

AuthorsOpenReview ↗

Response - Part 2

(Presentation - Figure 3 and the slack decomposition.) We sympathise with the reviewers critique here and we had anticipated that the brevity of this experiment section may have posed problems. We tried our best to fit fuller explanations of this content into the main text, however, this wasn't possible to do except at the expense of other important content. Now we have a page of additional space we will expand the experimental section in the main text and as part of that provide a fuller description of what the "point estimate" (our bound without the confidence bound subtracted), "realizable prior" (the error given by the best image we could find that maps closest to the prior mean in lpips feature space), "inverted to image (LPIPS)" (the error given by the best image we could find that maps closest to the reconstruction in lpips feature space given by the attack) and per-block ρblk\rho_{\mathrm{blk}} curves are. The per-block curve ρblk\rho_{\mathrm{blk}} is a diagnostic, not a second guarantee. Our bound ρ⋆\rho^\star assigns every block the full leakage γ\gamma. For the codebook mechanism we can compute the leakage γb≤γ\gamma_b \le \gamma that each block actually receives, and ρblk\rho_{\mathrm{blk}} is the same bound with γb\gamma_b in place of γ\gamma (Proposition G.1). It therefore lower-bounds every attack on the codebook mechanism only, and the gap between ρ⋆\rho^\star (which for a given number of bits bounds what an attack can achieve on any mechanism) and ρblk\rho_{\mathrm{blk}} is what looseness in our bound comes from assuming the worst leakage for every block. Both curves stop because we only have a limited number of samples. A codebook at rate RR quantizes space into 2R2^R cells, and computing γb\gamma_b requires an entropy estimate within each cell. With too few records in a cell this estimate is biased low, which would understate the gap that ρblk\rho_{\mathrm{blk}} is meant to measure (and at some point we have more cells than samples). Hence we are restricted and unfortunately can't plot the curves for larger values of γ\gamma.

(Methodology - Block orthogonalisation, k∣dk \mid d.) Divisibility is mostly a convenience and isn't strictly necessary. Equal block sizes simplifies the methodology and we see no reason to use unequal block sizes unless the dimension, mm, has no suitable divisor (for example if mm is prime as you point out). In that case we suggest padding with zeros to a convenient dimension. The padded coordinates are deterministically zero and known to the adversary, so any attack on the padded representation immediately turns into an attack on the original representation. In practice the question does not arise as Hadamard matrices exist only at orders 1, 2 and multiples of 4 so a dimension with no suitable divisor, including but not limited to primes, will already be zero-padded to something divisible (Remark C.1). Optimisation over block sizes under which blocks can be of unequal size might be an interesting investigation, however, is out of scope for this paper. We will add it as possible future work.

(Presentation - Range of ε\varepsilon and accuracy in Figure 3.) Figure 3 is there to illustrate how close our bound is to a concrete attack and to pin down where the slack arises from. The only quantity that every curve on the plot share is γ\gamma and is hence why we have plotted it as such; the code-book mechanism isn't differentially private and as such has no associated ε\varepsilon. Therefore, we think that adding ε\varepsilon to the plot may end up confusing the reader. We can't add accuracy as the codebook mechanism doesn't train a model and the linear model trained with the DP-SGD mechanism and subsequently attacked isn't a classifier - as detailed in Section G.5 we choose a loss such that the gradient is the input, this loss is just the output of a linear model (with no bias). This should become more immediately apparent with the expanded experiment section.

Reviewer_NAhCOpenReview ↗

Thanks for the response

Thank you for providing a detailed response. I find it to be quite thorough and thoughtful in addressing the concerns that I raised.

I've revised my overall score from 2 to 3.

AuthorsOpenReview ↗

Addressing your review in the revised pdf

Thank you again for your detailed review, and for the revised score. We are glad our response was helpful. We have now uploaded the revised PDF. Here are the changes made in response to your review, under the headings of our response above:

(Presentation - Use of AI.) With the extra page, the details needed to read the experiments are moved from the appendix into Section 6 (see "Figure 3 and the slack decomposition" below).

(Presentation - Trajectory notation.) The shorthand θ\theta is removed; we write θ0:T\theta_{0:T} throughout, including Appendices D and G.6.

(Methodology - Assumption 3.1.) No change; the finite-precision assumption is kept for the reason given in our response.

(Presentation - Δ\Delta.) The fixed spacing is removed from Assumption 3.1.

(Presentation - Line 174.) The two sentences are merged (paragraph after Definition 3.3).

(Presentation - Duplicate definition of νΨ2\nu_\Psi^2.) Removed from Eq. (3); it is now defined once, in Eq. (5).

(Presentation - Removing Ht−1\mathcal{H}_{t-1} on line 315.) Removed from Section 4.

(Presentation - Overloading nn.) The training-set size is ntrainn_{\mathrm{train}} and the estimation-sample size is nestn_{\mathrm{est}} (Sections 3.1 and 5, Appendices E and F). Section 5 and Proposition 5.1 now name the samples DestD_{\mathrm{est}} and D⊥D_\perp.

(Methodology - Data splits and Algorithm 1.) Appendix F.1 has a new paragraph, "Using the bound to inform the experimental design/pipeline", and a new Req 6. It states that no hyperparameter in our experiments is chosen using D⊥D_\perp or DestD_{\mathrm{est}}, and that both must be disjoint from DtrainD_{\mathrm{train}} if the bound is used to choose the schedule. The data-split figure (now Figure 5) has a new panel (c), Table 2 and Appendix F.3 are updated to match. Algorithm 1 is rewritten with explicit inputs and output, for a single run. Multiple runs are covered in Req 2, which says how their leakages add. New Algorithm 2 gives the inverted process: it solves Eq. (14) for the leakage budget in closed form, then finds the smallest σ\sigma that meets it, using the split of Figure 5(c).

(Presentation - Conceptual figures.) The Figure 1 caption now explains the notation. The pipeline diagram is now Figure 4, with a caption, an introductory sentence and a pointer to Algorithm 1.

(Presentation - Figure 3 and the slack decomposition.) Section 6 has three new paragraphs: "The codebook mechanism", "The chain of bounds and attacks" (Eq. 15) and "The remaining curves". Together with the rewritten Figure 3 caption, these define every curve: ρblk\rho_{\mathrm{blk}} (a diagnostic, not a second guarantee; Proposition G.1), the codebook attack, the point estimate, the realizable prior and "inverted to image", and say why ρblk\rho_{\mathrm{blk}} and ρcb\rho_{\mathrm{cb}} stop.

(Methodology - Block orthogonalisation, k∣mk \mid m.) Optimising over blocks of unequal size is added to "Future work" (Section 7). Zero-padding is described in Remark C.1.

(Presentation - Range of ε\varepsilon and accuracy in Figure 3.) Section 6 now states that the codebook mechanism has no ε\varepsilon and that the attacked linear model is not a classifier (check footnote).

Reviewer_ryMkOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper proposes an information-theoretic framework for lower bounds on training data reconstruction of DP-SGD models with a prior-aware adversary that has access to all training data except the target instance. The framework is modular and can handle different measurements of reconstruction success including LPIPS. Experiments show the usefulness of the bounds, and analysis is given when there is slack in the bounds.

Critical strengths
  • The paper is organized well, and the body-text equations, tables, and figures are well-presented.
  • The prior-aware and representation-flexible nature of the framework is important for potential relevance towards real-world attacks.
  • Much experimental detail is given to improve reproducibility.
Critical weaknesses
  • More justification for the experimental attack choice would be useful (see Questions).
  • (minor point) Clarity in the methodological diagrams could use small improvements. (I do not mean for the below suggestions to be overly prescriptive, and the authors are welcome to justify their original decisions, or propose alternatives to the below suggestions.)
    • In the grey box in Figure 1, I suggest making it more clear that the four leftmost options (Pixels, Coarse or partial features, LPIPS, Other representations) are instantiations of the "Representation Ψ\Psi".
    • The "Computing the bound" diagram of the Experiments section could use a sentence introducing the diagram.
Questions for authors
  • Could the authors please share more about why they chose the prior-aware attack of Hayes et al. (2023) for experiments? Are there alternative attacks that would be informative for future work to experiment on with your framework?
  • Could the authors please clarify which parts of their contribution may prove useful/relevant to lower-bounding privacy leakage of defenses outside of DP-SGD? What conditions must a general reconstruction defense meet for a version of this framework to apply?
3 comments

Thank you for your review and identifying areas of improvement in the paper, details on how we will address them are below. We will be providing an updated pdf as soon as possible incorporating all reviewers comments. Once this is done we will update you with pointers to each individual reviewer showing where their comments have resulted in changes to the paper.

(Choice of attack.) The attack's role in this paper is to provide a reference point of what empirically we can show an adversary could recover. Therefore we needed an attacker that (i) uses the whole threat model of Section 3.1 (all other records, the full trajectory, a prior) and (ii) targets the quantity we are bounding (the expected squared error). The candidate-prior attack of Hayes et al. (2023) satisfies both, and is the attack they used to test their own bound. We did some initial exploration of more sophisticated attacks (tailored to also satisfy (i) and (ii)) including diffusion methods (Schwethelm, 2024), however, gains in comparison to the attack we adopted were marginal and by no means consistently better across DP-SGD schedules. We will include a pointer to some more sophisticated attack ideas such as those of (Schwethelm, 2024) that could be compared against our bound in the future work. We adopted and tweaked the candidate-prior attack as it's simple and effective which reduces the chance of faulty implementation and illustrates the main messages of this set of experiments. Thank you for pointing out that we haven't explicitly written out the justification for our choice of attack, we will correct this in the revision.

(Beyond DP-SGD.) To apply our bound to a privacy mechanism other than DP-SGD we need only come up with a bound on I(xi;θ∣X−i)I(x_{i};\theta|X^{-i}). This corresponds to replacing box 1 and 2 (in blue) in Figure 1 with an alternative mechanism and bound on that mechanism's leakage term, I(xi;θ∣X−i)I(x_{i};\theta|X^{-i}). We consider parameters θ\theta but this could equally be replaced for whatever object is being released such as a statistic, embedding, synthetic data, etc. A slight caveat is that the mechanism should treat records symmetrically (permutation invariance), if not then one must keep a separate γi\gamma_i for each record. Where and how this could be applied is an interesting question for future research. We will add a section in the appendix (referred to in the main text) that discusses how one can go about swapping alternative components into the framework.

(Figures.) We agree with both suggestions and will (i) relabel the grey box in Figure 1 so that pixels, coarse/partial features, LPIPS and other representations are shown as instantiations of the representation Ψ\Psi, and (ii) give the "Computing the bound" diagram a number, a caption and an introductory sentence in the text, which Reviewer NAhC also requested.

AuthorsOpenReview ↗

Addressing your review in the revised pdf

We have uploaded the revised PDF. Changes made in response to your review, under the headings of our response above:

(Choice of attack.) The "Attack comparison" paragraph of Section 6 now gives our reasons for using the attack of Hayes et al. (2023). "Future work" in Section 7 points to more sophisticated attacks that could be compared against the bound.

(Beyond DP-SGD.) New Appendix H, "Replacing components of the framework", states what a replacement for each of the four modules must provide. It is referenced from Section 3.1, the Figure 1 caption and Section 7.

(Figures.) In Figure 1 the grey box is now headed "Choices of representation Ψ\Psi" and each option is written as Ψ=…\Psi = \dots, the caption now explains the notation. The "Computing the bound" diagram is now Figure 4, with a caption and an introductory sentence at the start of Section 6.

Thank you for your careful handling of my concerns. I also appreciate your thorough response to Reviewer NAhC who raised many important points I had not considered. I will maintain my positive score.

Reviewer_YEQ3OpenReview ↗
Rating
4(+1)
Confidence
1
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper proposes a modular framework for computing reconstruction bounds to answer the question of how accurately an adversary can reconstruct training samples. The authors use information-theoretic concepts to derive such distortion bounds, separating the information about a record revealed by training and the uncertainty already present in the data distribution. They combine both components, measured through conditional mutual information and source entropy, respectively, to compute a lower bound on the expected error of the reconstruction attacks.

Critical strengths
  • The paper proposes a modular framework where each of the three modules can be replaced independently.
  • The bound can be computed before training as the proposed method does not depend on the architecture or a parameter count.
Critical weaknesses
  • The framework assumes i.i.d. data samples. The numerical experiments in Section 6 however do not necessarily satisfy this assumption. The data in the CelebA dataset for example is non i.i.d. as it contains multiple images of the same faces.
  • The authors additionally only test attacks that are run on a linear model. This is a weaker attack than the threat model in Section 3.1.
Questions for authors

One of the assumptions you make is that samples are i.i.d. For CelebA, however, this is not the case. How do you expect correlated samples to affect the validity of the bound? Could the framework be easily extended such that it covers non-i.i.d. samples?

3 comments

Thank you for reviewing our paper and pointing out some issues that needed more explicit clarification, as discussed below we will address this in our revision. We will be providing an updated pdf as soon as possible incorporating all reviewers comments. Once this is done we will update you with pointers to each individual reviewer showing where their comments have resulted in changes to the paper.

(i.i.d.\ assumption and CelebA). We thank the reviewer for raising this point. The only place where Assumption 3.2 (i.i.d.\ sampling) is used is in the proof of Lemma~3.4 (Section B.1). There we write I(xi;θ,X−i)=I(xi;X−i)+I(xi;θ∣X−i),I(x_i;\theta,X^{-i}) = I(x_i;X^{-i}) + I(x_i;\theta\mid X^{-i}), and use the i.i.d.\ assumption to conclude that $ I(x_i;X^{-i})=0$. If independence does not hold, then the proof can be modified by retaining the additional term I(xi;X−i)I(x_i;X^{-i}). In that case our result becomes a bound in terms of γ+I(xi;X−i),\gamma + I(x_i;X^{-i}), so the effect of dependence is transparent: it contributes an additional information term measuring how much can already be inferred about xix_i from the remaining records. We will add text after Lemma 3.4 making this dependency explicit. Regarding CelebA specifically, we would be cautious about identifying repeated identities with a violation of the i.i.d.\ assumption. The presence of multiple images of the same celebrity does not by itself imply that the samples are not i.i.d. For example, one could model the source distribution PxP_x as a distribution over face images of a list of celebrity identities under which some identities appear more frequently than others; independent draws from such a distribution would naturally produce repeated identities. What matters for Assumption 3.2 is whether the records can be regarded as independent draws from a common distribution PxP_x, not whether two realised samples happen to depict the same individual. That said, the reviewer raises a valid concern: if the dataset construction procedure were to introduce additional dependence between records beyond that implied by an underlying population distribution, then I(xi;X−i)I(x_i;X^{-i}) need not vanish.

(Linear-model attack). The bound is agnostic to the model chosen. Precisely, the model and it’s parameters are only considered when bounding γ\gamma (Theorem 4.1) and the quantity we bound it with only depends on qtq_{t} and σt\sigma_{t}. So for any given qt,σtq_{t}, \sigma_{t} our bound holds no matter the model choice. Therefore to create the best scenario possible for the attacker we choose a model which is easy to attack. In our revision this will be made clear in Section 6 in the main text. We therefore chose a linear model, whose per-example gradient is exactly the input. We discuss this in the 'Model.' paragraph in section G.5. We aren't exactly sure what you mean when you say 'This is a weaker attack than the threat model in Section 3.1.', however, our model makes full use of the threat model detailed in Section 3.1 but goes no further, ie. our attacks don't violate the threat model.

AuthorsOpenReview ↗

Addressing your review in the revised pdf

We have uploaded the revised PDF. Changes made in response to your review, under the headings of our response above:

(i.i.d. assumption and CelebA.) New text directly after Lemma 3.4 (Section 3.1) states that this lemma is the only place Assumption 3.2 enters the derivation of Theorem 3.6, and that for dependent records the results hold with γi\gamma_i replaced by γi+I(xi;X−i)\gamma_i + I(x_i; X^{-i}).

(Linear-model attack.) The "Attack comparison" paragraph of Section 6 now explains why we chose this attack. The bound depends on the model only through γ\gamma, which Theorem 4.1 bounds from the schedule alone, so we attack the model most favourable to the adversary. The full description of the model remains in the "Model" paragraph of Appendix G.5.

Thank you very much for your comments and uploading the revised version of the manuscript. My concerns have been addressed and I will increase the score accordingly.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Revised PDF

Summary of changes in the revised PDF

Thank you all reviewers. The revised PDF is now uploaded, here we document all changes, by location:

Main text

  • Figure 1. Grey box relabelled so each option is shown as a choice of Ψ\Psi; caption now explains the notation. (ryMk: Figures; NAhC: Conceptual figures)
  • Section 3.1. θ0:T\theta_{0:T} used throughout (NAhC: Trajectory notation). Fixed spacing dropped from Assumption 3.1 (NAhC: Δ\Delta). Sentences after Definition 3.3 merged (NAhC: Line 174). Training-set size written ntrainn_{\mathrm{train}} (NAhC: Overloading nn). New text after Lemma 3.4 on dependent records (YEQ3: i.i.d. assumption and CelebA).
  • Section 3.2. νΨ2\nu_\Psi^2 defined once, in Eq. (5). (NAhC: Duplicate definition of νΨ2\nu_\Psi^2)
  • Section 4. Ht−1H_{t-1} removed. (NAhC: Removing Ht−1H_{t-1})
  • Section 5. Samples named DestD_{\mathrm{est}} (size nestn_{\mathrm{est}}) and D⊥D_\perp. (NAhC: Overloading nn; Conceptual figures)
  • Section 6. Pipeline diagram is now Figure 4, with caption and introductory sentence (ryMk: Figures; NAhC: Conceptual figures). "Attack comparison" explains the choice of model (YEQ3: Linear-model attack) and of attack (ryMk: Choice of attack). Three new paragraphs and a rewritten Figure 3 caption explains every curve (NAhC: Figure 3 and the slack decomposition; Range of ε\varepsilon and accuracy in Figure 3; Use of AI).
  • Section 7. Future work mentions blocks of unequal size (NAhC: Block orthogonalisation) and more sophisticated attacks (ryMk: Choice of attack).

Appendix

  • Appendix F. New paragraph and Req 6 on using the bound to choose the schedule; new panel (c) in the data-split figure; Algorithm 1 rewritten; new Algorithm 2. (NAhC: Data splits and Algorithm 1)
  • Appendix H (new). What a replacement for each module must provide. (ryMk: Beyond DP-SGD)

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.