Noisy SIGNSGD Is More Differentially Private Than You (Might) Think

Dear reviewer nyXX

We appreciate your time and effort in reviewing our paper and providing a positive evaluation. Please find our response below.

Comparison with sketching-based approaches: Thank you for pointing out this important aspect. We note that the compression of differentially private mechanisms aims to compress and simulate the distribution of the DP randomizer, usually in the presence of some shared randomness. The resulting compressed mechanisms have a smaller communication cost compared to the original mechanism while retaining the (or weakened) privacy guarantee.

On one hand, our work endeavors to quantify the privacy amplification effect of the sign-based compressor instead of achieving minimum communication cost for a given differential privacy mechanism without ruining its privacy guarantee. On the other hand, we believe that our method can be further combined with these compression schemes (i.e., simulating a Bernoulli distribution). Considering the privacy-utility-communication trade-off in this case would be an interesting future direction.

We will add a literature review and the corresponding discussions in related works in the revised version.

Dear reviewer t9hH

We appreciate your time and effort in reviewing our paper and providing constructive comments. Please find our point-by-point response below.

Question about error analysis: The rationale behind the analysis in Eqs (14)-(16) is that unbiased estimate of gradients is generally preferred in distributed/federated learning, considering that the majority of convergence analyses are established on the assumption of unbiased gradient estimator. Particularly, assuming a smooth loss function, the key is to bound $\langle\nabla F(\boldsymbol{w}^{(t)}), \boldsymbol{w}^{(t+1)}-\boldsymbol{w}^{(t)}\rangle$ (see Eq. (71)), where $\boldsymbol{w}^{(t+1)}-\boldsymbol{w}^{(t)} = -\eta\frac{1}{M}\sum_{i\in \mathcal{H}}\boldsymbol{g}\_{i}\^{(t)}$ for SGD and $-\eta\frac{1}{M}\sum\_{i\in \mathcal{H}}sign(\boldsymbol{g}\_{i}\^{(t)} + \boldsymbol{n}\_{i}\^{(t)})$ for Noisy SignSGD. In this case, it is desired that $\mathbb{E}[sign(\boldsymbol{g}\_{i}\^{(t)} + \boldsymbol{n}\_{i}\^{(t)})]$ is as close to (a scaled version of) $\boldsymbol{g}_{i}^{(t)}$ as possible such that the performance of Noisy SignSGD approaches that of SGD.

Results in Figure 3: Indeed, for small $\sigma_{DP}$, Gaussian noise $\mathcal{N}(0,\sigma_{DP})$ tends to have a larger standard deviation than Logistic noise $Logistic(0,s)$. More specifically, to ensure the same privacy guarantees, $s = c/\ln(\Phi(c/\sigma_{DP})/\Phi(-c/\sigma_{DP}))$ (see discussion below Eq.(13)), and $\sigma_{DP} > s\pi/\sqrt{3}$ (the standard deviation of logistic noise) when $\sigma_{DP}$ is small. In this sense, G-NoisySign may not always be better than L-NoisySign, especially when $\sigma_{DP}$ is small and data heterogeneity is not a concern. However, we note that heterogeneous data and a large $\sigma_{DP}$ (i.e., more stringent privacy requirement) are of particular interest, especially in differentially private federated learning. We will add the discussion and numerical results for more general cases in the revised version.

Additional experiments: We perform additional experiments on FMNIST with $\alpha = 100$ to simulate homogeneous data, and the results (10 repeats) are given below.

We also perform more experiments on CIFAR-10 (5 repeats due to limited time) with $\alpha = 100$.

Fewer workers: We perform more experiments on FMNIST (10 repeats) with 5 workers selected in each round with $\alpha = 0.1$.

It can be observed that G-NoisySign and L-NoisySign attain comparable performance with the Gaussian mechanism in all the experiments above.

Performance gap with baselines & best results: Note that the goal of our paper is not to outperform DP-SGD in accuracy but to show the privacy amplification of sign-based compression. Please refer to our response to Reviewer AkDc under Marginal improvement over DP-SGD and Concern about presenting the best results for more details.

Number of repeats & essential references: We will increase the number of repeats and add the reference as suggested in our revised version.

We hope that your comments have been addressed adequately. Please let us know if there are any questions.

Dear Reviewer Jupt,

We appreciate your time and effort in reviewing our paper and providing a positive evaluation. Please find our point-by-point response below.

Relation to other compression techniques under privacy constraints: Thank you for pointing out this important aspect. We note that the compression of differentially private mechanisms aims to compress and simulate the distribution of the DP randomizer, usually in the presence of some shared randomness. The resulting compressed mechanisms have a smaller communication cost compared to the original mechanism while retaining the (or weakened) privacy guarantee.

On one hand, our work endeavors to quantify the privacy amplification effect of the sign-based compressor instead of achieving minimum communication cost for a given differential privacy mechanism. On the other hand, we believe that our method can be further combined with these compression schemes. The problem concerning privacy-utility-communication trade-off is important and interesting, which will be considered in our future work.

