- 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 . However, I recommend that the authors avoid using just plain (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 . For the most part, the paper does already avoid using and typically just uses . However, there are some places in the Appendix, where 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, is explicitly mentioned, but then the 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 , 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 () is identical for all , 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 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 (note: 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 is already compact enough and is clearer as it avoids using more notation.
In Section 5, , 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 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 overlapping with part of the train, and all of the validation and test splits? However, this seems problematic as estimates calculated via will seem to affect parameters chosen for training as specified in Algorithm 1 (page 25), i.e., to ultimately set for a given target .
Algorithm 1 also has other issues:
- It specifies as a required input, but then at the last step suggests inverting the calculations of some steps to set to target a given . It seems that this is offered as an alternative, but this procedure should be better clarified.
- Inverting steps 1 and 6 do not seem so obviously straightforward. These should be elaborated upon.
- 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 , 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 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 " 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 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 curve, but aren't these curves extended to higher ? It would be interesting to see if they trend further down to zero or stay closer to the attack curves at higher .
Questions for authors
For the block orthogonalization trick, is divides strictly needed? If 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 " and "codebook") not continue for larger ?
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 considered in Figure 3?
4 comments
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 curves are. The per-block curve is a diagnostic, not a second guarantee. Our bound assigns every block the full leakage . For the codebook mechanism we can compute the leakage that each block actually receives, and is the same bound with in place of (Proposition G.1). It therefore lower-bounds every attack on the codebook mechanism only, and the gap between (which for a given number of bits bounds what an attack can achieve on any mechanism) and 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 quantizes space into cells, and computing 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 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 .
(Methodology - Block orthogonalisation, .) 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, , has no suitable divisor (for example if 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 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 and is hence why we have plotted it as such; the code-book mechanism isn't differentially private and as such has no associated . Therefore, we think that adding 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.
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.
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 is removed; we write 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 - .) 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 .) Removed from Eq. (3); it is now defined once, in Eq. (5).
(Presentation - Removing on line 315.) Removed from Section 4.
(Presentation - Overloading .) The training-set size is and the estimation-sample size is (Sections 3.1 and 5, Appendices E and F). Section 5 and Proposition 5.1 now name the samples and .
(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 or , and that both must be disjoint from 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 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: (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 and stop.
(Methodology - Block orthogonalisation, .) Optimising over blocks of unequal size is added to "Future work" (Section 7). Zero-padding is described in Remark C.1.
(Presentation - Range of and accuracy in Figure 3.) Section 6 now states that the codebook mechanism has no and that the attacked linear model is not a classifier (check footnote).
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 throughout.
(Methodology - Assumption 3.1.) If we were simply to set Ψ=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 Ψ. After applying Ψ the resulting distribution could place positive probability on a set of zero volume in Rm, 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 −∞ (or undefined), so the conditions required by our bound are not met. We must therefore either add dither after applying Ψ, 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 - Δ) As you have correctly identified the fixed spacing Δ is not required. Accordingly, we will drop Δ.
(Presentation - Line 174.) Agreed, the sentences should be merged as suggested and we will implement it.
(Presentation - Duplicate definition of νΨ2.) Agreed, the first instance will be removed.
(Presentation - Removing Ht−1 on line 315.) Agreed, the notation will be removed.
(Presentation - Overloading n.) Agreed, we will amend the paper to use sub-scripted n's which we already use in part of the paper so ntrain is now reserved for the training set and nest for the estimation sample size.
(Methodology - Data splits and Algorithm 1.) First, to be clear, none of our experimental results use Dest 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,σ)). 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:n notation in Section 5 which should be Dest 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).