Universal Exact Compression of Differentially Private Mechanisms

We thank Reviewer GP8R for the constructive feedback. We are pleased to hear Reviewer GP8R thought our PPR technique is interesting and the paper is very well-written. Please find our responses to the questions and comments below.

Regarding a more self-contained and accessible version on a special case: In the revised manuscript, we will explain the PPR algorithm using the Gaussian mechanism as an example, which will hopefully make the exposition more accessible.

Regarding the common random sequence: In practice, the common random sequence is generated using a pseudorandom number generator (PRNG) initialized with a seed shared between the client and the server. While this seed must be communicated between the client and the server, and may lead to an increased communication cost, note that the client and the server only ever need to communicate one seed, which will be used to initialize a PRNG that will be used in all subsequent privacy mechanisms and communication tasks. This is similar to running a large-scale randomized simulation program on a computer, where we only need to initialize the random seed once when the simulation starts.

Practically, the client and the server will share the seed when the connection is established as a small overhead, and can use the same PRNG throughout the whole connection. If the client is applying DP mechanisms to transmit a high-dimensional data, or is using DP mechanisms many times, the cost of communicating the seed will only contribute a small fraction of the total communication cost. On the other hand, if the client is only applying DP mechanisms a small number of times on some small data, then the cost of communicating the seed will be dominated by the overhead in TCP/IP handshaking. In any case, the cost of communicating the seed is insignificant.

Regarding running time for larger $\\varepsilon$: We have discussed the running time of case $\\varepsilon = 0.05$ in the paper. We report the running time for some larger values of $\\varepsilon$'s as follows: For $\\varepsilon = 6$ (which is the largest $\\varepsilon$ that is plotted in Figure 1), we can choose $d_{\\mathrm{chunk}}=2$ in the sliced PPR to have an average running time $0.0127$ seconds or choose $d_{\\mathrm{chunk}}=4$ to have an average running time $0.6343$ seconds, where we calculate the running time by averaging over $10000$ trails. For $\\varepsilon = 10$ (as suggested by the reviewer), we can choose $d_{\\mathrm{chunk}}=2$ to have an average running time $0.0128$ seconds or choose $d_{\\mathrm{chunk}}=4$ to have an average running time $0.7301$ seconds. We plot the average running time (over $10000$ trials for each data point) against $\\varepsilon\\in [0.06, 10]$, with $d_{\\mathrm{chunk}}$ fixed to $4$. Please refer to Figure A in the attached pdf file, where we record the mean $T_{chunk}$ and the standard error of the mean. The standard error of the mean is given by $\\sigma_{\\mathrm{mean}} = \\sigma_{\\mathrm{time}} / \\sqrt{n_{\\mathrm{trials}}}$, where $\\sigma_{\\mathrm{time}}$ is the standard deviation of the running time among the $n_{\\mathrm{trials}}=10000$ trials.

Regarding the overhead in the privacy parameter: For $\\varepsilon$-DP, PPR may inflate the privacy budget $\\varepsilon$ by a factor of $2 \\alpha$ as shown in Theorem 4.5 (though we can make it arbitrarily close to $2$). However, if we instead consider $(\\varepsilon, \\delta)$-DP with a small $\\delta$, then Theorem 4.8 shows that the privacy budget $\\varepsilon$ of the compressed mechanism can be arbitrarily close to the $\\varepsilon$ of the original mechanism.

Regarding exponential running time: We agree with the reviewer that we can discuss more about the running time in main sections. We will move the paragraph "the running time complexity (which depends on the number of samples $Z_i$ the algorithm must examine before outputting the index $K$) can be quite high. Since $\\mathbb{E}[\\log K] \\approx I(X;Z)$, $K$ (and hence the running time) is at least exponential in the mutual information $I(X;Z)$" from the limitation section to after Theorem 4.3.

Regarding shared randomness and privacy: All privacy analyses in the paper assumes that the adversary knows both the message $K$ and the shared randomness $(Z_i)_i$. The trade-off between communication cost and privacy are described in Theorem 4.3 and Theorems 4.5-4.8.

Regarding clients using the same shared randomness: It is assumed that each client uses a different independent shared randomness. Otherwise, we can no longer ensure that the privacy-preserving noises at the clients are independent. Nevertheless, as mentioned earlier in this response, the cost of generating these shared randomness is insignificant. We will clarify this in the revised manuscript.

Regarding the argmin in line 166: Since the $T_i$'s are continuous random variables, with probability one, there do not exist two equal values among $\\tilde{T}_i$'s. This will be clarified in the revised manuscript.

