Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper introduces the theoretical framework for a new noise reduction algorithm for probabilistic differential privacy (DP), namely, the Brownian mechanism (BM), and it also compares it empirically with the Laplace noise reduction (LNR) mechanism on empirical risk minimization (ERM) tasks. The privacy loss (random variable) for BM is characterized, a bound on it is given, and two 'privacy boundaries' are derived for it using results from martingale theory. Additionally, LNR, introduced in [Ligett et al., 2017], is extended in this paper to the continuous-time setting (and it is briefly indicated in the appendices how a Skellam noise reduction mechanism can be derived from the present work).
strengths_and_weaknesses: Strengths:

- Quality: The derived results and the empirical assessment are of high quality and highly non-trivial.
- Clarity: The paper is extremely well-written.

More details: The introduction of BM is a natural step after LNR, as Gaussian perturbation is expected to be more private than a Laplace perturbation if one cares about $\ell_2$-sensitivity. Nevertheless, the authors borrow results from martingale theory that make the introduction of BM a nontrivial analogue of LNR. Further, the results are derived in a highly rigorous manner. Also, the extension of LNR to the continuous setting, besides being rigorously derived in a nice way, yields a significant improvement regarding the privacy problem: querying a utility now can only cause a privacy loss comparable to that incurred by the disclosure of the private parameter. Additionally, a union bound in [Ligett et al., 2017] is disposed of, yielding tighter bounds.

=====

Weaknesses: The following are not detrimental weaknesses of the paper, as it is strong as is; rather, they are rooms for improvement.

- The performance comparison between BM and LNR is largely empirical. The main concern here is that it could be that the chosen datasets and tasks fall within a regime where BM outperforms LNR, but that this regime, as far as the present paper is concerned, is unknown. The authors mention in Line 16: "[BM] empirically outperforms existing work on common statistical tasks, ...." Relatedly, in Line 302, the authors write "... we plotted guaranteed (in the case of LNR) or high-probability (in the case of BM) privacy loss on the x-axis against average loss (either logistic or ridge) on the y-axis." In addition, the authors write in Appendix C in Line 579, before proving a utility guarantee for ReducedAboveThreshold, "... instead of plotting the utility guarantee in our experiments in Section 6, we instead plot empirically observed loss/accuracy." In view of these statements, I think the work could be stronger if more aligned comparisons between BM and LNR are presented.

- There are no details about how BM can be incorporated with composition of DP mechanisms; this issue is mentioned only as a limitation in the conclusion of the paper.
questions: - In Line 495, for $X_t^{\pi}$ to be well-defined, one at least should require that each $(\lambda,\omega) \mapsto Y_t^\lambda(\omega)$ is a Borel function.

- What is $T_1$ in Definition 3.1? It looks like it is a pre-specified constant $T_1$ or function $x\mapsto T_1(x)$, and it would be good to add this remark. Then, do we require $T_2(f(x)+B_{T_1(x)})\le T_1$ (or $\le T_1(x)$), in accordance with the $T_n$ specifying a sequence of time functions? Various instances of such initial parts of a trend have to be carefully specified in the paper, e.g., it is imposed that $\eta>0$ in Line 227, yet it is mentioned in Line 238 that $(Z_t)_{t\ge 0}$ (i.e., $\eta=0$) will be used (perhaps one should define $\mathrm{Lap}(0)$ as deterministically $0$).

- The term 'density' is loosely mentioned in Definition 2.1 (e.g., density with respect to which measure?). I recommend slightly modifying how the definition is spelled out.

- The paper has superb presentation, but a few typos should be fixed. 
- - English typos include: "depend [on] the" in Line 101; delete 'the' in Lines 187 and 222; replace ',' with '.' in Line 235; delete 'instead' in Line 570. 
- - Math typos include: need $\mathcal{L}_{1:n}^{\mathrm{Alg}}$ in the last equation after Line 546; $Z(t)$ is used in Line 559, but only defined in Line 593; should probably be $\mathrm{Lap}(\tau,\frac{2\Delta}{\epsilon_n})$ in Line 572; the two equations after Line 586 need to be fixed; 'minus' sign missing in penultimate equation after Line 612; also, the wording of Prop. 4.2 might be revised, as ex-post privacy is prefixed with a pair when first defined.

