Summary
This paper presents extensive background on ex-post-privacy as well as some new analysis providing a new method for leveraging this framework for the design of differentially private interactive protocols. Finally, this framework is instantiated in a method for releasing private counts while targeting an accuracy constraint.
Strengths
* The theoretical framework presented is quite general and seems to be very strong.
* Though relaxed notions of privacy are used internally in mechanism design, the main results here are stated for more tradition $(\epsilon, \delta)$ DP.
* The power of the theoretical framework _could_ conceviably lead to quite substantial concrete implementations and applications.
Weaknesses
* The generality of the analysis yields an associated weakness: for the vast majority of the main body, the precise methods of application are somewhat unclear. E.g. it is not obvious until the end of the paper that we will not literally be guaranteeing that all of our released values are withing percent, which makes the design of interactive protocols which use this style of mechanism + composition an important and more or less unstated problem space.
* The point above can be restated in more direct terms: if the authors wish to see this analysis and framework have a big impact, it is probably still to much of a lift to ask the community to fill in the gaps between the abstract presentation which dominates here and concrete algorithmic implementations.
Questions
* IIUC, the final guarantee claimed here is epsilon, delta DP. Is this correct? If so, I think the paper could benefit from a stronger statement of this much earlier. E.g. the abstract uses ‘differentially private’ and ‘ex post private’, but the statement about an overall guarantee just uses the word ‘privacy’. This leaves a reader somewhat confused about which notion of privacy applies here.
* In theorem 3, what _exactly_ do we mean by statistic and its sensitivity? IE, a Brownian motion itself has no data-dependence, but a Brownian noise reduction mechanism does. Is the notion of statistic and sensitivity we are using here something like: the Brownian noise-reduction mechanism is data-dependent, so its path is data-dependent, and the statistic is a function of the path--so for every neighboring $x, x'$, the function $f_i$ of these different paths can differ by no more than 1, _uniformly_ over the randomness in the BM? This would seem to me to be a somewhat different notion than that of usual sensitivity, where there is no randomness involved. Perhaps the term 'statistic' is intended to imply that the randomness has already been integrated out? But if so, what does this mean precisely (e.g. what would an example be)? Further, it seems like the result of Theorem 3 is independent of these statistics $f_i$, unless they are hiding in the stopping times $T_i$ somewhere? NOTE: it is possible that this $f_i$ is intended to recall $f$ of definition 4.4; but if so, I am not quite grokking this relationship--since the $f$ in definition 4.4 can, I guess, be viewed as one _particular_ statistic of the function $BM(x)$ (the limit of the expectation of the second toordinate as $t \to 0$), but doesn't really provide any immediate pointers to generalizing this notion?
* It's not necessarily clear from the presentation of the paper what relationship there is between ex-post mechanisms, noise-reduction mechanisms, and the Brownian noise reduction mechanism. Meaning, e.g. the statement in definition 4.2 seems to apply to the privacy loss random variable directly, considered as a function of both its inputs and its randomness--at least, this is how I interpret the equality in definition 2, equality of functions. If this is true, seemingly this definition would be applicable to any particular property of the functions $L$; e.g. if $\cal{L}^{(k)}$ was $(\epsilon, \delta)$-DP then $\cal{L}^{(1:k)}$ would be as well (since it is just a statement about the function $L$, and these functions are equal). But thinking about the domains and ranges, it seems like these functions take values in different spaces. So it's not clear, I suppose, what this equality means? Maybe there is a suppressed relationship to ex-post privacy?
* If I read correctly the definition of $(\cal{E}, \delta, \epsilon^*)$ ex-post-private (internal to definition 2) is equivalent to $(\epsilon^*, \delta)$ DP. Is this correct? If so, readers may find it useful to have this explicitly called out, since likely many are more familiar with DP than ex-post privacy.
* Nit on eqn (4): IIUC, choosing the particular functional form here (e.g. $\frac{1}{2 t_n^{(kn)}}$) doesn't necessarily play an enormous role--we could likely choose some 'other way' of determining how much 'budget is left' and push the same choice into Lemma 5.2 (and Theorem 4). Is this correct, or is there something fundamental about the way this function is expressed? If there is nothing fundamental, I would advocate as a reader to abstract over this function, and clarify what properties are 'actually' needed here.
* Nit on conclusion of Thm 4. Can this be stated as a zCDP guarantee? Or are we doing something _specific_ that forces us to go to $(\epsilon, \delta)$-DP?
Rating
6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
Limitations
The major unaddressed limitation is the potential difficulty of designing effective algorithms which leverage this perspective and analysis. That is, it is not entirely clear how fruitful the analysis presented here will be. This paper _could_ be _extremely_ strong with some reasonable extensions, perhaps as a theory paper with associated 'mechanism design paper' that provides many instantiations of this theoretical framework to perform various privacy sensitive tasks. For this reason, the paper reads as somewhat borderline to me--potentially pointing the way to serious applications, but not quite closing the gap entirely yet.
Negative social impacts not immediately applicable.