Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper studies the concurrent composition of interactive differentially private mechanisms. It shows optimal parallel composition properties of approximate DP and RDP.
strengths_and_weaknesses: Strengths: This paper studies an important problem. Currently, interactivity is one of the major obstacles in DP deployment. The previous optimal composition theorems only hold for sequential composition. Studying concurrent composition is timely research.

Weaknesses: Most of the paper is sound to me, however, I have a few concerns.

1. My main concern 1: on page 2, in the setup, the paper describes that ``A first computes a pair ... sends a query x_1 to M_{i_1} and gets the response.'', which is only one case in the interactive setting. The algorithm can send the first message to adversary A as well. The proof technique for the two cases might be different. For example, it claims that ``Again, we modify A to a new mechanism A' first queries RR...'' on page 5, which is only for one case.

2. My main concern 2: I'm not sure if Corollary 1 is immediate from Theorem 2, since zCDP allows for varying \alpha in the Renyi divergence. I don't see how the proof can be directly generalized here. This paper needs to justify this claim.

3. In the proof of RDP, the proof assumes the order of the messages, which needs justification. The order lemma in [VW21] only holds for approximate DP but not RDP, although I'm convinced it's true (still, there should be a lemma to prove this before using this fact.)
questions: See the weaknesses.
limitations: Yes.
review_title: null

final_score: rating: 3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed ethical considerations.
review_content: summary: The paper, as the title suggests, studies optimal composition theorems for interactive differential privacy, following the framework of [Vadhan and Wang 2021] and resolving one of the open questions in that paper.

strengths_and_weaknesses: I like the simplified definitions of interactive system and concurrent composition, compared to [Vadhan and Wang 2021].

questions: See below
limitations: Unfortunately, I still find the paper missing an important piece, which is an explicit example illustrating how concurrent composition offers more than the existing framework ([Mironov, 2017] and [Dong et al., 2022]. Are there algorithms that previous works cannot analyze tightly or previous analysis is wrong/faulty? I also couldn't find anything helpful in [Vadhan and Wang 2021].

The framework seems novel indeed. However, if I were to do it, I would break each "system" $M_i$ into smaller pieces. Namely, as in Definition 1, each $M_i$ is a randomized mapping $Y^*\to Y$ and hence can be decomposed into a sequence of traditional mechanisms: $M_{ij}:Y^j\to Y,j=0,1,2,\ldots$. If each of these $M_{ij}$ is private, then one can compose using the existing results even when they interleave (say the adversary decides to use $M_{i_t,t}$ after observing $t$ outcomes). What does interactive DP offer exactly? I would like to see an explicit playground where this question can be answered clearly.
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: This work studies the problem of concurrent composition for differential privacy. The authors provide formal proofs for differential privacy guarantees for parallel composition for different notions of differential privacy. First, they extend the results by Vadhan and Wang [2021] on concurrent compositions with pure differential privacy, then they extended those results to also include other privacy notions such as Renyi DP and zero-concentrated DP.
strengths_and_weaknesses: The paper studies a significant problem, and the results are original. Extending the results for sequential composition theorems to concurrent theorems is an important step towards better understanding privacy. This work is interesting towards at least some audience.

The paper is well written and clear, however, some issues need to be clarified. The paper needs some proofreading still, but next are some examples of things to double check:

-The distinction between mechanisms and systems is mentioned in section 1.1, however, in laters parts of the paper, it seems that those are used interchangeably. For instance, on page 2, "Suppose $M_1,M_2,\cdots, M_k$ are $k$ systems." As from the definition above, should those be mechanisms instead?

- In section 1.2, "that $IT(A: M_1^0,\cdots,M_k^0)$ and $IT(A: M_1^0,\cdots,M_k^0)$, shouldn't the second one have superscript $1$?

questions: If possible, it would be nice to discuss how the adversary can use the query history to gain more information from the current query.
limitations: The authors discuss the limitations of the work, where possible future directions and extensions are 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 deals with exploring the “cost” of a concurrent composition of *interactive* DP mechanisms, compared to the (standard) non-interactive case.
 
The well-known composition theorems for DP mechanisms only hold when the mechanisms are non-interactive.
However, not all known mechanisms are non-interactive. The best example is the Sparse-Vector Technique, which is a very popular interactive mechanism, where the adversary in each round can (adaptively) choose a new query.
A natural question that arises is whether we can generalize the well-known composition theorems for non-interactive mechanisms to the interactive case in which several mechanisms can be executed concurrently (or alternatively, does it matter if we compose them sequentially or concurrently in terms of the obtained privacy guarantee?)
 
It is important to note that in other settings, the answer to similar results is not always positive. For instance, in the context of interactive proof systems, it is well-known that parallel-repetition does not increase soundness as sequential repetitions for 2-prover (and multi-prover) games and for interactive arguments (aka, computationally sound proofs).
 
However, in the context of interactive DP mechanisms, the situation seems more positive.
 
Vadhan and Wang 21 initiate the study of concurrent composition of interactive mechanisms. They showed that composing pure DP interactive mechanisms has the same cost as composing non-interactive mechanisms. However, for approximate DP mechanisms (i.e., with a parameter $\delta>0$), they only provided a very basic (and wasteful) composition theorem.
 
This work makes two major steps towards a positive answer: First, they extend the tight technique of Vadhan and Wang 2021 in the pure DP case for the approximate DP case, yielding that the cost of concurrent composition of approximate DP interactive mechanisms is the same as in the non-interactive case. Second, they provide a similar result (using a different technique) for Renyi DP, which in particular implies such results for other popular notions of privacy like zCDP and tCDP. 

strengths_and_weaknesses: Strengths:
1) The results are important and impressive.
2) The proof techniques of both cases (DP and Renyi-DP) are interesting.
3) Overall, the paper is well-organized, and looks sound - All proofs are provided in the supplementary material. I read the full proof for the DP case and I didn’t find something false (There were a few things that I didn’t understand, see my questions below).

