Optimized Tradeoffs for Private Majority Ensembling

We would like to thank the reviewer for providing valuable and detailed feedback. The setting and the problem we consider are formally stated in Problem 1.1. The assumptions for theoretical results presented in section 4 are clearly stated at the beginning of this section, that is, we consider the setting when all mechanisms are i.i.d. under pure differential privacy guarantee.

We would like to thank the reviewer for providing valuable and detailed feedback.

Our results hold for any prior $p_i$. The key motivation in developing the $\text{DaRRM}$ framework is to automatically calibrate the noise added, i.e., the design of our $\gamma$ function, so that the utility can be maximized under the same privacy guarantee, without knowing the underlying distribution of $p_i$'s. We choose the uniform prior distribution of $p_i$ in our experiments to present results in the most general case when one does not have prior knowledge of $p_i$'s. If we have prior knowledge of the $p_i$'s and by incorporating the prior distribution of $p_i$ in the optimization framework, we can get even higher utility with the same privacy guarantee. Computationally, since we approximate the optimization objective (note this does not affect the privacy guarantee) by subsampling $p_i$'s from its distribution, using a different prior of $p_i$ does not slow down the run time.

We added more experiment results in section F.1.3 to compare the error of $\text{DaRRM}_\gamma$ when $\gamma$ is optimized using the objective under

$p_i \sim \text{Uniform}([0, 1])$

as we did before and under another distribution $\mathcal{T} \sim \text{Uniform}([0, 0.3]\cup [0.7, 1])$, which represents one's prior belief that there is a clear majority among the mechanisms. We then compute $\text{DaRRM}_\gamma$'s error in three settings with three different actual $p_i$ distributions: 1. $p_i \sim \text{Uniform}([0, 1])$,$\forall i\in [K]$, 2. $p_i \sim \text{Uniform}([0, 0.1])$, $\forall i\in [K]$, implying a clear majority of 0 among the mechanisms, and 3. $p_i = 0.5, \forall i\in [K]$, implying there is no clear majority.

As one can see from the results, if the prior distribution of $p_i$ is close to the actual distribution, optimizing $\gamma$ under this prior distribution leads to additional utility gain (i.e., less error); while if the prior distribution of $p_i$ is far from the actual distribution, optimizing $\gamma$ under the prior distribution is not as optimal but still better than naive methods. We find that using a uniform prior generally leads to good performance.

Please see the updated draft for more results.

We would like to thank the reviewer for providing valuable and detailed feedback. We have uploaded an updated version the draft to reflect changes to improve the presentation. All modified places in the draft are colored in blue.

$**Response to Weakness. **$

$**Writing.**$

• Point 1 & 2 & 3 See the updated draft.
• Point 4: The $f$ is defined in Lemma 3.3. To make it clearer, we changed $f(...)=$ to be $f(...) :=$.

$**Experiments. **$

In the experiments on private Sign SGD, we fix the total privacy loss of each communication around privacy loss to be $m\epsilon = 0.3$. The total privacy loss for each coordinate in the gradient vector is composed across $T$ iterations, and the resulting total privacy loss across all communication rounds, i.e., the overall $\epsilon$ parameter, is the same for each private majority ensembling technique we use in the experiments. We used two simple CNN models on the two datasets MNIST and CIFAR10 with $28938$ and $9074218$ parameters Hence, the dimension of the gradient vector here is $d = 28938$ on MNIST and $d = 9074218$ on CIFAR10. Since the dimension $d$ for both datasets are different, we think making a plot with x-axis as the # communication rounds is clearer.

You are correct that the total number of composition is gradient dimension $d$ $\times$ # rounds, which can be very large. This is indeed a drawback of private Sign SGD (which guarantees pure DP), compared to the more widely applied DP-SGD (which only comes with approximate DP guarantees), although people use private Sign SGD instead of DP-SGD to combat Byzantine adversaries. Designing Byzantine resilient and private optimization algorithm with good privacy-utility trade-offs is out of the scope of this work, but can be interesting to think about.

We emphasize that we only use the base version of private Sign SGD as an application to demonstrate the usage of our theory and the $\text{DaRRM}$ framework; more advanced versions of Sign SGD with higher utility that exploit sparsity and round skipping will also benefit from our framework. For example, as we have mentioned in the footnote on page 8, to limit the privacy loss, one can apply sparsification techniques to reduce the number of gradient coordinates sent by the clients.

As the reviewer mentioned, our setting and PATE's setting are different and are not directly comparable. PATE aggregates outputs from non-private teachers while we consider private teachers, while our $\text{DaRRM}$ framework does not apply when the teachers are non-private. In our setting, when the teachers are private, the ensembling guarantee of PATE still applies as it relies on the typical sensitivity analysis, yet gives much worse utility guarantee, since it cannot exploit the fact the teachers are private themselves. Therefore, we show that the naive PATE extension is suboptimal but there is no way to extend our algorithms into the original PATE setting, and comparing to ensembling non-private teachers in term of downstream accuracy is outside the scope of our setting. Note that the main goal is to show that the typical sensitivity-based noise injection, via "Laplacian" and "GNMax" which are two subroutines used in PATE, are suboptimal in terms of ensembling utility and can be used as naive baselines for majority ensembling in the experiments.

Thanks for the response!