Regarding worst-case encoding size: We can apply Markov inequality $\\mathrm{Pr}(\\log K > L) \\le \\mathrm{E}[\\log K] / L$ on the bound in Theorem 4.3 to show that $\\log K$ is most likely small. If the worst-case encoding length must be controlled, i.e., $\\log K \\le L$, we can modify the method to have the encoder output $0$ instead if the $K$ given by PPR exceeds $2^L$. After this modification, the method may not be exact, though the error probability is bounded by $\\mathrm{Pr}(\\log K > L)$, which is small due to Markov inequality and the bound in Theorem 4.3. We will explain this in the revised paper.

We thank Reviewer U6Tv for the constructive and detailed feedback. We are pleased to hear that Reviewer U6Tv appreciate the universality of our proposed method. Please find our responses to the comments below.

Shared randomness and privacy: Whether shared randomness weakens or prevents privacy depends on the design of the mechanism. Indeed, the 1-bit protocol [5] guarantees privacy in the presence of shared randomness. [30] is slightly different since its privacy-utility trade-off depends on computational assumptions, which is not the case for our work (and most related works cited by us). In some other algorithms, shared randomness can be detrimental to privacy, and additional steps or assumptions are needed to alleviate this problem (e.g., [43] requires a trusted aggregator; [46] requires secure aggregation).

Note that our proposed PPR algorithm also requires shared randomness (see Section 4; it will be made clearer in the revised version), though it is designed to ensure privacy even when the adversary can access both the shared randomness and the compressed data. All privacy analyses (Theorems 4.5-4.8) in the paper assume that the adversary knows both the message $K$ and the shared randomness $(Z_i)_i$.

To clarify, using shared randomness is not an advantage or a disadvantage by itself. It only becomes a disadvantage if it harms the privacy, which may happen in dithered quantization schemes (unless with additional steps and/or assumptions [43,46]), but does not happen in [5,30,65] or our PPR algorithm. The purpose of mentioning shared randomness in the introduction and related work section is to highlight the challenges in ensuring privacy in the presence of shared randomness, though we understand that it could give an impression that we are claiming shared randomness to be an advantage of the proposed algorithm, which is not our intention. This will be clarified in the revised version. The advantages of our algorithm are universality, exactness (comparing to [5,30] which are approximate) and communication efficiency.

The presentation of Poisson functional representation: We will have a more detailed explanation of the Poisson functional representation in the revised version.

Advantages of exact simulation: The advantages of exact simulation (refer to the ``Exactness'' paragraph in page 2) are:

1. Exact simulation does not introduce any bias in compression, and hence it guarantees unbiasedness for tasks such as distributed mean estimation (DME).

2. For the Gaussian mechanism for DME, guaranteeing that the resultant local noise of the compression is exactly Gaussian will result in an overall noise that is Gaussian as well. This provides the central DP of the PPR-simulated Gaussian mechanism, in addition to (and with a better $\\varepsilon$ than) the local DP. Otherwise, only a much looser central DP can be provided, since when the local noise is not "summable", one must rely on generic privacy amplification techniques, e.g. shuffling [Erlingsson et al., 2019], which suffers from highly sub-optimal constants and are only meaningful for limited privacy regimes where $\\varepsilon_{local} \\ll 1$, making it less practical for most FL applications.

This highlights an important advantage of exactness. If the goal is only to design a stand-alone privacy mechanism, then we can study the privacy and utility of the mechanism, without studying the output distribution. However, if the output of the mechanism is used for downstream tasks (e.g., for DME, after receiving information from clients, the server sends information about the aggregated mean to data analysts, where central DP is crucial), having an exact characterization of the conditional distribution of the output given the input will allow us to obtain precise (central) privacy and utility guarantees. Otherwise, we must fall back to the worst-case guarantee (for DME, the central DP guarantee can only be the same as the local DP, which is far from optimal), or use a sub-optimal generic privacy amplification technique.

Advantages of PPR under more conservative regimes or with further compression: The y-axis of Figure 1 is in logarithmic scale, which may make the MSE's look closer than they actually are. For example, when $\\varepsilon=1$ and we compress $d=1000$ to $50$ bits, CSGM has an MSE $0.1231$, while PPR has an MSE $0.08173$, giving a 33.61% reduction. For a case with further compression under more conservative $\\varepsilon$, for example, when $\\varepsilon=0.5$ and we compress $d=1000$ to $25$ bits, CSGM has an MSE $0.3877$, while PPR has an MSE $0.3011$, giving a 22.33% reduction. Such reductions are significant, considering that all considered mechanisms are asymptotically close to optimal, so a large improvement compared to an (almost optimal) mechanism is unexpected. We plot the MSE against the compression size (ranging from 25 to 1000 bits) for $\\varepsilon\\in \\{0.25, 0.5, 1.0, 2.0\\}$ in Figure B in the submitted pdf file.