Weaknesses:
1) I find the two different proof techniques for $(\varepsilon,\delta)$-DP and Renyi-DP as a disadvantage rather than an advantage. It is unclear to me if there is something inherently different between the privacy loss measures in this context of sequential vs concurrent composition.
2) While the authors did an effort to give an intuition for the proof in the Renyi-DP case, I still couldn’t understand the idea behind all the calculations.
3) There are many typos and other minor issues in the writing (see examples in the next paragraph).

Overall, I think the strengths of this paper are more significant than its weaknesses, so I recommend accepting it.

questions: High-Level Questions:
1) I’m wondering if each privacy loss measure (e.g., $(\varepsilon,\delta)$-DP, Renyi-DP, f-DP) requires a unique and tailored proof technique, or if one can find more general high-level arguments for showing equivalences between sequential and concurrent composition of interactive mechanisms.
Can you explain (in high level) why the proof technique for $(\varepsilon,\delta)$-DP does not hold for Renyi-DP (and vice versa)? 
2) What about other approximate notions of differential privacy, i.e., approximate zCDP which is also very useful. Can you provide tight composition theorems for it by somehow combining your two results?


Technical Question:
1) In the supplementary material, lines 548-551, there are four cases, and you claim that “It is easy to see that if none of the above happens, we can keep increasing $tE^{0/1}$ “. Can you elaborate? E.g., what happens if $tE^0$ is tight at $y_{t+1}$ but $tE^1$ is not? Why $Gap_1$ must be zero in that case?

Minor issues/typos:
1) Line 16: [Dwork et al. 2016] ->  [Dwork et al. 2006]
2) Line 20: A remains -> M remains
3) Line 90: $(\alpha,\varepsilon)$ -> $(\varepsilon,\delta)$
4) I suggest to write $(\varepsilon,\delta)$-DP instead of writing $(\varepsilon,\delta)$-approximate DP all the time. This is very standard. You can mention it in Definition 2.
5) Line 180: $IT(N^b:A)$ should be $IT(A:N^b)$ (be consistent).
6) Line 213, the right term: missing $\in S$ in both terms.
7) Paragraph 216-223: Presents a different proof technique than what is written in the supplementary material. 
8) “The bound for $D_{\alpha}(P||Q)$” -> “The bound for $D_{\alpha}(Q||P)$”
9) Line 324: $Z_T$ -> $z_T$

Minor issues/typos in the supplementary material:
1) Equation 18 (and other places): What is the difference between $E^b$ and $\mathcal{E}^b$?
2) Line 493: the -> then
3) Line 497: contron -> control
4) Equation 21: Why don’t you use the notation of $M^b((y_i),(x_i))$?
5) Equation 22 and many other places: Write max{*} instead of max(*) to make it more readable. 
6) Equation after line 513: No second term in the max.
7) I suggest replacing $tE$ with $\tilde{E}$.
8) Line 598: $B_1,\ldots,B$ $->$ $B_1,\ldots,B_k$.
9) Equation after line 603, right term: $M_1^b -> M_{1,j}^b$ and  $M_k^b -> M_{k,j}^b$.

limitations: In the “Conclusion and Future Directions” section (section 4), the authors address the limitations of their results.
review_title: null

Meta-review: metareview: The paper proposes proves optimal parallel composition theorems for major notions of differential privacy (approximate DP, Renyi DP, and zero-concentrated DP). We believe that this is an interesting theoretical contribution to the DP literature. We encourage the authors to incorporate the comments from the reviewers to make it more interesting for the ML audience.
confidence: Certain
Decision: Accept