Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper studies the problem of bounding the privacy loss of the sub-sampled shuffle model, motivated by the real-world application of federated learning with differential privacy.

The broad type of mechanism studied in this paper is as follows:\
Setup:
- Consider dataset $(d_1, \ldots, d_n)$ where client #$i$ has the datapoint $d_i \in \mathcal{X}$.
- Consider any $\epsilon_0$-locally differentially private mechanism $\mathcal{R} : \mathcal{X} \to [B]$.

(One round of) the mechanism is as follows:
- $k$ out of $n$ clients are chosen. Each chosen client $i$ send $\mathcal{R}(d_i)$ to the _shuffler_.
- The shuffler randomly permutes the received responses from the $k$ chosen clients and sends it to a central server, which can post-process the same in an arbitrary manner.

The goal is to know, for any given $\delta$, what is the smallest $\epsilon$ for which the above mechanism is $(\epsilon, \delta)$-differentially private (DP) : this $\epsilon$ can depend on $\epsilon_0$, $k$, $n$ and $\delta$.

One approach for analyzing the privacy loss is to compose (in some way) the privacy loss guarantees of each of the two steps : sub-sampling and shuffling. One such way is to compose the Renyi differential privacy guarantees of the two steps (since Renyi-DP usually gives better bounds than the standard "advanced composition"). This paper instead takes a direct approach to bounding the Renyi-DP loss, and also demonstrates empirically that doing so, does better than performing any kind of composition of the two steps.

The paper uses the recently introduced technique of _ternary-$|\chi|^{\alpha}$-differential-privacy_ to prove the theorems.
main_review: The problem studied in this paper is practically very relevant and timely, as federated algorithms are being deployed in practice at a massive scale and privacy is a mounting concern. The shuffle model is emerging as an important middle ground between the central and local models of differential privacy.\
It is important to have as tight a guarantee on the privacy parameters as possible, so as to have good utility while preserving privacy. Even constant factor improvements in estimating the privacy loss can be practically relevant.

The main contribution in the paper is the direct analysis of the privacy loss in the subsampled shuffle model. The main technique used is the ternary $|\chi|^{\alpha}$-DP that was introduced in a recent work of [Wang et al. 2019].

This direct analysis is empirically shown to yield better bounds than composing the privacy guarantees that have been obtained previously for sub-sampling and for shuffling separately (different kinds of compositions are considered, and the bound proved in this paper is significantly better than these). Moreover, the paper also proves a lower bound on the Renyi-DP loss of the sub-sampled shuffled mechanism : this is also useful to know in practice.

#### Significance and originality:

While the direct analysis in the paper is technically challenging and involved, I feel it is somewhat incremental over the prior work of [Wang et al. 2019].\
However, the improved bounds could be highly impactful in practice.

#### Quality of the paper:

The paper is well-written overall, and contributions are clearly stated.\
While I did not carefully verify all the proof details, they make sense at a high level.

#### Minor Typo:

- Page 3 (Defn 1). Since this definition is for a fixed $\lambda$, I think $(\lambda, \epsilon(\lambda))$ should be simply $(\lambda, \epsilon)$.
limitations_and_societal_impact: The paper raises good points about the potential negative societal impacts of this work: namely that private learning is inherently at odds with checkability of fairness criteria (since the data is private, it can be hard to directly check whether the data was biased or not). It also points out that a small subset of adversarial users could contribute malicious data to the learning algorithm, thereby leading to unfavorably learnt models.

These issues are not specific to the results in this paper, but are broadly applicable to learning with differential privacy.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The paper studies discrete randomization mechanism in the subsampled Renyi DP model. They give a bound on the RDP of the subsampled shuffle mechanism and also give a lower bound. 
main_review: The biggest positive of the paper is the upper bound on subsampled renyi DP. The bound is concrete and can be implemented in practice to account for the privacy loss in the real world when we use shuffle DP. I verified the proof and it is correct to the best of my understanding. 

I will next point out the cons against the paper. 
1. The paper studies pure LDP mechanism whose range is a discrete set while one of the applications of the paper is SGD. The loss function in the SGD has the range over the real. This is a discrepancy which I do not understand. For example, for p=2, the mechanism of DJW samples a uniform point in the \ell_2 ball in the direction of the gradient with probability e^eps/(1+e^eps). This would always yield a point whose coordinates are real. 
2. The proof technique in the paper is almost identical to that by Girgis et al. "On the Renyi Differential Privacy of the Shuffle Model." The only difference is that the reduction to the special case where they have to consider three databases of special form. This has to do with the proof technique introduced in Balle et al. analytic moment paper for subsampled RDP (BKW19). Even the observation that the randomization in the shuffle model can be seen as a weighted convolution of two probability distributions was made in FMT20. I fail to see what it new in this paper. I would appreciate if the authors can point exactly what is new in the paper or whether it is just the adaption of Girgis et al. to BKW19 and FMT20. 
3. Since the expectation is not always on a single distribution, I would suggest the authors to make it explicit. For example, when they prove the joint convexity of ternary divergence, what is the expectation over in each of the term? Is it over R_a, R_0 and R_1, respectively? Then I believe you need to use Jensen, the joint convexity of bivariate function, and Fubini. 

Finally comparing the result with the Girgis et al.'s main result, setting gamma=1 in Theorem 1 does not yield Theorem 1 in Girgis et al. As a result, there is a big discontinuity near 1 when we map RDP guarantee with subsampling rate. 