Moreover, we note again that PPR achieves a better trade-off between MSE and central DP than CSGM, while also giving local DP guarantees that CSGM cannot provide. Another advantage of PPR under more conservative regimes (small $\\varepsilon$) is that the trade-off between $\\varepsilon$ and MSE of PPR exactly coincides with the trade-off of the Gaussian mechanism for small $\\varepsilon$, as seen in Figure 1. In contrast, CSGM is close to (but strictly worse than) the Gaussian mechanism. This means that for small $\\varepsilon$, PPR provides compression without any drawback in terms of $\\varepsilon$-MSE trade-off compared to the Gaussian mechanism (which requires an infinite size communication to exactly realize). This advantage is a consequence of exact simulation.

References

[Erlingsson, Úlfar, et al.] ``Amplification by shuffling: From local to central differential privacy via anonymity,'' SODA 2019.

We thank Reviewer VD1w for the constructive feedback. We are pleased to hear that Reviewer VD1w find the idea of viewing the compression of the output of LDP algorithms as channel simulation inspiring, and our technique can serve as a fundamental primitive to DP algorithm designers. Please find our responses to the questions and comments below.

Regarding running time for larger $\\varepsilon$: We have discussed the running time of case $\\varepsilon = 0.05$ in the paper. We report the running time for some larger values of $\\varepsilon$'s as follows: For $\\varepsilon = 6$ (which is the largest $\\varepsilon$ that is plotted in Figure 1 of the original manuscript), we can choose $d_{\\mathrm{chunk}}=2$ in the sliced PPR to have an average running time $0.0127$ seconds or choose $d_{\\mathrm{chunk}}=4$ to have an average running time $0.6343$ seconds, where we calculate the running time by averaging over $10000$ trails; for $\\varepsilon = 10$ (as suggested by the reviewer), we can choose $d_{\\mathrm{chunk}}=2$ to have an average running time $0.0128$ seconds or choose $d_{\\mathrm{chunk}}=4$ to have an average running time $0.7301$ seconds. It shows the running time are acceptable even for large values of $\\varepsilon$.
We plot the average running time (over $10000$ trials for each data point) against the values of $\\varepsilon\\in [0.06, 10]$, with $d_{\\mathrm{chunk}}$ always chosen to be $4$, in Figure A in the submitted pdf file.

Regarding exponential running time: We agree with the reviewer that we can discuss more about the running time in main sections. We will move the paragraph ``the running time complexity (which depends on the number of samples $Z_i$ the algorithm must examine before outputting the index $K$) can be quite high. Since $\\mathbb{E}[\\log K] \\approx I(X;Z)$, $K$ (and hence the running time) is at least exponential in the mutual information $I(X;Z)$'' from the limitation section to after Theorem 4.3.

Regarding privacy guarantee: For $\\varepsilon$-DP, PPR may inflate the privacy budget $\\varepsilon$ by a factor of $2 \\alpha$ as shown in Theorem 4.5 (though we can make it arbitrarily close to $2$). However, if we instead consider $(\\varepsilon, \\delta)$-DP with a small $\\delta$, then Theorem 4.8 shows that the privacy budget $\\varepsilon$ of the compressed mechanism can be arbitrarily close to the $\\varepsilon$ of the original mechanism.

Moreover, we would like to note again that another advantage of our exact simulation scheme is that PPR enables having both local and central DP guarantees at the same time.

We thank Reviewer NbQx for the constructive feedback. We are pleased to hear Reviewer NbQx thought our manuscript is well-organized and easy to follow. Below, we clarify the weakness and address the question pointed out by the reviewer

Regarding small $n$: Firstly, as noted in footnote 6, the restriction $\\varepsilon < 1/\\sqrt{n}$ (which may require a smaller $n$) is due to the simpler privacy accountant [24]. A tighter result that applies to any $n$ can be obtained by considering Rényi DP instead, as discussed in Corollary G.3 in Appendix G.

Moreover, in the context of federated learning or analytics, $n$ refers to the cohort size, which is the number of clients in each round. This cohort size is typically much smaller than the total number of available clients. For example, as observed in [Kairouz et al., 2019], the per-round cohort size in Google's FL application typically ranges from $10^3$ to $10^5$, which is significantly smaller than the number of trainable parameters $d \\in [10^6, 10^9]$ or the number of available users $N \\in [10^6, 10^8]$.

Furthermore, even in the context of traditional, non-FL training with a DP-SGD-type optimizer, $n$ refers to the batch size rather than the total number of samples, where privacy can be amplified via random batching.

Regarding the reason for which Corollary 5.1 does not relate to $n$: Note that Corollary 5.1 (and also PrivUnit) considers local DP instead of central DP (see Definition 4.1). Therefore, the privacy analysis and guarantees do not depend on the total number of clients $n$.

References

[Kairouz et. al, 2019] "Advances and open problems in federated learning."