I also recommend that it be mentioned that Fig. 4 is in the appendix (when mentioned in Line 198); also, a comment by the authors on why the variances shown in Fig. 4 are large might be in order.
limitations: The authors mention briefly in the conclusion that existing composition results for DP are inapplicable for BM, and that noise reduction is concerned only with output perturbation. Although not a hinderance to the quality of the paper, it would have been nice to see some indication on how composition results can potentially be derived for BM.

The authors mention that there are "no negative societal impacts," but it can be argued that privacy mechanism can be misused.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper introduces a Brownian mechanism for private release, in which an analyst (1) generates a sequence of noise values from a Brownian process up until a certain large time point, (2) starting from this large time point, takes steps back until they find a noise value which incurs acceptable utility, and (3) releases the data with noise at the identified time point. Because of the Markov properties of the process, the privacy loss of such mechanism only depends on the final noise value output. The authors show two ways to compute the epsilon-guarantee of the resulting mechanism in terms of ex-post privacy. Next, the authors extend the existing Laplace-based Markov process mechanism to continuous time. In the final part of the theoretical sections of the paper, the authors introduce a ReducedAboveThreshold mechanism for deciding when to stop the Brownian (or another noise reduction) mechanism when the utility has to be computed on private data. In this algorithm, the utility with added Laplace noise is compared against a noisy threshold, with threshold noises coming from a Laplace-based Markov process which is synchronized with the main (e.g., Brownian) process. Finally, the authors conduct two experiments on private release of the logistic regression parameter vector, and ridge regression via covariance perturbation, finding that the Brownian mechanism on average results in lower privacy loss at the same level of utility threshold, and the privacy loss is more consistent.
strengths_and_weaknesses: The paper deals with a useful setting in modern data analysis, in which an analyst might want to adaptively pick the best privacy level subject to accuracy constraints. The paper proposes two tools (Brownian mechanism and ReducedAboveThreshold) which formalize an iterative interactive procedure in which the analyst tries several noise levels before settling with a satisfactory one. Unlike the previous work on Laplace-based process mechanism, the proposed Brownian mechanism is calibrated to L2 sensitivity, thus suitable to multi-dimensional vectors. I believe this is a useful contribution to the field, given that the results are correct (I have not verified the proofs.)

The main issue with the paper is clarity. The notation is obtuse with the generic time functions $T$ which have an unclear definition, stopping functions $N$, privacy boundary functions $\psi$, privacy functions $\mathcal{E}$. It took a lot of time and effort to parse. The intended meaning of some functions only become clear at a much later point after its introduction, such as $T_n$ by line 211. In general, the generality of exposition is a hindrance. Corollary 2.7, if I understand the intention correctly, would be better as two algorithms for two usage scenarios (accuracy-first and privacy-first). Section 3 seems to be disconnected from the rest of the text. It is also not fully clear if the results of the paper cannot be achieved using the tools of fully adaptive composition. In the experimental section, although the results are convincing, it is unclear if the comparison of guaranteed privacy and high-probability privacy is fair, and how exactly is the empirical privacy loss computed.

As ERM is a motivation of the work, it would be interesting to see how the output perturbation with BM compares to objective perturbation at the same accuracy levels.


questions: * How does the proposed mechanism relate to the prior work on fully adaptive composition? Can the results be re-analyzed in the framework of fully adaptive composition?
* In the experiments, are comparisons of guaranteed privacy loss and high-probability loss fair? How is the privacy loss computed in the experiments (using Theorem 3.6?).
* Is the continuous-time extension of Laplace-based Markov process mechanism necessary for Algorithm 1? 
* Is there a reason that the Algorithm 1 settles when finding any noise level within the utility threshold, if it seems that it could proceed to actually do the minimization of privacy loss?
limitations: The limitations are discussed.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: The paper considers the Brownian mechanism, a new noise reduction DP scheme that allows for "stripping off" the noise gradually until the desired accuracy is satisfied. By leveraging the Markovian nature of the Brownian noise, the privacy guarantee of releasing a sequence of queries (with different epsilons) is the same as releasing the least private one. This improves upon using independent noise, where the privacy needs to be accounted for via composition theorem. In addition, compared to the Laplace-based method [LNRWW 2017], the Brownian mechanism gives an $\ell_2$ guarantee and hence is more suitable for FL tasks. Finally, the authors combine the Brownian mechanism with ReducedAboveThreshlod, a generalization of the AboveThreshold method in [Dwork 2014], giving an adaptive (ex-post) privacy guarantee that will be at most twice that of the non-adaptive version.
strengths_and_weaknesses: - Strengths