In your response, you write "we fix the total privacy loss of each communication around privacy loss to be 0.3". However, in your Figure 3's caption, you write "ensuring that each coordinate of the aggregated sign gradient is 0.3-differentially private". So does it mean for each round, the privacy loss is 0.3*d-DP? Then even just 1 round will be more than 8000-DP? I would say such an epsilon is just meaningless. Or you mean each coordinate aggregation is 0.3/d-DP? Given the magnitude of d, it's almost 0-DP and it's hard to believe there will be any utility.

Furthermore, in Appendix, I saw "each client computes its gradient based on the entire local dataset at each communication around", so is the privacy calculation correct in the paper? What does it even mean by "each ensemble itself is $\varepsilon$-DP" in this case? (if the dataset for training different ensemble is different, the naive privacy loss is no longer $m \varepsilon$-DP)

Although I understand that the paper is considering the case that each teacher is already $(\varepsilon, \delta)$-DP, I think it's beneficial to add a comparison with original PATE. If the original PATE significantly outperforms aggregating private teachers, then what is the main motivation for this work? E.g., are there scenarios where we must have differentially private teachers and cannot have non-private teachers?

We would like to thank the reviewer for providing valuable and detailed feedback. We have uploaded an updated version the draft to reflect changes to improve the presentation. All modified places in the draft are colored in blue.

$**Overloading of$\gamma$notations. **$

• We updated Algorithm 1 by introducing a different notation, $p_\gamma$, as the coin-flipping probability.
• In most places in the draft, $\gamma$ is the function $\gamma: \{0,1,\dots,K\} \rightarrow [0, 1]$, except in Lemma 3.2, where we show the generality of $\text{DaRRM}$ holds with an even more general $\gamma: \{0, 1 \}^{K+1} \rightarrow [0, 1]$.
• To make the $\gamma$ notation consistent, we rephrased the optimization problem in Eq.3 so that the variable is now $\gamma \in [0, 1]^{K+1}$, with an additional constraint saying $\gamma$ is symmetric around $\frac{K+1}{2}$.

$**The formulation of Theorem 4.1.**$

• Variables $p_i, p_i'$ are defined in "Notations", which presents all notations used throughout the paper as is stated in this section "throughout the paper, we use ...", in section 2.1 "preliminaries".
• To avoid confusion, we now call $m$ the privacy allowance and have updated this in the draft, including the Appendix. $m\epsilon$ now refers to the usual notion of privacy budget. Just to be clear, $\epsilon$ is never an integer in the context. $m$ does not have to be an integer in our context either. However, the total privacy loss of a subsampling algorithm is an integer multiplier of $\epsilon$ by nature. For a privacy allowance $m \in (i, i+1)$, $i\in \mathbb{N}^{+}$, we can only subsample $i$ items to ensure the privacy loss is within the total budget. Hence, to simplify the presentation, we consider an integer $m$ in the context of the subsampling algorithm, as in Theorem 4.1.
• We have slightly re-structured Theorem 4.1 to make it clearer. See the updated draft.
• The goal is to design $\gamma$ in our proposed $\text{DaRRM}$ framework to solve Problem 1.1. We have updated the theorem statement to make it clearer.

$**Other notation and related issues. **$

• Point 1 & 2, we updated the statement of Lemma 3.1, changing $\mathcal{L} \Rightarrow l$ and $\gamma \Rightarrow \gamma_{Subsampling}$ as suggested.
• $\mathcal{D}$ and $\mathcal{D'}$ are defined as the adjacent datasets in the "notation" section in section 2.1 "preliminaries". We also re-stated that $\mathcal{D}$ and $\mathcal{D'}$ are adjacent datasets in the paragraph right before introducing Lemma 3.3, in the original draft.
• In Lemma 3.3, it is stated "For $\gamma$ that is a symmetric function of the sample sum", which implies "symmetric" meaning $\gamma(l) = \gamma(K-l)$, where $l$ denotes the sample sum, i.e., $\sum_{i=1}^{K} S_i$. To make it clearer, we updated the draft by replacing this sentence with "For $\gamma: \{0,1,\dots,K\}\rightarrow [0, 1]$ such that $\gamma(l) = \gamma(K-l),\forall l,$"

$**Minor language issues. **$

We have corrected those issues in the updated draft.

$**Response to Lemma 3.3 being too optimistic. **$

Lemma 3.3 indeed indicates "if and only if". This is because the statement directly follows the definition of differential privacy and applies only algebraic manipulations. We note that for the "only if" direction, the condition that we assume is that DaRRM is private for any $\epsilon$-private mechanisms; therefore even if favorable conditions on the mechanisms occur, our privacy cost inequality will still hold. We slightly modified and simplified part of the proof of Lemma 3.3 to emphasize both "if" and "only if" directions. See the updated proof in section C.4. Note that the same lemma statement as in Lemma 3.1 followed by its proof was indeed in section C.4 in the Appendix of the original draft, as promised in the main paper. The confusing part might be that we manually numbered all lemmas in the Appendix and there was a mismatch in the lemma numbers (although the title of each section in the Appendix has the correct lemma number). We corrected all lemma numbers in the Appendix.

We have made a pass through the entire draft, including the main paper as well as all theorems/lemmas/proofs in the Appendix. We tried our best to make all theorems/lemmas/proofs as clear and rigorous as possible. Please see the updated draft. Thanks.