- Rating
- 1
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 3
Read review
Paper summary
The paper considers the question whether we can characterize the remaining budget in fully adaptive f-DP accounting via a pair of distributions such that all possible choices of mechanisms (possible meaning all mechanisms for which the total trade-off function does not cross a predefined threshold trade-off function) lead to total trade-off function that is above the trade-off function we'd get when we compose the trade-off function determined by the pair . This is a sort of subproblem one encounters when trying to carry out fully adaptive privacy accounting with trade-off functions or with privacy loss distributions and privacy profiles. The answer is negative: only in case of point mass and certain "total-failure probability" mechanisms this is possible. The background for this problem is fully adaptive accounting: Regehr et al. and Long et al. (references in the paper) have recently shown that in general it is not possible to do fully adaptive accounting accurately with so called trade-off functions or privacy loss distributions. It is possible with Rényi DP (Zrnic and Feldman, 2021), and it is an interesting question whether something more accurate is possible since in the non-fully adaptive case we can do more accurate accounting than RDP, via privacy loss distributions.
Critical strengths
- Interesting characterization for this sub problem of fully adaptive DP accounting.
Critical weaknesses
-
The motivation is unclear. Suppose we had a meaningful positive answer: there is a non-trivial class of mechanisms for which we can characterize that remaining budget via single trade-off function or single pair of distributions. What could we do with this characterization? I think we could not somehow 'subtract' the trade-off function from the 'budget trade-off function' as in case of GDP, for example. There is that Torgersen's product theorem given which considers non-adaptive compositions, but I don't see how it could be applied here. This leads me to the next point:
-
I think the setting the paper considers is ultimately non-adaptive. I don't exactly see how the results could be applied in the fully adaptive case.
-
The writing could be improved. I understood the main results of the paper but to be honest, I couldn't really understand some parts like the abstract. Also elsewhere there are sentences like: "Feasibility supplies safety; greatestness supplies completeness." which is I cannot understand.
-
I think one weakness is that the problem has been in some sense already solved by Regehr et al. and Long et al. (references in the paper). They both show that in general it is not possible to do fully adaptive accounting accurately with so called trade-off functions or privacy loss distributions. That suggests that for general-purpose fully adaptive accounting (and for fully adaptive accounting for DP-SGD) that is more accurate than the RDP one the right direction is some sort of approximate accounting. That does not in itself of course exclude accurate fully adaptive accounting in some special cases, but the paper does not seem to identify any such special case.
Questions for authors
- same as above: Suppose we had a meaningful positive answer: there is a non-trivial class of mechanisms for which we can characterize that remaining budget via single trade-off function or single pair of distributions. What could we do with this characterization? We could not somehow 'subtract' the trade-off function from the 'budget trade-off function' as in case of GDP, for example, and operationalize that for fully adaptive accounting, or?
3 comments
Thank you for the reply. Regarding the first point: that semigroup property does hold for the Gaussian mechanism (or GDP mechanisms, when we are carrying out fully adaptive GDP accounting, or other single-parameter family of trade-off functions with ordering), and that can be used for the fully adaptive accounting. However, in the paper, Section 3 considers general mechanisms and the results show impossibility in the general case. I don't see how it could be used for fully adaptive accounting. In particular, I don't see how the equivalence given at the end of page 3 could be used for fully adaptive accounting, since you need to be able to somehow subtract that .
Thank you for the follow-up. The equivalence on page 3 is used by taking as the new cap. Suppose exists for and the next request is chosen after seeing the output of , subject only to . Every such conditional release is then bounded by the same fixed experiment , so the adaptive composition theorem of Dong et al. (2022) bounds the whole interaction by . The accountant can then discard and : the next remaining budget is the residual of the issued at the cap , again a one-step question. Applying the page-3 equivalence to the request shows that this residual coincides with the residual of at , and the same argument, conditional on the first output, covers each later step. The subtraction is therefore the residual map applied repeatedly, and it permits each request to depend on earlier outputs whenever every residual along the way exists. Under GDP this map is the subtraction of squared parameters.
Section 3 concerns general mechanisms, and Theorems 1 and 3 identify when this map is defined: at every cap exactly for erasure-type spends, while Gaussian, Laplace, subsampled Gaussian and randomized-response spends each have caps at which it is undefined. At such a cap the admitted requests have no admitted upper bound, so an accountant that lets the next request depend on earlier outputs has no single experiment to compose against; Regehr et al. (Corollary 4) exhibit an adaptive failure under a Gaussian budget. Our results locate this obstruction already in one step. We will add this paragraph to Section 3 of the final version.
Thank you for your careful review. We appreciate your constructive comments.
We have uploaded a revised version, with red margin notes naming the review point each change addresses.
W1 (motivation), Q1 (use of a positive answer)
An exact one-experiment remaining budget is essentially unavailable, and the revised abstract and introduction state this negative result as the main conclusion. Theorem 1 shows that a spend C has a greatest feasible request at every feasible cap exactly when its privacy loss, whenever finite, takes a single value. This class is of erasure type: one common output, plus outputs that reveal the hypothesis. Gaussian, Laplace, subsampled Gaussian and randomized-response mechanisms lie outside it, so each has a cap B at which no single experiment replaces the pair (C,B) (new Table 1 and the paragraph after Theorem 1).
Where a positive answer exists, it is used by subtraction, as for GDP; the revised Section 6 opens with this use. For a weakly continuous semigroup with finite privacy-loss support, Theorem 4 and Eq. (2) give
Cs⊗R⪯Ct⟺R⪯Ct−s
for every binary request R, including requests outside the family, so Ct−s alone answers every one-step admission question. The same theorem shows that these semigroups have one finite loss value at each time and are erasure semigroups in the self-dual case. Theorem 4 therefore marks the boundary of the negative result, and the revised Section 6 closes with this statement and a worked erasure example.
Torgersen's theorem enters the negative results as the cancellation step. In Section 5, take the cap B=C⊗R2. A greatest feasible R⋆ would satisfy R2⪯R⋆ and C⊗R⋆≃C⊗R2; cancellation gives R⋆≃R2, which contradicts the feasibility of R1⪯R2.
W2 (non-adaptive setting)
The setting is one step with independent composition C⊗R, as the revised introduction states; fully adaptive filtering is the subject of Regehr et al. and Tran et al. One step is where a remaining budget is used: under GDP, after spend G1 against cap G2 the analyst passes on G1 alone, and the next Gaussian request is compared with it without the original pair. Theorem 1 says exactly when this hand-off loses nothing, and Example 1 shows what it loses otherwise. The direct test admits RR(0.70), while the residual G1 allows at most RR(0.6915), a bit error of 30.854% against 30.000% (Table 3), and no feasible residual admits both G1 and RR(0.70) (Table 2). The loss is thus a property of the spend, present for one independent release.
W3 (writing)
The spend C bounds past disclosure and the cap B bounds total disclosure. A request R is admitted when C⊗R⪯B. A remaining budget is one experiment R⋆ such that R is admitted exactly when R⪯R⋆. "Feasibility supplies safety" means that R⋆ is itself admitted, so every request below it is admitted. "Greatestness supplies completeness" means that every admitted request lies below R⋆. The revised Section 3 uses these explicit statements, and the revised abstract and introduction define each term at first use.
W4 (relation to prior work)
For each standard mechanism Theorem 1 gives a definite rule (revised Section 1, after Table 1): keep the pair (C,B), or export a family-restricted or approximate residual, whose loss Example 1 quantifies. Erasure-type spends, and only these, admit an exact residual at every feasible cap.
The negative direction of Theorem 1 uses the supremum construction, the composition criterion (their Theorem 7, our Proposition 2) and the gap mechanism of Regehr et al., whose Corollary 4 establishes failure under some Gaussian budget. The last paragraph of the revised introduction lists three additions.
First, Theorem 1 decides every fixed spend, with an arbitrary privacy-loss law. The criterion asks whether composition with C preserves suprema of requests; for each nonconstant finite-loss law, Appendix D.3 builds two requests whose profiles cross at a point that splits the law, so their supremum is not preserved.
Second, Theorem 3 (Section 5) separates equivalence cancellation from order reflection. For every finite-support spend with several finite loss values, it constructs two bounded, mutually absolutely continuous requests whose profiles cross while their products with the spend are ordered at every threshold; the larger product is a cap with no greatest residual.
Third, Theorem 4 (Section 6) classifies weakly continuous semigroups with finite privacy-loss support at every time.
We hope these responses and the revision address your concerns, and we respectfully invite you to reassess the paper in light of them.