Response to Reviewer Mzdj's follow-up comment
Dear Reviewer Mzdj,
Thanks for your further comment. It is indeed not easy to interpret the privacy guarantee in terms of $f$-DP, and we would like to further clarify from the following different aspects.
**In terms of type II error rate**: Note that as we mentioned in our global response, for the examined scenario in Fig. 4 of the manuscript, compared to SQKR, the proposed ternary compressor increases the type II error rate (which measures the probability that the attacker makes a wrong guess about the true data in hypothesis testing) from $f(\alpha) = 0.068$ to $f(\alpha) = 0.484$ (when $\alpha=0.5$ and $\epsilon = 2$).
**In terms of $\epsilon$-DP given the same MSE and communication cost**: As we discussed in our global response, given the same MSE and communication cost as that of SQKR with $\epsilon_{SQKR} = \\{1,2,5\\}$, the proposed ternary compressor yields approximately $\epsilon_{ternary} = \\{0.05,0.2,3.9\\}$. Note that by definition, for differentially private mechanisms $M$ and all neighboring datasets $D_{1}$ and $D_2$, $e^{\epsilon} = \max_{S}\frac{P(M(D_{1}) \in S)}{P(M(D_{2}) \in S)}$, in which $S$ is the subset of the image of $M$. In this sense, $e^{\epsilon}$ measures the ratio of probabilities that the attacker observing $S$ given neighboring datasets $D_{1}$ and $D_2$. A smaller ratio implies that it is more difficult for the attacker to distinguish $D_{1}$ and $D_{2}$. As an example, improving from $\epsilon_{SQKR} = 5$ to $\epsilon_{ternary} = 3.9$ means that this ratio of probabilities decreases by a factor of $e^{5-3.9} \approx 3$.
**In terms of MSE given the same $\epsilon$ and communication cost**: Recall that the MSE of SQKR is proportional to $var = \frac{1}{k}(\frac{e^{\epsilon}+2^{k}-1}{e^{\epsilon}-1})^{2}$ (here we only keep the terms that are related to the communication cost and the privacy requirement $\epsilon$ for ease of discussion), and $\epsilon_{SQKR} = 5$ corresponds to $var = 6.31$ (let $k =10$). We note that for the same $var = 6.31$, the ternary compressor yields $\epsilon_{ternary} = 3.9$.
We can also readily examine the MSE of SQKR when it attains $\epsilon_{SQKR} = 3.9$ (i.e., the same privacy as that of the ternary compressor with $var = 6.31$), which gives $var = 49.08$. This means that to achieve the privacy guarantee of $\epsilon_{SQKR} = 3.9$, SQKR yields an MSE that is $49.08/6.31 \approx 6.35$ times that of the proposed ternary compressor.
Overall, we believe that such an improvement is not small.
**In terms of the improvement in communication efficiency given the same privacy and utility**: Since we use different measures of differential privacy from SQKR, directly comparing the ternary compressor with SQKR is difficult in this case. Therefore, we adopt the classic Gaussian mechanism (which is order-optimal in terms of privacy-utility tradeoff) as the baseline in the right figure in Fig. 4 of the manuscript. Our results imply that the privacy-utility tradeoff of the proposed ternary compressor matches that of the classic Gaussian mechanism well, i.e., the communication efficiency is obtained with negligible loss. Note that our results hold as long as $\mu < \sqrt{4dr/(1-r)}$, in which $\mu$ is the privacy guarantee and $r$ the sparsity ratio. Even when $r = 1$, the ternary compressor leads to an improvement of 32x in communication efficiency (if 32 bits are used to represent a float) compared to the Gaussian mechanism. The improvement is supposed to be larger when $r$ decreases.
Finally, we would like to mention that the contributions of this paper are not limited to the proposed ternary compressor. The analyses of tight $f$-DP guarantees for a variety of recently proposed differentially privacy mechanisms and compression schemes are valuable on their own.
We hope the above clarification further alleviates your concern. Please let us know if there are further questions.
Best regards,
Authors of the paper