The paper extends the previous noise reduction technique in [LNRWW 2017] to $\ell_2$ geometry with $(\varepsilon, \delta)$-approximate DP. Having an $\ell_2$ guarantee is always preferable for FL tasks in both theory and practice. In addition, the improved AboveThreshlod method seems to be significant and allows for much tighter privacy accounting.

- Weakness

1. In general, I think the theoretical grounding looks mostly sound. However, I do have a technical question regarding Lemma 3.2 (see the "Question" section). As Lemma 3.2 is the basis of almost all results of this paper, I'd appreciate it and will increase the score accordingly if the authors can clearly clarify it.

2. In my opinion, the presentation can be improved by providing more high-level descriptions of how this work compares with [LNRWW 2017]. In particular, in Section 4, the authors extend the LNR scheme in [LNRWW 2017] to the continuous case; however, I don't think I can fully appreciate why extending LNR to the continuous case is important and what is the advantage of doing so.

3. As the privacy of the Brownian Mechanism is ex-post and is determined by the privacy functions $\mathcal{E}_n$, it seems to be unclear how to set them in practice. It would be good if the authors could briefly discuss it.
questions: 1. As in [LNRWW 2017], Lemma 3.2 builds on the Markov property of the Brownian mechanism. However, as in general, the time functions $T_n$ may depend on the future of the Brownian noise, i.e., $T_n = T_n(f(x), B_{T_{n-1}},...,B_{T_1})$, i am not sure whether the Markovian property still holds. In its proof, the authors claim that by using the strong Markov property of Brownian motion, one can replace the time indices with random ones. I am not sure whether this is correct or not, as to my knowledge strong Markov property only ensures $B_{T+t_1},..., B_{T+t_n}$ being Markov for a stopping time $T$. I think the authors need to include more details in the proof, as Lemma 3.2 is the basis of the Brownian mechanism.

2. The notation of the stopping function $N(x)$ is a little confusing, as it gives a false impression that the stopping time can directly depend on the private data set $x$. However, if my understanding is correct, it could only depend on the prefix of the private release $M_{[1:n-1]}(x)$. The notation of $N(x)$ could be misleading and (incorrectly) suggest that the ReducedAbove threshold is unnecessary since one could directly compare $M_n(x)$ with $f(x)$, which would still be a valid stopping time.

==========
Post rebuttal: the authors' response to Q1 has addressed my main concern, and i have modified my score accordingly.
limitations: Yes, the social impact is properly discussed.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: This paper generalizes and improves the framework Ligett et al. for releasing a private
query subject to accuracy constraints. In this framework, a query is released
with gradually less noise until a desired accuracy constraint is met, and the
privacy cost is the cost of the last output.

They noise the query with a continuous
distribution specified by Brownian motion, allowing the fully-adaptive release
of the query where even the desired epsilon values are allowed to depend
previous outputs. Their Brownian Motion Noise Reduction offers improved 
performance over the Laplace Noise Reduction, the previous state of the art.

Finally, they generalize NoisyAboveThreshold to allow adaptive values of
epsilon. Combined with the previous results, this enables the accuracy
constraints to also depend on the the private database.

strengths_and_weaknesses: + Results allow fully adaptive release of the query (where epsilon are allowed
to vary) and apply to functions with bounded l_2 sensitivity.

+ Brownian motion is simpler, more elegant, and offers improved performance over previous work.

+ The generalization of AboveThreshold allows the accuracy constraint to depend
on the private database and have the same privacy cost as releasing the final
output. This overcomes a major hurdle of previous work in this area, and makes
the accuracy-first framework more practical.

- Some minor writing mistakes, which I will describe.

questions: Definition 3 does not make sense. What does the symbol $\sigma$ mean here? Furthermore,
what precisely is a stopping time with respect to a sequence of mechanism
outputs?

Is it efficient to produce samples from the Brownian motion algorithm or the Laplace
Noise Reduction technique? It would help the paper to describe implementation details.

limitations: Yes - there are no real limitations to this work.
review_title: null

Meta-review: metareview: The reviewers unanimously agreed that the paper is well-motivated and the theoretical results surrounding the proposed Brownian mechanism are interesting. Initial concerns regarding presentation and clarity were assuaged after the authors' responses to the reviews. Overall, the paper is a non-trivial and valuable extension of [Ligget et al., 2017] and should be presented at the conference.
confidence: Certain
Decision: Accept