We will add a literature review and the corresponding discussions in related works in the revised version.

Convergence across iterations: We will add the corresponding figures showing the convergence with respect to the communication round or communication overhead in the revised version.

Third sentence of the abstract: We will revise and break it down into two sentences for clarity.

The font size of Figure 2: We will revise accordingly.

We hope that your comments have been addressed adequately. Please let us know if there are any questions.

Dear Reviewer AkDc,

We appreciate your time and effort in reviewing our paper and providing constructive comments. Please find the response to the comments below.

Concern about presenting the best results: This is due to confusion. We run the algorithms for 5 repeats, compute the mean and standard deviation, and present the results with the highest mean accuracy over all the tuned learning rates. We will revise it accordingly to avoid confusion.

Privacy amplification or tighter evaluation: We note that in Fig. 1, the black curve shows the privacy of the Gaussian mechanism, and the blue curve for the Gaussian mechanism combined with $sign$. The improvement is due to the privacy amplification effect of $sign$.

Privacy amplification is small: As we discussed in Remark 2, compared to the Gaussian mechanism without $sign$, there is an improvement by a factor of $\sqrt{\frac{\pi}{2}} \approx 1.25$. In such a case, if a Gaussian mechanism with variance $\sigma$ gives $\mu_{G} = \frac{2C}{\sigma}$-GDP, further incorporating $sign$ provides $\mu_{GNS} = \frac{2C}{\sigma\sqrt{\frac{\pi}{2}}} \approx 0.8\mu_{G}$. There is a decrease in $\mu$ for around 20%.

Accuracy decrease for majority vote: Note that majority vote improves the server-to-client communication efficiency and may provide another improvement in privacy if central DP is concerned (consider privacy leakage of releasing the aggregated results), considering that taking the majority vote is equivalent to adopting $sign$ at the server side. Unfortunately, the improvement in communication efficiency and central DP comes with a loss in privacy. The interlay among communication, privacy in terms of central DP, and accuracy would be an interesting future direction.

Impact of clipping: We agree that studying the impact of clipping is important, which has been considered in some existing works, e.g., [R1-R2]. However, we want to emphasize that the convergence analyses are not our major contributions. Instead, we focus more on the privacy amplification effect of sign-based compressors. Therefore, we follow the existing literature and adopt the bounded gradient assumption.

[R1] X. Zhang, et al. Understanding clipping for federated learning: Convergence and client-level differential privacy, ICML 2022.

[R2] X. Chen, et al. Understanding gradient clipping in private SGD: A geometric perspective, NeurIPS, 2020

Marginal improvement over DP-SGD: We would like to clarify that our goal is not to show that noisy SignSGD outperforms DP-SGD in accuracy, but that compression by $sign$ does not result in much loss in privacy-accuracy tradeoff. Particularly, discarding the magnitude leads to a significant improvement in communication efficiency (32$\times$ assuming each float number is represented by 32 bits), which may in turn hinder the accuracy. We show that the loss in accuracy caused by compression leads to privacy amplification. A comparable privacy-accuracy tradeoff with DP-SGD means that the improvement in communication efficiency is obtained almost for free.

Randoming the sign: Randomizing the sign could further improve the privacy guarantees, and Theorem 1 in the paper can capture the amplification as long as the probability of flipping is known. However, without clipping, we may not utilize the privacy amplification effect of taking the signs since it is not DP on its own.

Step size tuning: In our experiments, we find that DP-SGD is more sensitive to learning rates. The best learning rates of DP-SGD vary for different $\mu$'s, while those of G-NoisySign and L-NoisySign (and the majority vote variants) only change slightly. This may be attributed to the fact that adding noise with a large variance to the gradients makes the training process less stable (e.g., a large noise may lead to a large deviation in model updates), and a smaller learning rate is preferred. The clipping effect of the $sign$ compressor may help in this case. We will add more discussion in the revised version.

The choice of clipping threshold: We note that many existing works adopt a similar clipping threshold for experiments at a similar scale. For example, [R3] suggested a consistent performance with $C \in \\{1,2,3,4,5\\}$ for MNIST. [R4] adopted $C=1$ for both MNIST and CIFAR-10. [R5] set $C \in \\{1, 1.5\\}$ for MNIST. In our experiments, we tested different $C \in \\{1,2\\}$ for FMNIST, and the trends are consistent with those presented in the paper. We will add more detailed discussions in the revised version.

[R3] M. Abadi, et al. Deep learning with differential privacy. ACM SIGSAC conference on computer and communications security, 2016.

[R4] Q. Zheng, et al. Federated f-differential privacy. AISTATS, 2021

[R5] J. Dong, et al. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B, 2022

We hope that your comments have been addressed adequately. Please let us know if there are any questions.