Unless these concerns are not addressed explicitly, I am afraid the paper is a clear reject for me. I am currently keeping the score high enough in an optimistic hope that the authors address it clearly and concisely giving me reasons to increase my score. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper follows the line of research aiming at tightening the privacy analysis of existing differentially private learning schemes. The authors consider the distributed learning framework, where a group of clients collaborate within a parameter-server architecture to learn a joint ML model under privacy (against the server). In this context, the paper analyzes the differential privacy guarantees obtained by  combining (i) subsampling of the clients (ii) local randomization at the client level and (iii) shuffling clients’ responses before sending them to the server. The authors provide new (upper and lower) bounds on the privacy guarantee of the above scheme for discrete local randomizers.  To do so, they rely on some well-known result from differential privacy (especially Renyi differential privacy), but also devise some interesting new proof schemes. The numerical comparison with existing works show that in some parameter regimes, the proposed bound considerably improves existing bounds studying the same framework.  
main_review: Relevance: The problem of tightening the privacy analysis of the distributed learning paradigm is an active and important line of research that is perfectly suited to a major ML conference like NeurIPS.

Clarity: The paper is overall clear and well written. I like that the authors provided sketch of proof and discussions on their results while presenting them (i.e., in the main body of the paper). 

Quality: I did not have the time to go over all details of the proofs (hence my low confidence), but from my level of reading, both the technical and empirical contents look sound.  I just list below a couple of questions to the authors. 
- The problem formulation (line 139) considers only one data point per user, which is quite restrictive. The authors briefly explained in the limitations paragraph (line 90) that it might not be trivial to generalize their results to arbitrary numbers of data points per user, and claim that their results are close ‘in spirit’ to uniform sampling. However it is unclear to me if the present results are simple to generalize even in the uniform sampling case. Could the authors clarify this point for me? 
- Numerical results presented in Figure 2 and 3 presents some considerable improvements in the privacy/accuracy trade-off compared to previous works in certain parameter regimes. However in some other cases (e.g., in the extreme privacy/ low accuracy regime on the left of Figure 3), the comparison seems at the disadvantage of the new technique. Do the authors have some (theoretical or empirical) insight on what parameter regimes are the best suited to their analysis? 

Originality: I think that the paper is not very original, but its theoretical contribution seems sufficiently significant to me. I think the authors provided an analysis of the subsampled + shuffle framework by making a good use of previously known results and by devising new proof schemes when needed. In particular, I believe that the reduction in Section 6 could be of independent interest in future works.
limitations_and_societal_impact: I believe the authors adequately addressed both the limitations and social impact of their work.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The focus of the paper is on Rényi differential privacy (RDP) in the shuffle model of DP. The main result in the paper is to introduce (at least somewhat loose) upper and lower RDP bounds for an arbitrary subsampled discrete mechanisms in the shuffle model. I think this is a novel, if fairly limited contribution.
main_review: -- after rebuttals & discussion:
I still think this is a borderline paper and I therefore keep my score unchanged. I agree with the authors that the proofs have some novelty, but the paper also has some clear weaknesses (mainly the close relationship with the existing arXiv paper, looseness of the bounds, and the gap between the upper and the lower bound).
--

The authors consider privacy accounting of arbitrary discrete mechanisms with subsampling in the shuffle model of DP, a recently introduced distributed setting assuming a trusted shuffler besides the dataholders and the analyst or central server. As the main results of the paper, the authors introduce an upper and a lower bound for RDP. The bounds are not tight, and there is a significant gap between the bounds. However, the upper bound does improve on the existing methods.

The main reservations I have about this paper is that it seems almost as a small slice cut off from the more extensive paper on archive (and cited in the current paper, Girgis et al. 2021: On the renyi differential privacy of the shuffle model), and the contribution in this paper alone seems limited. Without properly checking the proofs, it also seems like they are mostly simple modifications on the existing proofs of the arXiv paper, combined with some techniques from an earlier subsampled RDP paper (Wang et al. Subsampled Rényi Differential Privacy and Analytical Moments Accountant).

All in all, the paper does make some clear improvement on the current methods, but it seems to be fairly limited in scope.

Questions/comments for the authors:
1) Since most of the proofs follow closely (sometimes almost verbatim) the proofs of the arXiv paper, I think this needs to be stated clearly also in the main paper for each Thm (currently this is mentioned in the Supplement).

Minor comments
* Add bibliography to the Supplement as the citation numbers differ from the main text.
* You could add a paragraph on alternative approaches to privacy accounting (maybe in the extended related work?) to dispel the idea that RDP is the only possible approach (compare e.g. privacy loss distributions or Gaussian DP). However, since these haven't been used in the shuffle model (as far as I know), I do not think this needs to be too extensive.
* Fix the spelling of Rényi, pretty please.
limitations_and_societal_impact: The limiting assumptions are stated clearly-enough. I do not think this paper needs to specifically discuss societal impact.
review_title: null

Meta-review: There is a consensus that the paper provides an interesting theoretical contribution to an important and timely problem, the shuffle model being an actively studied model of privacy that is also increasingly studied in federated learning (FL).

The authors' result on analyzing the privacy loss in the subsampled shuffle model and the accompanying empirical evaluation are valuable contributions towards tightening the privacy/utility trade-offs of DP-SGD in a natural FL setting.

However, there is also a consensus that the paper has a somewhat limited technical novelty, with proofs very similar to ones in recent work. Also, some concerns are raised regarding the remaining gap between the obtained lower and upper bounds.

That said, the reviewers are in agreement in leaning towards acceptance.
Decision: Accept (Poster)