- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies the problem of privacy admission (i.e. accounting or composition) under the assumption that historical mechanisms may have lost information: only their RDP guarantees for a finite number of orders are visible to the accountant, who makes decision about whether the new mechanism can be admitted while satisfying an overall approximate-DP constraint. The key observation/assumption is that the distribution of the new mechanism can be known in exact, therefore converting it to an RDP guarantee for composition with historical mechanisms under known orders brings unnecessary privacy loss. The paper argues in that this loss can be strict, and proposed a solution based on optimization.
The general concept behind the idea is interesting: that compositions can be more accurate by considering exact distributions instead of potentially loose (R)DP bounds, and the paper has a reasonable theoretical contribution with both algorithm design and separation analysis. However, I find the paper difficult to follow, not merely because it is math-involved, but also due to problems like undefined notation, missing pointers to the appendix, and abstract theorems without sufficient intuition or illustrating examples. Besides, I am also concerned about the realism of the problem setting, and the evaluataion.
Critical strengths
S1. The observation that composition from exact distributions provides more accurate privacy guarantees then composition over loose (R)DP guarantees is interesting and may inspire future research that may be beyond the scope of that the paper considers.
S2. The paper is deeply math-involved in its detailed problem formulation, separation results and algorithm design, so that there is a reasonable technical depth.
Critical weaknesses
W1. I find the paper difficule to follow. As mentioned, this is not merely due to its theoretical flavor. In particular:
W1.1. I suppose Section 3 is for preliminaries. However, many definitions are missing here. For example, the paper does not itself contain a formal definition for RDP except for the bounds mentioned near line 110, which can make it hard for readers who are not very familiar with the literature. Besides, the definition of approximate-DP also do not look standard (although it is correct). Near line 125, superscripts like "ac" or are undefined. "Lebesgue decomposition" was mentioned in Theorem 11 in the appendix, but not here and there is no pointer to it. Similar problems in definitions for , , and (is there a reason for using different characters for and ?). All these makes the presentation difficult to follow, despite a relatively straightforward underlying idea.
W1.2. Line 214 says "Let denote GDP ... The privacy loss of is ...". From my understanding Gaussian DP is a privacy notion (similar to RDP), does it mean is a mechanism that satisfies GDP? Again, no definition for GDP nor pointer to appendix or reference. No formal definition for for RR and .
W1.3. I would suggest providing concrete examples for Theorem 2 to make the paper easier to follow. Currently it only shows that there can be a possible gap. It would be more meaningful to show how large the gap can be under meaningful parameter choices, which also makes the proof more convincing.
W2. While the contribution in algorithm design is meaningful, the problem setting and assumptions require further justification.
W2.1. Is there a concrete example where historical compression can be lossy? The paper justified this in the second paragraph by saying that diverse mechanisms can be applied that provide privacy guarantee unified under RDP, but (1) this does not explain why only a finite number of orders can be kept, since the privacy loss function that accepts as a parameter also requires finite storage; (2) the underlying mechanisms are "different" but not "lost", would considering their exact distributions provide a even better result than what this paper is proposing?
W2.2. The abstract assumes that the new request is fixed independently of past private outputs, thus adaptive composition is forbidden, which narrows the practical usage of the proposed solution.
W2.3. While the paper assumes that historical information can be lost such that only finite orders remain, its assumption in Line 110 is that the Renyi divergence bounds in two directions are stored in separate. This is questionable under the proposed setting: the more realistic assumption is that only the final bound, namely the larger of the two is kept.
W3. Experimental settings are somewhat limited. The evaluation considers orders from 2-8, and focused on accept/reject decisions. Based on the inequality near line 152, it is more reasonable to measure the privacy gain, namely the difference in the tolarated achieved by the naive composition verses the solution proposed. Besides, the paper should also investigate or discuss about whether the privacy gain works on (note that the inequality assumes the same ). It would also be interesting wo see the overhead compared to considering exact distributions for all mechanisms, i.e., the lossless case.
Questions for authors
See W1.1, W1.2, W2.1.
4 comments
Thank you for the feedback. I have checked the revision file, while my concerns have been addressed case-by-case, the writting (i.e. W1) has not improved too much, and the paper still looks LLM-generated in general: theoretical claims without sufficient heuristics or examples, tons of symbols in the main text, tabular display of experiment results without figures... They all make the paper extremely hard to follow (for a human reader), and the revised version keeps a similar writing style. Given that one other reviewer also raised concerns on presentation, I am doubtful about whether the current writing is understandable to a general audience of the conference.
I agree that the underlying idea can be interesting, but the paper should be presented in a more human-readable way for evaluating its contribution in my opinion.
Thank you for your continued engagement and for the constructive feedback. We take your comments on presentation seriously.
We are revising the main text to make it easier to follow, and will upload the new version before the discussion deadline. We would be grateful if you could take another look.
Thank you very much for the time you have spent on our paper, for checking the revision, and for naming what makes it hard to follow. We have uploaded a further revision of the main text, with the passages rewritten for readability shown in blue.
Each main result is now preceded by a worked instance. The Introduction gives a randomized-response example, with the threshold, the historical bound and the two privacy values, before any result is stated. Section 5 computes the same instance before Theorem 2 and displays the two-point law that the multiplied moments allow, and Section 6.1 shows how one quadratic function gives the upper bound before Theorem 3. Section 4 now works in one direction without an index, defines the two values compared with the cap in words, and uses fewer symbols; Section 3 sets the standard definitions as displayed formulas. In Section 7, Figure 1 now shows the two main comparisons, the decisions of the direct and aggregate accountants on identical inputs and the DP-SGD caps that the direct accountant admits while an aggregate law exceeds them, with the exact values moved to Appendix A.
We would be grateful if you could take another look. There is still time before the end of the discussion period, and if any passage remains hard to follow or you have further suggestions, we would be glad to revise it.
Thank you for your detailed review. We appreciate your helpful suggestions.
We have uploaded a revised version, with red margin notes naming the review point each change addresses.
W1.1
The revised Background (Section 3) states approximate DP in its standard form: P(A)≤eεQ(A)+δ for every measurable event and ordered neighboring pair. For α>1, Dα(P∥Q)=logEQ[(dP/dQ)α]/(α−1), so an RDP bound is the moment inequality stored in the receipt. “ac” and “⊥” are the absolutely continuous and singular parts of the request in its Lebesgue decomposition with respect to Q, and hF(t)=supA(PF(A)−tQF(A)) is the request's hockey-stick profile, singular mass included. W and C name the values of two different optimization problems: WF maximizes over compatible histories with the request factor fixed (the class KF), and Cagg over all laws satisfying only the multiplied moments, with KF⊆Aagg. The revision gives these formal definitions in the new Background section (Section 3), defines h, K, W, C and the Lebesgue-decomposition notation where they first appear (Section 4), and points to Theorem 11 in Appendix D.1.
W1.2, W1.3
Gμ is the canonical Gaussian binary experiment (N(μ,1),N(0,1)), the pair that defines μ-GDP. Fa is symmetric RR, whose Q-side likelihood ratio is a with probability 1/(a+1) and 1/a otherwise. The historical slack η means EX2,EX−1≤1+η. The revision defines Gμ and μ-GDP in Section 3 and Fa and η in Section 5 before Theorem 2; the separation proofs are in Appendix D.3.
For example, substitute a=3, η=1/2704 into Theorem 13. At γ=5,
WF(5)≤1/52<1/40<1/26≤Cagg(5).
The cap δ=1/40 separates the decisions, and the difference in privacy values is at least 1/52≃0.0192. The aggregate witness has mass 1/26 at likelihood ratio 6. At this cap its contribution requires γ≥6−26/40=107/20, whereas retention already admits at γ=5, so the epsilon gap is at least log(107/100)≃0.0677. The revision adds this worked example after Theorem 2 (Section 5).
W2.1
A standard case is DP-SGD: Opacus's RDP accountant composes privacy on a fixed default list of 151 orders, and when that RDP vector, rather than the training configuration, is passed to a later accountant, it is exactly our receipt. On (1): what is passed on is a list of numbers at fixed orders, and no fixed finite set of RDP orders is universally future-sufficient, even with exact saved moments (Proposition 1; Appendix C). On (2): when the full historical laws are available, exact-history accounting applies and can be tighter; our accountant serves the case where only the record is passed on. The revised Introduction gives the Opacus example.
W2.2, W2.3
Adaptive requests are covered when they postprocess a fixed request: Proposition 10 (Appendix D.1) covers transcript-dependent requests Fz=Kz∘F⋆ when F⋆ is fixed and the data-independent postprocessing kernels are jointly measurable, and the joint output is then dominated by EH⊗F⋆. For example, the transcript can select additional noise above a fixed Gaussian baseline, and the accountant checks that baseline. The revision states this condition in Section 4.
Keeping only the larger bound also fits the receipt: a single usual (αj,ρj)-RDP bound valid for all ordered neighboring pairs supplies Mj+=Mj−=exp((αj−1)ρj), and Section 4 notes after the receipt definition that separate directional storage is optional. The DP-SGD record below uses this convention.
W3
The gain appears in privacy values as well as in decisions. The example above guarantees a gain of at least 1/52 in δ and at least log(107/100) in ε. On a DP-SGD record on Opacus's default orders (Section 7.3, Table 3), a Gaussian request μ=1/2 receives certified δ bounds of 2.3e-2, 1.0e-3 and 3.8e-6 at ε=1.10, 1.95 and 3.00, while feasible aggregate laws reach 4.8e-2, 2.7e-3 and 1.2e-5. The aggregate accountant there receives all 61 integer orders. On the 30 Table 2 cases, the same-input aggregate comparison gives certified gaps in 16 cases, up to 0.319 versus 0.423.
When full historical laws are available, exact-history accounting can be cheaper and tighter (Section 7.1, Appendices B.5 and B.9): the two-atom history needs two request-profile evaluations, whereas receipt-based accounting must additionally optimize and verify over all compatible histories.
We hope these responses address your concerns, and we would be grateful if you would consider raising your score.