Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Authors: Richeng Jin
Huaiyu Dai
Venue: ICML 2025 poster (2025)
Keywords: differential privacy
sign-based compressor
Primary area: social_aspects->privacy
TL;DR: This paper shows the privacy amplification of the sign-based compressor when combined with deferentially private mechanisms

Abstract: The prevalent distributed machine learning paradigm faces two critical challenges: communication efficiency and data privacy. SIGNSGD provides a simple-to-implement approach with improved communication efficiency by requiring workers to share only the signs of the gradients. However, it fails to converge in the presence of data heterogeneity, and a simple fix is to add Gaussian noise before taking the signs, which leads to the Noisy SIGNSGD algorithm that enjoys competitive performance while significantly reducing the communication overhead. Existing results suggest that Noisy SIGNSGD with additive Gaussian noise has the same privacy guarantee as classic DP-SGD due to the post-processing property of differential privacy, and logistic noise may be a good alternative to Gaussian noise when combined with the sign-based compressor. Nonetheless, discarding the magnitudes in Noisy SIGNSGD leads to information loss, which may intuitively amplify privacy. In this paper, we make this intuition rigorous and quantify the privacy amplification of the sign-based compressor. Particularly, we analytically show that Gaussian noise leads to a smaller estimation error than logistic noise when combined with the sign-based compressor and may be more suitable for distributed learning with heterogeneous data. Then, we further establish the convergence of Noisy SIGNSGD. Finally, extensive experiments are conducted to validate the theoretical results.

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Richeng Jin'
Huaiyu Dai
Abstract
1. Introduction
Nowadays, deep learning has been playing a vital role in various applications, which is fundamentally reshaping the development of our modern society. With the tremendous growth of neural network size, it is unlikely, if not impos- sible, to store all the training data single machine and perform centralized training. Therefore, distributed learning has become the most prevalent training paradigm. In the typical parameter server framework, a set of workers (or equivalently clients) collaboratively train a global model un- der the coordination of server. In the celebrated distributed stochastic gradient descent (SGD) algorithm (Bertsekas & Tsitsiklis, 2015), the server maintains model that is up- dated iteratively by aggregating the stochastic gradients derived on the local datasets from the workers.
The prevalent distributed machine learning paradigm faces two critical challenges: commu- nication efficiency and data privacy. SIGNSGD provides a simple-to-implenee
approach with improved communication efficiency by requiring workers share only the signs of the gradients. However, it fails to converge in the presence of data hetcrogeneity, and a simple fix is to add Gaus- sian noise before taking the signs, which leads to the Noisy SIGNSGD algorithm that enjoys compet- itive performance while significantly reducing the communication overhead. Existing results sug- gest that Noisy SIGNSGD with additive Gaussian noise has the same privacy guarantee classic DP-SGD due to the post-processing property of differential privacy, and logistic noise may be a good alternative to Gaussian noise when com- bined with the sign-based compressor. Nonethe- less, discarding the magnitudes in Noisy SIGNSGD leads to information loss, which may intuitively amplify privacy. In this paper, make this intu- ition rigorous and quantify the privacy amplifica- tion effect of the sign-based compressor. Partic- ularly, we analytically show that Gaussian noise leads to a smaller estimation error than logistic noise when combined with the sign-based com- pressor and may be more suitable for distributed learning with heterogeneous data. Then, fur- ther establish the convergence of Noisy SIGNSGD. Finally, extensive experiments are conducted to validate the theoretical results.
Distributed SGD faces two critical challenges. As the sizes of neural networks grow, the communication overhead in- curred for the transmission of gradients becomes the major bottleneck. For instance, modern large language models may have billions of model parameters, and sharing the gradients leads to prohibitive communication overhead. In the meantime, in applications like federated learning, the local training data may contain sensitive information about the workers, which renders them unwilling to participate in training. Particularly, it has been shown that training data can be effectively reconstructed from the gradients (Wang et al., 2019; Zhu et al., 2019; Yue et al., 2023), resulting in privacy concerns.
To address communication efficiency concern, SIGNSGD, which allows the workers to transmit the signs of gradients and enables an improvement of 32x in communication ef- ficiency, is proposed (Bernstein et al., 2018; 2019). One major concern that prevents the application of the vanilla SIGNSGD is the non-convergence issue in the presence of data heterogeneity across workers. Therefore, various meth- ods, including error compensation (Karimireddy et al., 2019; Zheng et al., 2019), stochastic sign compressor (Chen et al., 2020b; Safaryan Richtárik, 2021; Jjin et al., 2024; Tang et al., 2024), variance reduction (Chzhen & Schechtman, 2023), local momentum (Sun al., 2023), and adaptive methods (Crawshaw et al., 2022), have been proposed to address the non-convergence issue.
'College of Information Science and Electronic Engineer- ing, Zhejiang University, Hangzhou, China. 'Department of Electrical and Computer Engineering, North Carolina State Uni- versity, Raleigh, NC, USA.. Correspondence to: Richeng Jin <richengjin @ @zju.edu.cn>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Among these approaches, a simple and elegant fix is adding

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Gaussian noise to the gradients before taking the signs, which leads to the G-NoisySign compressor and the corre- sponding Noisy SIGNSGD algorithm (Chen et al., 2020b). Meanwhile, adding Gaussian noise is the de facto method for preserving differential privacy (DP) in distributed learn ing, which has been shown to be order-optimal (Cai et al., 2021). Thanks to the post-processing property of differential privacy, the privacy guarantee is preserved after taking the signs of the perturbed gradients (Jin et al., 2020). (Chaud- huri et al., 2022) and (Guo et al., 2023) empirically observe that Noisy SIGNSGD achieves a comparable performance to the classic Gaussian mechanism without compression. Recently, (Jang et al., 2024) shows that logistic noise (with the corresponding compressor denoted by L-NoisySign) is more appropriate than Gaussian noise for sign-based gradi- ent descent methods. However, these works do not account for the potential privacy amplification effect of s-gm(-). In- tuitively, discarding the magniudees of the noisy gradients further incurs information loss, which may potentially im- prove privacy preservation. In this work, we make this intuition rigorous by theoretically deriving the differential privacy guarantee of the generic NoisySign compressors and investigating their performance in distributed learning. In particular, this paper makes the following contributions.
(Chen al., 2020b) shows that the convergence of SIGNSGD is not guaranteed and proposes to add carefully designed noise ensure a convergence rate of O(d /T+). (Jin et al., 2024) proposes a stochastic-sip compressor to address the non-convergence issue. However, none of these works takes privacy into consideration.
Differential Privacy Mechanism: To improve communica- tion efficiency over the classic DP-SGD (Abadi et al., 2016), significant research efforts have been devoted to develop- ing discrete mechanisms. (Agarwal et al., 2018) extends the one-dimensional binomial noise scheme (Dwork et al., 2006a) to the general d-dimensional case with more compre- hensive analysis in terms of (c, 5)-DP. (Canonne et al., 2020; Kairouz et al., 2021) study the DP guarantees of discrete Gaussian noise. (Agarwal et al., 2021) and (Chen al., 2022) propose the Skellam mechanism and the Poisson bi- nomial mechanism, respectively, with Rényi DP guarantees. (Chaudhuri et al., 2022; Guo et al., 2023) propose privacy- aware compression through numerical mechanism design, and (Zhu & Blaschko, 2023) studies the impact of random sparsification on DP-SGD. (Chen et al., 2020a) proposes the subsampled and quantized Kashin's 's response (SQKR) mechanism that achieves order-optimal estimation error in distributed mean estimation. (Chen et al., 2023) studies privacy amplification by compression for central (c, 6)-DP, while (Jin et al., 2023) considers the privacy amplification of random sparsification through the lens of f-DP.
We theoretically analyze the differential privacy guar- antee of the generic NoisySign compressor that cap- tures G-NoisySign and --NossySign as special cases and show the privacy amplification effect of the sign(-) compressor through the lens of f-DP. Particularly, for the scalar case, the derived privacy guarantee is tight, in the sense that it cannot be improved in general.
The most related work to this paper is (Jang et al., 2024), which finds that logistic noise is more appropriate than Gaussian noise when combined with the sign-based com- pressor. It is shown that, given the same privacy guaran- tee, L-NoisySign has a lower sign-fipping probability than G-NoisySign. However, the sign-flipping probability may not be the best performance indicator considering that the vanilla SIGNSGD has a sign-flipping probability of 0 but fails to converge with heterogeneous data. In sharp contrast, by accounting for the privacy amplification effect of the sign(.) compressor, we show that G-NoisySign enjoys a smaller estimation error given the same privacy guarantee, which leads to a smaller probability of wrong aggregation in the distributed sign estimation scenario with data heterogeneity. In addition, we adopt the emerging f-DP framework (Dong et al., 2021), which enjoys a better composition property than the classic (e. 8)-DP considered in (Jang et al., 2024).
Based on the theoretical results, we further show that given the same privacy guarantee, G-NoisySign enjoys smaller estimation error than I.-NoisySign and may be more suitable for distributed learning scenarios with heterogeneous data.
We establish the convergence of Noisy SIGNSG with two aggregation schemes: averaging and majority vot- ing. Extensive numerical and experimental results vali- date our theoretical findings.
2. Related Work
Sign-based Gradient Quantization: The idea of sharing the signs of gradients in SGD can be traced back to 1-bit SGD (Seide et al., 2014). Despite that basn- quantiza- tion is biased in nature, (Carlson et al., 2015) and (Bernstein et al., 2018; 2019) show theoretical and empirical evidence that sign-based gradient descent schemes converge well in the homogeneous data distribution scenario. (Safaryan & Richtárik, 2021) shows the convergence of SIGNGGD given the assumption that the probability of wrong aggregation is less than 1/2. In the heterogeneous data distribution case,
Compression of Differential Privacy Mechanism: An- other line of research considers the compression of differen- tially private mechanisms (Bassily & Smith, 2015; Triastcyn et al., 2021; Feldman & Talwar, 2021; Shah et al., 2022; Liu et al., 2024), which aims to compress and simulate the distribution of the DP optimizer, usually in the presence of some shared randomness. The resulting compressed mech- anisms have smaller communication cost compared to
2

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
the original mechanism while retaining the (or weakened) privacy guarantee. In this work, investigate the privacy amplification of the sign-based compressor.
Let P and Q denote the probability distribution of M(S) and M(S"), respectively. Following the formulation in (Dong et al., 2021), the task of distinguishing the two hy- potheses can be described as a tradeoff between the achiev- able type and type II error rates. Specifically, for a rejection rule 0 - Φ S 1, the type and type II error rates are defined as Cle = I [o] and 3. = 1 - E2( [6], respectively. f-DP characterizes the tradeoff between these two error rates by a tradeoff function formally defined as follows.
3. Problem Setup and Preliminaries
3.1. Problem Setup
We consider the classical parameter-server distributed learn ing framework, comprising M workers (denoted by 7() and central server. Each worker is equipped with local dataset Pm. and the collective objective is to minimize the finite- sum function:
Definition 2 (Tradeoff function). For any two probability distributions P and Q on the same space, the tradeoff func- tion T Q) [0. 1] - [o, 1] is defined as T(P, (a) inf [n : as S a}. where the infimum is taken over all (measurable) rejection rule $
min F(w) def WERd
Σ fm(w), mEH
(1)
M
where fm (w) represents the local loss function associated with worker m, defined by Dm and the parameter vector
Definition 3 (f-DP). Let f be a tradeoff function. With a slight abuse of notation, a mechanism M is f-differentially private if T(M(S),M(S
w E W. Specifically, fm(w) (w) = pmm E.ED... 1(w; s) where |Dml is the size of 'Dm and I W x D + R is
2 f for all neighboring datasets S and S' which suggests that the attacker can- not achieve type II error rate lower than f(a).
the loss function that quantifies the error of prediction on a data point 8 E Dm made with w.
f-P can be converted to 8)-P) in a lossless way as follows.
3.2. Differential Privacy
Lemma 1. (Dong et al., 2021) A mechanism is f(a)- differentially private if and only if it is (e, ddifferrenel private with
Differential privacy is rigorous mathematical framework for quantifying and ensuring privacy in data analysis. At its core, DP guarantees that the output of a mechanism remains statistically indistinguishable for two neighboring input datasets that differ in only one record. Formally, it is defined as follows.
f(a) = max(0, (0, 1 - 6-e,,, e (1-8-a)) (4)
We further introduce a special instance of f-DP with f(a) = 4 a) μ)), referred to as μ-GDP. In this case, μ-GDP corresponds to the tradeoff function of two normal distributions with mean and μ., respectively, and unit variance. It has the following composition property. Lemma 2. The T-fold composition of HD-GDP mechanisms is u + ug + +.... -DP.
Definition 1 ((e, 0)-D (Dwork al., 2006a)). random- ized mechanism M is deifferrrnnyl private for all nei neighboring datasets S and S' and all O C O in the range of M, we have
(2) in which e, 8 20 0 are the parameters that characterize the level of differential privacy.
P(M(S) E O) S P(M(S)) E O))
4. Differential Privacy of Noisy SIGNSGD
4.1. DP Guarantees of Generic Sign-based Compressors
The application of differential privacy can be largely divided into two categories: (1) Central differential privacy (CDP) (Dwork et al., 2006b) requires a trusted central server to randomize the collected data from the workers and release a private version of the aggregated results; (2) Local differ- ential privacy (LDP) (Kasiviswanathan et al., 2011) does not assume a trusted central server. Instead, the workers perturb the data before sharing them with the central server. In this work, similar to (Jang et al., 2024), we mainly focus on LDP.
In this section, we consider generic sign-based compressor and investigate its privacy guarantee through the lens of f- DP, starting with the scalar case and extending it to the vector case in Section 4.3.
Definition 4 (Generic Sign-based Compressor). For any given [-c,c], c), the generic noisy sign-based compressor outputs NoisySign(x, P+1 P-1) 1), which is given by
1, with probability p-1 (x))
N NoisySign(2. (e.Sigg( = -1, 1, with probability p- (x),
3.3. f JDifffrrentill Privacy
(5)
where p+1 (x), p- (2x) [pmin J. (41 1, and 0 S Pmin S Pmaxx 1.
Consider two neighboring datasets S and S', from the hy- pothesis testing perspective, there are two hypotheses Ho the underlying dataset is S,
In the following, we show the f-DP of the basnd com- pressor. We provide a sketch of proof, and the complete
H the underlying dataset is S'.
3

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
proof is given in Appendix A. It is worth mentioning that the result is tight and cannot be improved in general since no relaxation is involved.
4.2. Privacy Amplification of deterministic sign(-)
Given the privacy guarantee of the generic sign-based com- pressor in Section 4.1, examine the privacy amplifica- tion effect of the deterministic sign(.) compressor. Intu- itively, the sign(-) operator does not provide differential privacy guarantees on its own due to its deterministic na- ture, and the adversary can distinguish x from x' given sign(z) or sign(z') if zx' < O. However, when com- bined with differentially private mechanisms, discarding the magnitude is expected to improve the privacy guar- antees. Specifically, we consider the noisy sign-based compressor combined with Gaussian noise, denoted by G- NoisySign, given in Algorithm 1. The G-NoisySign com-
Theorem 1. Suppose that Pmaz + Pruin = 1, and P+1(x) > (+)( Vx > y. The sign-based compressor is is PNoosySign (a) difffereentl private with
Pmaz
for a E [0, Pminn,
{ NNoisySig (o)
Pman
Pmin
Pmnn a, for a E [Pmin 1].
Pmnce
Pmux
(6)
Sketch of Proof. The proof of Theorem 1 utilizes the Neyman-Pearson Lemma (Lehmann et al., 2005), which states that the most powerful test for the hypothesis testing problem (i.e., whether the input is x or x²) at a given type error rate a is threshold-based, which determining the corresponding
Algorithm G-NoisySign Compressor (Chen et al., 2020b)
Input: e > 0, x E [-c, c). Gaussian noise n with zero mean and variance ohp-
reduces the problem threshold. Without loss of generality, assume that x >> r' and let Y NoisySign(a"' PP+1.P-1) N (2,
Privatization: - sign(s + n).
) and X =
pressor first perturbs the input x with a Gaussian noise n with zero mean and a variance of obP and then returns the sign of the noisy result. According to (Dong et al., 2021), is known that directly releasing x + n gives μ(- GDP with μ onp
We may set the threshold h p (wm) for (-))-1
p (())
ie., if the likelihood ratio P(X-k) is larger than/equal to/smaller than h, the hypothesis that the true data is a will be rejected with probability 1///0,, where & E (-1,1} is the observed output of the sign-based compressor. In P(Y=1) since this case, observing that P(X=-1) > 1 > P(X=1)
p(Y=k)
2c which further suggests (e, 6)-DP with -e' c' n ()) for any 2 0. If we measure the μ-GDP and (c, ()PP in terms of tradeoff func- tions, we have f pGaussian (a) 4 ( (11-0 a) - p)) and fC (Gaussiin = max(0, - 8 - e'a, (1 81- a)), respectively. In the following, we prove that releasing sign(æ + n) instead of vacy protection. Utilizing Theorem 1, readily obtain the f-DP guarantee of G- G-NoisySign as follows.
8(c) D e + +2)
"
p+1 (1)) > P+i(U)) (v), Ya > y,, we can derive the type I and type II error rates as follows.
Ep[ø] = 7P( -1)= = >p-1((>) a,
(7)
adds another level of pri-
1-Eold) = 1 - -Pp--p-------- = = 1111-111p-((11
= p- (x)(
(8)
j JGNS (a)
(=) a.
Cz2
for a E [0, 10- oor )},
-b0)),
Similarly, when a E (x-1 11. we set h P(Y=1)
P(X=1)+ and
4
1
for a E [ ODF ) 1]. 02
therefore
Erlo| P(X 1) + xP(X=1
(12)
(9)
-x-( + (x+ =a,
and
Figure/ 1 compares the privacy guarantees of the G- NoisySign mechanism with the Gaussian mechanism (i.e.. directly releasing x +n) given c = and DP = 2. It can be observed that JGNS (a) 2 fa 2
1 1 Eold = 1 - P(Y = -1) - -P((Y- = 1)
= =P-1(x') - (2')
(10)
&Goussion (at) 2 pCaussion (a), i.e., given the same type I error rate a, G-NoisySign at- tains a larger type II error rate than the vanilla Gaussian mechanism, which suggests that it is more difficult for the adversary to distinguish the inputs, or equivalently, better privacy.
= =2-1(x')- - a (x) P+1(x').
(1)
In summary, the type II error rate is given by
1 (ar)
p-1(m) a, for E [0,p-1(x)) (x)],
(a(a)= = p(1(z') e1)(2)) a, for E [p-1(x), 1].
(m) P+i(a)
Logistic Mechanism: Note that the generic sign-based based compressor in Definition 4 captures the logistic mechanism in (Jang et al., 2024) as a special case. More specifically, the logistic mechanism replaces the Gaussian noise n in
(11)
The infimum of (a) is attained when p-1(x') = Pmax and p-1(x) (x) = Ponin which completes the proof. LI
4

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
1.0
Therefore, we use Vingne x sign (a + NO, ap)) and 2s x sign (z Logistic((O s)) as the estimate of for G-NoisySign and L-NoisySign, respectively. In the high- privacy regime (i.e., large OD and s), the estimation errors A and A are dominated by the second terms in (14) and (15), respectively, which are given by
2
0.8
G NoisySion (P)
Gaussian Nolse (GDP)
0.8
Gaussian Noise (ic. DP
0.4
|x 3
| 3
0.2
|
(16)
60 DP /
12s²
0.0
0.0
0.2
0.4 0.6
0.8 1.0
When 8 = c/ In necessary condition for
/
c
)), the sufficient and
ODD
opr
Figure 1. Privacy Amplification of sign(-). For "G-NoisySign",. the tradeoff function is given by (12) with 1 and opp- 2: for "Gaussian Noise (GDP)". the tradeoff function given by fy pClonssion (a) with / 1; for "Gaussian Noisc ((, DP)", the tradeoff function is given by f2.6 f.aussiion (a) with e =
A Gl
L is given by
+
v2c
In
oDp
(17)
ODP
app
Let h(x) = In( (ar)
2.x, then h1' h((x) = [
((x)
(11-(2))
$1 "(opp) In( D(- "pr"
and 8 $6- 5 + ) - c'0(-; 1 - 4), in which
v2 ((z) 41
2
22, in which ((-) is the probability
c= c=== and aDp- 2.
density function of the standard normal distribution.
<(a)
T(*)
is the famous inverse mills ratio for the standard normal distribution, which is known be strictly convex (Gasull
Algorithm 1 with logistic noise ~ Logistic(O, 8) for some hyperparameter 8, which leads to p+1 el Ze
& Utzet, 2014), which suggests {(z) + ((-2) > 2 200)
Φ(ar)
d(-n)
(0)
V2T > v2. Therefore, h(x) > 1(0)= = for x > 0, i.e.
and p-1 = a te- s. respectively. Utilizing Theorem yields the following/ f-DP guarantee for I.-NoisySign.
c t
the inequality (17) holds for any ap > O. As result, we conclude that, in the high-privacy regime, G-NoisySign is more suitable if we are more concerned with the estimation error. This corresponds the distributed mean estimation scenario, which is the building block of federated learning.
1 e az for [0,
#
(aN
2 +0 27
e a for +e $ 1].
(13)
Figure 2 presents numerical results that compare G- NoisySign and L-NoisySign in terms of the ratios between the estimation error (i.e., A and | and the input magnitude [x|] for different Dp and z, which validate the analytical results above.
Comparison between G-NoisySign and L-NoisySign: It can be readily shown that L-NoisySign attains the same ( ) privacy guarantees as G-NoisySign when e = -- epp which means s = c/ In( (n( / -- )). While (Jang et al., 2024) suggests that the logistic mechanism outper- forms the Gaussian mechanism when the sigm(-) compres- sor is applied, we find that this is because the privacy ampli- fication effect of discarding the magnitude is ignored. More specifically, in the following, we show that G-NoisySign may be better than L-NoosySSign in terms of the estimation error in distributed mean estimation. Particularly, utilizing Taylor expansion, we have
ane
034
Uuthigh go
ta Bailydiir
0.2
cone
2.4
-2.1 -2
411
83
Figure 2. The comparison of the ratios between the estimation error and the input magnitude for G- G-NoisySign and L-NoisySign. For the left figure, we fix c 1 and = 0.1 with varying dDP, while for the right figure. we e = and app 0.5 with varying x. For L-NoisySign, we set c/ Iu(# ( ) -pp) to ensure the same privacy guarantee.
[sign (I + (N(00 =
+
TDP
DDP
1
1
DD
2k
dt=
dt
V2T
22T
2 k!!
DDF
PDP
1
x
DP
T
3 3
x
ODP
Remark 1. (Jang et al., 2024) considers the error rate of (14)
sign sampling as the performance metric. We note that this may not be a good performance indicator for federated learning with helerogeneous data across workers. In partic- ular, it has been observed that the vanilla SIGNSGD, which corresponds to the case that the error rate of sign sampling is O. fails to converge in the presence of data heterogeneity (Karimireddy et al., 2019; Chen et al., 2020b; Jin et al.,
and
E Elsign (x + Logistic(O,, s))] = (lanh( _ - tanni-
(--)
I
2
25
28
T
x²
28
2483
55
(15)
5

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Sketch of Proof. In the vector case, we consider higher
Probability of Woog Aggregation
1.0
dimensional hypothesis testing problem given by
0.9
SoisySign L-NoisySign
Ho z ~ P P1 x P2 x x Pa.
(20)
0.8
H1:2 ~ Q = Q1 x Q2 x x Qa-
Let Ta(z) = log [ (z(2.)
denote the privacy loss, in which z = |2|, 22, ..... za] is the output of the mechanism,
IT (x.))
p.(-) and q:(-) denote the probability density functions of
0.5
P. and Q, given the input vectors x and x', respectively.
2
Similar to (Jang et al., 2024), the maximizer of the privacy loss is given by x' -
Oor
C 1. Va
Figure 3. The comparison of the probability of wrong aggregation between G-NoisySign and L-NoisySign. A set of 100 workers are considered, with Tme. -0.05 for S m 98 and x.. 10 for 99 S m S 100. set c 10.
According to the Neyman- Paaaann lemma (Lehmann et al., 2005), the most powerful test at level is thresholding function of Ta(=), and we have
f(a) + Ga((a) = $ - a) - -m), in which μ is the limit of jud with
(21)
2024). With such consideration, we present additional nu- merical results that evaluate the probability of wrong aggre- gation of G-NoisySign and L-NoisySign in Figure 3. More specifically, we consider a set of workers m E H. each with some data Iim, and we are interested in the probability of wrong aggregation, i.e., P(sign()) J. EmEn dign(xm + M Emen Im)). It can be observed in Figure 3 that, in the presence of data heterogeneity, G-NoisySign may outperform L-NoisySign and attain lower probability of wrong aggregation. Note that when OD is small, the probability of wrong aggregation is larger than 0.5, which confirms the results that SIGNSGD may fail with heteroge- neous data. As ODP increases, the probability of wrong aggregation first decreases and then increases. Considering that SIGNGGD converges a stationary point when the prob- ability of wrong aggregation is less than 0.5 (Safaryan & Richtárik, 2021), this implies that adding appropriate noise may benefit both privacy and aggregation accuracy. How- ever, it does not mean that G-NoisySign always outperforms L-NoisySign. More numerical results concerning the impact of data heterogeneity can be found in Appendix C.2.
Hd Eq [Ta(2)] - Ep [Ta(2))
(22)
Varq [Ta(2)]
For G-NoisySign, we have Eq [Ta[2]] Ep [T)(
M
n)) + sign( 1.
d
21
Σ
x
+
log
+
S
C'
C
+
vdo
C
= 2d
+
log
Vdoo
Vdo
vdo
(23)
and Varq [Ta(2)]
x
x/
Φ
Σ
+
+
log
σ
4d
C
+
(-C))
C
log²
+b
Via
C
Voloo
vdo
$
C
4.3. Extending to the Vector Case
vdo
(24)
The privacy analyses in Section 4.1 are concerned with the scalar case, which is extended to the vector case in this section. More specifically, we consider a higher dimen- sional hypothesis testing problem as in (Zheng et al., 2020) and (Dong et al., 2021), and the most powerful test is also threshold- based according to the Seyman-Pearson lemma.
As a result,
Eq [T((2))
Ep [Ta(2)]
Nd
v /Var [Ta(2)]
C Vdo
-Φ
(-
Vd
(25)
Theorem 2. For any vectors and x' with ||0||2, || x C, the tradeoff function JGNS (ni) for the corresponding hypothesis testing problem satisfies
C Vila
C Vilo
The mean value theorem (Rudin al., 1964) implies that
pGNS( (a) d Gp(o)= = Φ 1b( (1 - a) -1), (18)
x
in which y is the limit of pa with
+b
|
2z1-
(26)
2C
ov
2x
Hd S
(19)
2
C
Vdoo
6

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Algorithm 2 Differentially Private Noisy SIGNSGD
with the G-NoisySign compressor, i.e., Algorithm 2. Dif- ferent from (Jang et al., 2024) which mainly considers cen- tralized learning, we focus on distributed learning with data heterogeneity. To facilitate the convergence analysis, we make the following commonly adopted assumptions.
Initialization: The initial model weights wo. the batch size b, the clipping function Clip(-), the learning rate 7, and the total number of communication rounds T. for communication round = 0, 1, 2, .... ,T do The central server sends the model weights w(() to the workers.
Assumption 1. (Lower bound). For all a and some constant F", we have objective value F F(x) 2 F".
for each worker i 7 do
Sample mini-batch B training examples of size b at random from D.. Then compute and clip the per-example gradients and average the mini-batch gradients:
Assumption (Smoothness). Vy. x. we require for some non-negalive constant L,
L lly
Fly) S F(x) + (VF(2) x) + where (:--) is the standard inner product.
2
x x122,
(31)
9:
(t)
1 b
Clip (w
(28)
Assumption (Variance bound). For any worker m, the stochastic gradient oracle gives an independent unbiased estimate 9m that has coordinate-wise bounded variance:
.E
Compress and send - = C(g. ) sign (g;
(t)
BP I)) back the central server.
Egg = Fm F (l),,, vFm(w):) LoL.s (32)
end for
for vector of non-negative constants σL
The central server aggregates the received gradients with two possible schemes 0
"I,,,""',, "IL.a)
Agg(i Z (4) hee)
Assumption 4. (Gradient bound). For any worker m, the stochastic gradient satisfies gm S e, V1 Sisd. d.
1 [
Eieh 2,0)
Scheme I,
(29)
sign [Tे] EiEH ) Scheme II.
Note that clipping is usually applied to ensure bounded gradients in DP-SGD (Abadi et al., 2016). In this work, we follow the literature (c.g.. (Chen et al., 2020b; Xiang & Su, 2023)) and adopt the bounded gradient assumption, i.e., Assumption 4, for convergence analysis. The impact of gradient clipping is left for future work.
The central server updates the model by ((++1)] (t) n
(30)
end for
Therefore,
Theorem (Convergence of Noisy SIGNSGD with Scheme I). Suppose Assumptions 1-4 are satisfied, and the learning Then by running Algorithm 2 for T iterations, we have
2C
Pa S
(27)
rate is set as 1) "TLLa"
2
C vd
Vdoa
which completes the proof.
1
VF(W
11:
(F(w - F*) Ld 2
T
VT
Remark 2. We note that the Gaussian mechanism with variance a has a PG-GDP guarantee with PG 2C/a (Dong et al., 2019). In Theorem 2. when d and increase (which corresponds to larger neural network and more stringent privacy requirement), the privacy guarantee of G- NoisySign converges to PGNS = 2C / n/2. Therefore, there is an improvement by a factor of /T/2. Utilizing the composition property in Lemma 2, for the same overall privacy guarantee, G-NoisySign allows for π. / more train- ing steps than the classic Gaussian mechanism. Therefore, while (Jang et al., 2024) claims a similar improvement (i.e., 1.5x more training steps) when utilizing the L-NoisySign mechanism, our result suggests that this is mainly due to the fact that the privacy amplification effect of the sign(-) compressor over the Gaussian mechanism is ignored.
VLdV2 + +0
2/T
DP
(33)
Remark 3. Adding a Gaussian noise with variance ODP yields μ-GDP with μ = O pP) and the composition of p-GDP mechanisms in Lemma 2 suggests an overall privacy guarantee UT = O (VT//DD) over T communication
rounds. If we set aDr O (VT/Uz): Theorem 3 implies S 10(1//0 + (c444/T)) i.e.,
$ CILIIVV( it converges to the neighborhood of the local optimum with a gap O (1/UT), which matches the state-of-the-ar results (Fang et al., 2022; Koloskova et al., 2023).
5. Convergence of Noisy SIGNSGD
Theorem (Convergence of Noisy SIGNSGD with Scheme II). Suppose Assumptions 1-4 are satisfied, and the learning rate is set as 17 VI Then by running Algorithm 2 for
In this section, we show the convergence of Noisy SIGNSGD
7

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Table I. Fashion-MNIST Test Accuracy for Varying Privacy Requirements Per Communication Round (a 0.1)
0.04
0.08
0.4
0.8
1.6
GAUSSIAN NOISE
43.78 + 1.98%
58.69 1.48%
73.48 + 0.49%
77.17 + 0.51%
79.90 0.25%
G-NOISYSIGN
= 2.51%%
58.46 2.48%
73.78 = 0.57%
77.20 = 0.29%
79.57 0.57%
G-NOISYSIGN-VONE SIOTE
42.18 = 4.03%
56.59 = 1.91%
73.23 = 0.66%
76.47 + 0.61%
79.27 + 0.37%
L-NOISYSIGN
42.52 = 3.11%
58.39 1.53%
73.89 = 0.78%
77.18 + 0.31%
79.66 + 0.45%
L-NOISYSIGN-VOTE
40.46 + 3.82%
53.89 = 1.82%
73.23 + 0.47%
76.49 + 0.31% %
79.24 + 0.31%
Table 2. CIFAR-10 Test Accuracy for Varying Privacy Requirements Per Communication Round (a = 1)
0.8
1.6
4
GAUSSTAN NOISE
40.77+1.222
48.02+00.69
56.73+0.600%
63. 63.13+1.155 155
67.53+t 0.58%
G-NOISY SIGN
40.28=0.66%%
47.80=10.97%
56.56 100%
62.70:1.57%
66.82+1.2299
G-NOISYSIGN- VOTE
38.10=1.24%%
46.87=0.84%
55.39+
61.02:+0.96%
65.70+1.14 %
L-NOISYSIGN
40.06:10.819 %
47.77=+0.22%
56.72:11.296
6..46.t...8%%
66.69:t1.079
L-NOISYSIGN- VOTE
37.46+00.84%
46.33++0.0%%
55.53+00.90%
61.27+1.21%
65.25++0.71%
iterations, we have
size 32 32 in our experiments.
T
((Fo0")-FF*))
VLd 2VT
[VF((()))
Hyperparameters:
The per-example gradient clip- C and C
T
VT
ping thresholds are for Fashion-MNIST and CIFAR-10, respec- tively. We tune the learning rate from the set {0.001, 0.002, 0.003, 0.005, 0.01, 0.02, 0.03, 0.05, 0.1, 0.3, 0.5, 1, 2, 3, 5, 10} and run the algorithms for 500 com- munication rounds. We run all the algorithms for 10 repeats and present the mean test accuracy.
@DDdV22 2T
21101111
+
VM
VM
D
1
ODP
|اال||
+
VT
VM
VM
op
(34)
We compare the Noisy SIGNSGD algorithms with the G-NoisySign compressor and the L-NoisySign compres- sor with the classic Gaussian mechanism (i.e., DP-SGD (Abadi et al., 2016)). Note that the Gaussian mechanism has been shown to be order-optimal (without considering the communication efficiency) theoretically (Cai et al., 2021) and achieve the state-of-the-an privacy-utility tradeoff ex- perimentally (Guo et al., 2023). Table and Table 2 show that Noisy SIGNSGD with G-NoisySign and L-NoisySign attain comparable performance to the classic Gaussian mech- anism. In this sense, despite that discarding the magnitude information by adopting the sign(.) compressor may result in performance degradation, it leads to enhanced privacy and achieves comparable privacy-utility tradeoff. Note that Noisy SIGNSGD requires only 1 bit for each coordinate of the gradients and, therefore, provides improvement of 32x in communication efficiency. The results for the convergence over communication rounds are presented in Appendix C.2.2.
Results:
Remark 4. The bound in Theorem 4 depends on M. When ODP O(VTi ( and M O(T) (note that M is usu-
ally large in federated learning), we obtain a convergence rate of 1
T Σ (V (1/PT)+
6. Experimental Results
In this section, we present experimental results to validate our theoretical analyses in the previous sections.
Datasets and Models: We evaluate the performance of the algorithms
commonly used benchmarks for dif- ferentially private distributed learning: MNNSS (Xiao et al., 2017) and CIFAR-10 10 (Krizhevsky et al., 2009). We adopt a three-layer fully connected neural network for Mishion-MNIS" and the DPNASNet-CIFAR (Cheng et al., 2022) for CIFAR- 10. For Pashion-MNISS we consider a scenario of M 100 workers with the training data on each worker drawn independently with class labels following Dirichlet distribution Dir(a) with ers are sampled uniformly at random for training during each communication round. For CIF we consider a scenario of M = 30 workers with a = 1, and all workers participate in training during each communication round. We train both neural networks from scratch with a batch
0.1, and 50 work-
It is also worth mentioning that employing majority vote on the server side leads to performance degradation (less than 2% in most of the examined scenarios). While the local pri- vacy guarantees remain the same since it is independent of the aggregation strategy on the server side, there is supposed to be an enhancement in central differential privacy guaran-
8

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
tees since the server releases less information by adopting another sign(.) compressor (i.e., scheme II in (29)). Inves- tigating the privacy amplification effect of the majority vote mechanism remains an interesting future direction.
2018.
garwwal N., Kairouz, P., and Liu, Z. The skellam mech- anism for differentially private federated learning. Ad- vances in Neural Information Processing Systems, 34: 5052-5064, 2021.
7. Conclusion
Bassily, R. and Smith, A. Local, private, efficient protocols for succinct histograms. In Proceedings of the forty- seventh annual ACM symposium on Theory of compuling, pp. 127-135, 2015. 2015.
In this paper, we investigate the privacy amplification ef- feet of the sign(.) compressor, based which further show that the Noisy SIGN SGD algorithm achieves conver- gence rate and privacy-utility trade-off comparable to the classic DP-SGD both theoretically and experimentally. The analyses and results are expected to shed light on the devel- opment of privacy-preserving and communication-effiee distributed learning algorithms.
Bernstein, J., Wang, Y.-X., Azizzadenesheli, K., and Anand- kumar, A. signSGD: Compressed optimisation for non- convex problems. In International Conference on Ma- chine Learning, pp. 560-569, 2018.
Bernstein, J., Zhao, J., Arizzadenesheli, K., and Anandku- mar, A. signSGD with majority vote is communication efficient and byzantine fault tolerant. In International Conference on Learning Representations, 2019.
Acknowledgements
Richeng Jin is supported in part by the National Key R&D Program of China under Grant No. 2024YFE020080, in part by the National Natural Science Foundation of China under Grant No. 62301487, in part by the Zhejiang Provin- cial Natural Science Foundation of China under Grant No. LQ23F010021, and in part by Information Technology Cen- ter and State Key Lab of CAD & CG, Zhejiang University. Huaiyu Dai is supported by the US National Science Foun- dation under Grant ECCS-22032J1 2203214. The views expressed in this publication are those of the authors and do not necessar- ily reflect the views of the National Science Foundation. The authors also appreciate the constructive comments provided by the anonymous reviewers.
Bertsekas, D. and Tsitsiklis, J. Parallel and distributed com-
putation: numerical methods. Athena Scientific, 2015.
Billingsley, P. Probability and measure. John Wiley & Sons, 2017.
Cai, T., Wang, Y., and Zhang, L. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 49()): 2825-2850, 2021.
Canonne, C. L., Kamath, G., and Steinke, T. The discrete gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15688, 2020.
Impact Statement
Carlson, D., Hsieh, Y. P., Collins, E., Carin, L.,, and Cevher, V. Stochastic spectral descent for discrete graphical mod- els. IEEE Journal of Selected Topics in Signal Processing, 10(2):29-3311 201.
This paper presents work whose goal is to advance the field of aavacy-preserving machine learning. We believe that the proposed tool and method will benefit the design of communication-effiieen and differentially private dis- tributed learning algorithms. We do not find any potential negative socictal consequences of this work that must be specifically highlighted here.
Chaudhuri, K., Guo, C., and Rabbat, M. Privacy-aware compression for federated data analysis. In Uncertainty in Artificial Intelligence, pp. 296-306. PMLR, 2022.
Chen, W.-N,, Kairouz, P., and Ozgur, A. Breaking the communication priva-aaa-cccccccccaaay trilemma. Advances Neural Information Processing Systems, 33:3312-3324, 2020a.
References
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 308-318, 2016.
Chen, W.-N., Ozgur, A., and Kairouz, P. The poisson bi- nomial mechanism for unbiased federated learning with secure aggregation. In International Conference on Ma- chine Learning, pp. 3490-3506. PMLR, 2022.
Agarwal, N., Suresh, A. T., Yu, X. X., Kumar, S., and McMahan, B. cpSGD: Communication-eficienn and peateentially-privaa distributed SGD. In Advances in Neural Information Processing Systems, pp. 7564-7575,
Chen, W.-N., Song, D.,, Ozgur, A., and Kairouz, P. Privacy amplification via compression: Achieving the optimal trade-off in distributed mean estimation. arXiv preprint v.Xiv:2304.0/544 2023.

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Chen, X., Chen, T., Sun, H., Wu, S. Z.,, and Hong, M. Distributed training with heterogeneous data: Bridging median- and mean-based algorithms. In Advances in Neural Information Processing Systems, volume 33, pp. 21616-21626, 2020b.
Jang, J., Hwang, S., and Yang, H. J. Rethinking dp-sgd in discrete domain: Exploring logistic distribution in the realm of signsgd. In International Conference on Ma- chine Learning. PMLR, 2024.
Jin, R., Huang, Y., He, X., Dai, H., and Wu, T. Stochastic- Sign SGD for federated learning with thcoretical guaran- tees. arXiv preprint arXiv:2002. 10940, 2020.
Cheng, A., Wang. J., Zhang, X. S., Chen, Q., Wang, P., and Cheng. J. Dpnas: Neural architecture search for deep learning with differential privacy. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 6358 6358-6366, 2022.
Jin, R., Su, Z.. Zhong, C., Zhang, Z., Quek, T., and Dai, H. Breaking the communication- petpratiiiooiivaaa--ccaraaa tradeoff with f-differential privacy. Advances in Neural Informa- tion Processing Systems, 2023.
Chzhen, E. and Schechtman, S. Signsvrg: fixing signsgd via variance reduction, arXiv preprint arXiv:2305.13187, 2023.
Jin, R., Liu, Y., Huang, Y., He, X., Wu, T., and Dai, H. Sign- based gradient descent with heterogeneous data: Conver- gence and byzantine resilience. IEEE Transactions on Neural Networks and Learning Systems, 2024.
Crawshaw, M., Liu, M., Orabona, F., Zhang, W., and Zhuang. Z. Robustness unbounded smoothness of generalized signsgd. Advances in neural information processing systems, 35:9955-9966 2022.
Kairouz, P., Liu, Z., and Steinke, T. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference Machine Learning, pp. 5201-5212. PMLR, 2021.
Dong, J., Roth, A., and Su, W. J. Gaussian differential 2019.
privacy. arXiv preprint
Karimireddy, S. P., Rebjock, Q., Stich, S., and Jaggi, M. Er- ror feedback fixes signSGD and other gradient compres- sion schemes. In International Conference on Machine Learning. pp. 3252-3261. 2019.
Dong, J., Roth, A., and Su, W. Gaussian differential privacy. Journal of the Royal Statistical Society, 2021.
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In Annual international conference on the theory and applications of cryptographic techniques, pp. 486-503. Springer, 2006a.
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhod- nikova, S., and Smith, A. What can learn privately? SIAM Journal on Computing, 40(3):793 8266, 2011.
Koloskova, A., Hendrikx, H., and Stich, S. U. Revisiting gradient clipping: Stochastic bias and tight convergence guarantees. In International Conference on Machine Learning, pp. 17343 17363. PMLR, 2023.
Dwork, C., McSherry, F,, Nissim, K., and Smith, A. Cali- brating noise to sensitivity in private data analysis. In The- ory of cryptography conference, pp. 265 265-284. Springer, 2006b.
Krizhevsky, A., Hinton, G., al. Learning multiple layers of features from tiny images. Technical report, Univ. of Toronto, 2009.
Fang, H., Li, X., Fan, C., and Li, Improved convergence of differential private sgd with gradient clipping. In The Eleventh International Conference on Learning Repre- sentations, 2022.
Lehmann, E. L., Romano, J. P., and Casella, G. Testing statistical hypotheses, volume 3. Springer, 2005.
Feldman, V. and Talwar, K. Lossless compression of ef- ficient private local randomizers. In International Con- ference on Machine Learning, pp. 3208-3219. PMLR, 2021.
Liu, Y., Chen, W.-N., Ozgur, A., and Li, C. T. Universal exact compression of differentially private mechanisms. Advances in Neural Information Processing Systems, 37: 91492-91531, 2024.
Gasull, A. and Utzet, F. Approximating mills ratio. Journal of Mathematical Analysis and Applications, 420(2):1832- 1853, 2014.
Rudin, W. al. Principles of mathematical analysis, vol- ume 3. McGraw-hill New York, 1964.
Guo, C., Chaudhuri, K., Stock, P., and Rabbat, M. Privacy- aware compression for federated learning through numer- ical mechanism design. In International Conference on Machine Learning, pp. 11888-181111 11904. PMLR, 2023.
Safaryan, M. and Richtárik, P. Stochastic sign descent methods: New algorithms and better theory. In Interna- tional Conference on Machine Learning, pp. 9224-9234. PMLR, 2021.
10

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Seide, F., Fu, H., Droppo, J., Li, G., and Yu, D. 1-bit stochas- tic gradient descent and its application data-parallel distributed training of speech DNNs. In Fiffeenth Annual Conference of the International Speech Communication Association, 2014.
Zhu, L., Liu, Z., and Han, S. Deep leakage from gradients.
In Advances in Neural Information Processing Systems, 2019.
Shah, A., Chen, W.-N., Balle, J., Kairouz, P., and Theis, L. Optimal compression of locally differentially private mechanisms. In International Conference on Artificial Intelligence and Statistics, pp. 7680-7723. PMLR, 2022.
Sun, T, Wang, Q. Li, D., and Wang, B. Momentum sures convergence of signsgd under weaker assumptions. In International Conference Machine Learning, pp. 33077-33099. PMLR, 2023.
Tang, Z., Wang, Y., and Chang, T.H.. z-signfedavg: A unified stochastic sign-based compression for federated learning. In Proceedings of the AAAI Conference on Arti- ficial Intelligence, volume 38, pp. 15301-15309, 2024.
Triastcyn, A., Reisser, M., and Louizos, C. Dp-rec: Pri- vate & communication--fficeent federated learning. arXiv 2021.
preprint arXiv:2
Wang, Z., Song. M., Zhang, Z., Song, Y., Wang, Q., and Qi, H. Beyond inferring class representatives: User-level privacy leakage from federated learning. In IEEE INFO-
COM 2019-IEEE conference computer communica- lions, pp. 2512-2520. IEEE, 2019.
Xiang. M. and Su, L. Distributed non-convex opti- mization with one-bit compressors heterogeneous data: Efficient and resilient algorithms. arXiv preprint arXiv:22
arXiv:2210.006654 20.220.00000 20665v2, 2023.
Xiao, H., Rasul, K., and Vollgraf, R. Fashion-min mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1708.07747, 2017.
Yue, K., Jin, R., Wong, C.-W., Baron, D., and Dai, H. Gradi- obfuscation gives false sense of security in federated learning. In 32nd USENIX Security Symposium (USENIX Security 23), pp. 6381 1381-6398, 2023.
Zheng, Q., Dong, J., Long, Q., and Su, W. Sharp compo- sition bounds for gaussian differential privacy via edge- worth expansion. In International Conference on Ma- chine Learning, pp. 1 11420-11442 1435.. PMLR, 2020.
Zheng, S., Huang, Z., and Kwok, J. Communication- efficient distributed blockwise momentum SGD with error-feedback. In Advances Neural Information Pro- cessing Systems, pp. 11446-11456, 2019.
Zhu, J. and Blaschko, M. B. Improving differentially private sgd via randomly sparsified gradients. Transactions on Machine Learning Research, 2023.

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
A. Proofs
A.I. Proof of Theorem
Lemma 3. (Neymnn-Pearsen Lemma (Lehmann et al., 2005)) Let P and Q be probability distributions on Q with densities
P and 9. respectively. For the hypothesis testing problem Ho vs H1 Q, test Φ Q - [0, the most powerful test at level if and only if there are two constants h E [0, + and y [0, 1] such that & has the form
1, q(ar)
p(z) > h
7, p(z)
((x)
h
(35)
if ((x)
< h,
pla)
and Er((] = a. The rejection rule suggests that Ho is rejected with probability of 6(x) given the observation x.
In the following, we show the f-DP of the sign-based compressor.
Theorem 1. Suppose that Pmax + Pmin = 1, and p+1(x) p+i > The sign-based compressor is fNaisySign (a)- differentially private with
1
Baax at for E [0. Pminl:
NoissSSggn (a)
Pmnn
(36)
Pmin
Pman a, for a E [Pmino 1]. Peaxr
Pmas
Proof. Let Y NoisySign(z' PP41.P-1) ( and NoisySiggnz,, P41,11))))) we have
P(Y = -1) D-1(2')
P(X -1) (=)
(37)
P(Y = 1) p+1
P(X 11 P+1
When x > , can be observed that p(-=-1) in Lemma 3, and therefore
P(Y=1)
In this case, when a E (0,)-1(x)], we set -(X=-1)
P(Y=-1)
P(X=-1
P(==I]
Eplo] = >P(X = -1)) =
(38)
and
gr2d' (a) 1 Roll PP( = - =1 1 P-1(2') gg
(39)
p_1(z)
When a E [p-1(x),11, we set h P(Y=1) P(X=I) in Lemma 3, and therefore
Ep(d) P(X- 1) >P( p- (721 a,
(40)
and
Ba>da - P(Y = -1) -PY 1) (+1("')) - (2+) = =p+i(x') a x-p-1(x)
=1
P+1
(x').
P+1(z)
(41)
In summary, we have
1 p 1(a")
for a [0))-1(2)],
p p-1(2) a,
382d (a)
(42)
P+i(#') P11(2)
(+)("')
a (-) 1].
Pii(m)
When x < x', it can be observed that P(Y P(X=-)
1
In this case, when a E (0, we set P(X=1)
P(Y=1)
P(Y=1) in
P(X=1]
Lemma 3, and therefore
Eplo] = 7PX 1) (x+ = =a,
(43)
and
B gree' (a) = 1 - -Eolo) = 1 >P(Y = 1) = -1==)) = P+1 a. p+1 (x)
(44)
When E [1+1(1), 1], we set h r(Y=-1) in Lemma 3, and therefore
PX=
E Ep(Ø) = P(X X = + P(X -1) (+) - a,
(45)
12

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
and
a- P+1 p+1(2)
83 (a)= =1 1- -B = P(Y > -p) -p-1 ---
p p-1 (2')
p- p-1(x)
(46)
In summary, we have
P(i( a, for E [0.p+1 p-1(w") p-1(z') P-1(2) p-1(z) 04 for (2),
1 P+i(x()
8a (a)
(47)
The infimum of 3r>=' (a) is attained when p=1(x') Pmar and p-1(z) = Pminn while the infimum of 3 (a) is attained when P+1 (1²) Pmaz and (xr) = Pminn As a result, we have
Pmas at,
for a E [0, Pmin]:
NNoisySign =
Pmni
(48)
Ponin
Punin for E [pmin 1]:
Pmaz
Pmaz
which completes the proof.
A.2. Proof of Theorem 2
Theorem 2. For any vectors and x' with ||0||2, ||'|| C, the tradeoff function (GNS(a) for the corresponding
hypothesis testing problem satisfies
(a) d=oc Gy(a) = Φ (1 a) -M).
(49)
in which y is the limit of pa with
2C
Pd
(50)
V
2
C
Vida
der
Proof. In the vector case, we consider higher dimensional hypothesis testing problem given by Ho : z ~ P Pi x P2 x ... x Pa.
(51)
H1 :1:2~0 ~ Q = Q Q2
Qa-
[1 9:(x1)
in which p.(-) and (.) denote the probability density functions of P. and Q; respectively, and x = [z1. #2, Zel is the output of the mechanism. Similar to (Jang et al., 2024), the maximize of the privacy loss is given by x - Vd
Let Ta(z) = log
[T (z.)
According to the Neyman-Pearson lemma (Lehmann et al., 2005), the most powerful test at level a is a thresholding function of Ta()). Following the results in (Zheng et al., 2020) and (Dong et al., 2021), this is equivalent to applying some thresholding function h(a)) to the normalized statistic Ta(x) (r i.c., Ho is rejected if v [[ar)
Ta(z) Ep [Ta(2) h(a)..
(52)
Warr [T(22]]
Let Fa(-) be the CDF of Talz) [e((a)) Varr [T]]]] when is drawn from P, i.c., Fa(h) Pp Ta(x) Br s hn. By
(arrn(Ta(=)
the Lyapunov central limit theorem, En [T(=)]
converges in distribution to the standard normal random variable
/ /arrl/aa(>))
(Billingsley, 2017). Similarly, the normalized statistic v [aro
Bo(((a)) for Q also converges in distribution to the
standard normal random variable. Let Fa(h) = Po
Tu(z)- Eg [+)=)] < h
v Varra (=)
Given the above results hand, the type I erroo rate is given by
Ta(z) Ep [[a(2)]
IPp
> h
= -1 Fa(h)) a,
(53)
v Varp [a(z)]
13

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
and the type II error rate is given by
Ta(z) - Ep [T([)]] Po
Ta(z) Eg [Ta(2)]
S hh Eo [Ta())] - Ep [T(z)]]
<
PQ
f(a)).
(54)
Varr [Ta(2]]
Varp [Ta(=)]
Warp [Ta(z)]
Since f is symmetric, we can readily find that Varp [Ta(2)] = Varq [Ta(z]] (Dong et al., 2019; Zheng et al., 2020). As a result,
Ta(z) Eq [Ta(2)]
I hh I2 [Ta(z)] - Ep [Ta())]
f(a) = Pe
v Varq [Ta(z)]
Vare [T(2))
(55)
(1 EQ [T(2)] Ep [Ta(T)))]
= Fd
v Varq [Ta(z)
Since both Fa(-) and Fa(-) converges in distribution to (.)) when d increases, essentially have M(x) - G,((a) $ (1 - aa) -4),
(56)
in which is the limit of pa with
EQ [a(=)] Ep [Ta(z)]
Pd
(57)
v Varq [T(2)]
In the following, we consider two input vectors a and a' such that || S and ||ا||| S C, and x is the output of the NoisySign compressor with z P the input vector x and ~ Q otherwise. In this case, we have
Ep [a(z)] =
Σ
E2
log
+
log
(58)
E
22
+
log
log
Eq [Ta()]]
Σ
④
log
log
(59)
x
x
log
log
+p
Therefore,
x
EQ [T((z]] Ep [Ta(=)] =
Σ
x
x;
log
(60)
+
m
22
On the other hand, we have
x
x
+b
Varq [Ta(z)] Σ +
Φ
log
(61)
As result,
log
Na EQ [2(2)] Ep [T(2)]]
(62)
/Varq [Ta(2)]
5
log
2
Plugging x'
C. into (62) yields Va"
14

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
① C Vio
(-v2c)
C
vd
Ad 0 [Ta(2)) Ep [Ta(2] Varq [T]=)]
vda
(63)
C
C
vita
ddd
The mean value theorem (Rudin et al., 1964) implies that Therefore, we conclude that
x
1
+
|ar/
(64)
o
2n
2C
S
(65)
2
Φ
(-vvar
C
Viler
ddr
which completes the proof.
A.3. Proof of Theorem 3
Theorem (Convergence of NoisySign SGD with Scheme I). Suppose Assumptions 1-4 are satisfied, and the learning
rate is set as VTLd' T
Then by running Algorithm 2 for T iterations, we have
(F(w)(0)
F*) TPdddd2TDDD + VT
VLdv 2T +0 C. )
T Σ
obpp)
(66)
2VT
Before proving Theorem 3, we first show the following lemma.
Lemma 4. For any [-c, c) and app > G, we have
Elsign (I + ((0,
JDPV2T I + A,
(67)
and
B [lssign (x + (r), - E[sign (x + 1
(68)
in which A 0
Dpp
Proof.
Elsign (x + (())
+
ODP
ODP
DD
2
1
DDF
2
e
T
dt
E
7
dt
22
2
dl
2
DDF
30
x
dt
(69)
V2T
k
DDF
2k 2
PDP
dl
2T
PDF
k=
I 2k+1
"DP
+
2T
2T
24 24k + +1)
kk
DDP
3
P. +
0
ODPV 2n
DP
15

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
in which we utilize the Taylor expansion of e 2 Moreover,
E
sign (xr + ((, - Elsign (r +N ((0,)
Elsign (a + NO OD))]] + + (-aop) |1 Elsign (æ +N(00,DP)]]
1
ODP
x
+ [ sign (x +N(
(70)
ODP
ODP
Elsign (a + +(0,
CDP
= - (B[siigm (x + N(0, dDDD) 1
which completes the proof.
Given Lemma 4, we are ready to prove Theorem 3,
Proof. According to Assumption 2, we have
F(w((t)) (t+))) (t)
L (((+1) (0) + 7 [1
$ (VF(w(())
20
=- (
1
Σ
sign + nm))
+ 1 TM
Σ
sign(g (t)
+ nm
2
(71)
M
MEH
mEH
Ldn²
$ ())
Σ
sign(g! (t) + nm))
+ 2
M
mEH
Taking expectations on both sides yields E[F(w((+1) (()(
sign(g!! (t) + nmm) )
Ldn?
s -nE
V (F (1),
Σ
+
M
2
mER
|
(1)
Σ
Im
(
1
Σ
Am m
+
Ldn2
DDV 2T M
M
2
MEH
mEH
2
VF VF (w0 (1) (1)
11 -
VF (9)
1
Σ Am
)
Ldvi
(72)
-1|
ODPV2T
M
2
2
())
11- +
17
(F((0(0))
1|2
V2TODP
Σ Am
Ldn²
2P 2m -]
2
2
DDPV2T 2m
2
M
mEH
2
11-
C
Ldr2
(z (1)
+
n
+
ODPV 2m
DP
in which Am = A A,,, A m,2,
Am.d) with A Am.i = O
Vi, and we utilize the fact that - < a. ><
111 +
[bl..
Adjusting the above incquality and averaging both sides over = 1,2, ... ,T, we can obtain
Σ |F( ()) ((w JoDPV 2T + Ld LdV22noDP + c
(73)
Tn
16

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Letting 1 VETa gives
E (1) - ((w(t+1)) I
VLdV2RODP
c
+0
(74)
VT
2/T
DP
(F F* FV Ldy 2TODP
VLdV2TODP
+0
c
+0
VT
2VT
bp
which completes the proof.
B. Proof of Theorem 4
Theorem (Convergence of NoisySign SGD with Scheme II). Suppose Assumptions 1-4 are satisfied, and the learning rate set as 17 VTLd Then by running Algorithm 2 for T iterations, we have
1
(F(w
VTT
VLd
ØDrdV2r
2m
211
+o ca
(FF(w()) -
+
T
T
2VT
VM
VM
(75)
0
+ 0
ODP
||
+
M
VM
DP
Proof. According Assumption 2, we have F(w((+1)) - (!)
< (VF(w(()) (((+1) - (00 + 2
(w - 200
=-n (t), sign
1
Σ
sign(g (t) + nmm))
M
mE#
+ 2
18sggn
sign(g (1) nmm)
(76)
M
mER
Ldn2 2
<
1
VF(w (.)
sign
Σ
sign(g nm))
M
mER
Ldn²
d
= (1
+
2
+ 2m
(F(w(())) x sign( + Emex signio!") +n
()m (sign (VFo)))((ii(((((()))))))))))))))
where VF(w()), is the i-th entry of the vector (((((() and is the learning rate. Taking expectations both sides yields
B[F(w((+1)) - ((w(
Ldn²
< S-nl[VF(urr (1) )
(77)
d
+ 2m
V (F(
sign
Σ
(o (0) + mm)) # sign (ign(VF((w()))))
M
m
mEH
17

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
In addition,
sign
1
Σ
sign(gm. (1)
+ mmm)) # sign sign((F((w()))))
M
mEt
P
sign
Σ
sign(gm. (0)
+ Bm)) sign
2T
2
VF(wo())))
M
MER
P
sign (1) nm)
(m.i
2
VF(w(");
2
2
VF(
DDPV2T 2m
JDPV2T
MEH
E
M EMEN sign 9 m,t + nmm) dDpv2n VF(w(())
1
VF(w(()))
(78)
@DPV2T
E
M mE (i (g m + Pmm) N E
mEH
E sign(g + nmm)
(t)
(F(w(())
ØDPV2x
E
M MEN
signig (t)
1 m.j + n
M
EmEn SorVz (9)
9m.
@DPV25 VF (F(((())
mEN onpv2x E
mm
oDr
VF(20(0)))
+
V ((w(())
vDDV
For each term above, we have
sign(g (1) + nmm)
Σ
sign(g (1) + mm))
M
M
me H
mEH
2
sign(gm. + nm)
1
Σ
sign(g (1) + nm))
M
M
MEH
mEH
(79)
12
E
sign(g (t) +nm)
Σ MEH
E
sgg (t) + 1mm))
MEH
Σ
E
sign(gm. (1) nmm) E signig (1) + nm)) 11²
d
M
VM
18

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
d
2
VF(w
2
Σ
mm
DDV
2m
DDPV2T 2T
MEN
2
VF(w(t));
M Σ
DDPV 2x
DDP 2n
m.a
MEH
E
VF((u(t));
M Σ
(
0 ODP 2
QDPV 2n
m.
MEH
(80)
E
Σ
V Fmm(((()))
Σ
2
2
M
2D
M
aDPV
2n
mz
mEH
MEH
M
E
ODPV 2m
2
VFm(w()))
ODP 2T
2
9
m
(8)
[2
mEH
L.
1
M
QDPV2T
ODPV 2TM
2
and
E
Σ
E
sign(g (0)
+ nm)
M mEH
1
Σ
DDPV2
2
Im,i
(t)
50
c
(81)
MEH
Plugging (8)),,,),, and (81) into (77) yields
B[F(w((+1)) (1)
< < + Ldn
20
c²
DDPV2T
+ 21
VM +
+
2
OP
2
(82)
Ldn
0ppdy 2T
2
c²
(1) = = V
+
+
+
2
VM
VM
T
Adjusting the above incquality and averaging both sides overt 1,2, T, we can obtain
T
(83)
(LF(w(()) ((
Ldnj
appdV2T 2m
2 2
c
+
+0
T
VM
VM
DP
Letting 17 VLTd and dividing both sides by 1 gives
VF w (9)
(w)
((t()
LLd
0DrdV22
2110 +o
(84)
VT
2VT
VM
VM
(F( LLL
VLd
@DPdV2T 2T
2|102111
+
c
)
+
VT
2VT
V
VM
0
which completes the proof.
C. Details of the Implementation and Additional Results
Our experiments are mainly implemented using Python 3.8 with packages Numpy 1.19.2 and Pytorch 1.10.I.
19

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Probabiiiy Wronn Aggrogation
Probability Wioon Aggregation
0.56
0.54
0.40
0.52
0.35
0.50
0.30
0.48
0.25
0.46
Sin L-Noi sySign
0.44
G-NolsySign
0.15
L-NoisySign
0.42
10
Ogr
(a) Theterog
(b) Theterog
Probabiltt Wrong Aggregatin
G-NoisySign
Wrang Aggregation
G-NoisySign L L-NoisySign
NoisySign
0.7
0.7
0.6
Probabiiey
0.4
0.3
10
dgr
(c) Wheterog
(d) Theterog
Figure 4. The comparison of the probability of wrong aggregation between G-NoisySign and L-NoisySign with 10. A set of 10 workers considered, with 2m 1)), row, Theterog and Theterog = respectively. For the left and right figures in the second row, Theterog 5 and Theteroy = 10, respectively.
and xm. ([Thetrrr 1) otherwise. For the left right figures first
C.1. Dataset and Pre-processing
We perform experiments on standard Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky et al., 2009) datasets. The Fashion-MNIST dataset consists of 60,000 training samples and 10,000 testing samples. Each sample is 28x28 size gray-level image. We normalize the data by dividing it by the max RGB value (i.e., 255.0). The CIFAR-10 dataset contains 50,000 training samples and 10,000 testing samples. Each sample is 32x32 color image. The data normalized with a zero-centered mean.
C.2. Additional Results
C.2.1. ADDITIONAL RESULTS FOR SECTION 4
We conduct additional experiments examine the impact of data heterogeneity. In Figure 4, set of 10 workers is considered, with Z.m (-1,, 1) for m 7 and
N (Xhheterog: 1) otherwise. It can be observed that when the data distribution is less heterogeneous (i.c., Theterog 1). L- L-NoisySign outperforms G-NoisySign since the vanilla SIGNSGD converges well and Gaussian noise tends to result in larger variance than Logistic noise with the same privacy guarantees. When the data distribution becomes more heterogeneous, G-NoisySign outperforms L-NoisySign for an appropriate o aDp. The crossover happens when DD larger for more severe data heterogeneity. This validates that G-NoisySign may be more suitable for heterogeneous cases. We further consider set of 10 workers, with Fm. for < 7 and Zm Theterog otherwise, and the results presented in Figure 5, which agree with those in Figure 4.
C.2.2. ADDITIONAL RESULTS FOR SECTION
Figure 6 presents the convergence of the algorithms with respect to the communication rounds. Note that compared to Gaussian noise (i.e., DP-SGD), G-NoisySign and L-NoisySign reduce the communication overhead from the workers to the server by a factor of 32, while the majority vote variants further enjoy improvement in communication efficiency from the server to the workers.
20

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Probability of Wroo Aggregation
1.0
NaisySign
0.9
L-NeisySign
Probability Wrong
0.8
0.2
0.7
0.1
0.6
G-NoitySign
L-NolsySign
0.5
0.0
10
12
Ppr
Opr
(a) Theteroy
(b) Pheterog
3
Probabiityy Wrong Aggregation
Pobabillty of Wrong Aggregation
1.0
NoisySign
0.9
G NoisySign
L-NoisySign
L-NoisySign
0.8
0.7
0.6
0.5
0.3
dpe
Theterog
(d) Theteroy
Figure 5. The comparison of the probability of wrong aggregation between G-NoisySign and L-NoisySign with = 10. A set of 10 workers considered, with Zmm 1 for 7 and Z' Theterog otherwise. The results agree with those in Figure
40
45
35
40
Test Accuracy
30
35
25
Gaussian Noise G-NoisySign
30
Gaussian Noise
G-NolsySign
20
G NoieySiggnVaar L-NoisySign
NaisySign
15
L-NoisySign
NoisySSgnnVoot
15
NaisySign
10
10
100
200
300
300
400
500
Communication Rounds
Communication Rounds (b) 1.6
(a) / 0.8
Figure The convergence curve of the algorithms on CIFAR-I0 with E (0.8, 1.6).
We note that the composition property in Lemma 2 suggests that, for the same overall privacy guarantee, utilizing the privacy amplification effect of s-gm(-) allows for = 1.5x training steps with the same Gaussian noise variance per step. Therefore, in Table 3, we add two more baselines: (1) G-NoisySign without utilizing the privacy amplification analyses (i.c., adding Gaussian noise with the same variance as DP-SGD); (2) G-NoisySign that runs 320 rounds (slightly more than 500 2/a rounds) instead of 500 rounds. can be observed that G- G-NoisySign and G-NoisySign- Vote outperform the two additional baselines in all the examined privacy budgets, which validates that the privacy amplification indeed leads to improvement in test accuracy.
In Table 4-5, present the results for less heterogeneous data distribution, with 100 and the remaining settings the same as Table 1-2. In Table 6, we perform experiments on Fashion-MNIST with 5 workers selected in each communication round. It can be observed that G-NoisySign and L-NoisySigg achieve performance comparable to the Gaussian mechanism all the examined scenarios.
21

---

Noisy SIGNSGD Is More Differentially Private Than You (Might) Think
Table 3. Fashion-MNiSS Test Accuracy for Varying Privacy Requirements Per Communication Round = 0.1)
0.04
0.08
0.4
0.8
1.6
GAUSSIAN NOISE
43.78 1.98%
58.69 + 1.48%
73.48 + 0.49%
77.17 + 0.51%
79.90 + 0.25%
G-NOISYSIGN
45.24 = 2.51%
58.46 = 2.48%
73.78 + 0.57%
77.20 = 0.29%
79.57 = 0.57%
G-NOISYSIGN
40.94 = 4.49%
54.49 = 2.68%
72.71 + 0.68%
76.15 + 0.46%
78.70 = 0.65%
(320 ROUND)
G-NOISYSIGN W.O.
37.36 4.07%
52.06 + 2.54%
72.83 0.62%
76.49 + 0.43%
79.11 + 0.45%
PRIVACY AMPLIFICATION
G-NOISYSIGN- VOTE
42.18 4.03%
56.59 = 1.91%
73.23 0.66%
76.47 = 0.61%
79.27 0.37%
G-NOISYSIGN-VOOT
35.79 5.61%
49.85 + 2.65%
71.69 0.64%
75.17 + 0.39%
78.01 + 0.60%
(320 ROund)
G-NOISYSIGN- SINVVEE W.O.
38.00 5.26%
49.85 + 3.22%
71.64 + 0.83%
75.84 + 0.55%
78.52 + 0.39%
PRIVACY AMPLIHICATION
L-NOISYSIGN
42.52 3.11%
58.39 - 1.53%
73.89 0.78%
77.18 + 0.31%
79.66 - 0.45%
L-NOISYSIGN-VON VOTE
40.46 3.82%
53.89 = 1.82%
73.23 0.47%
76.49 = 0.31%
79.24 0.31%
Table 4. Fashion-MNIS" Test Accuracy for Varying Privacy Requirements Communication Round (a 100)
0.04
0.08
0.4
0.8
1.6
GAUSSIAN NOISE
45.47 + 3.25%
59.21 = 2.25%
74.29 = 0.42%
77.57 + 0.23%
80.31 + 0.27%
G-NOISYSIGN
45.46 - 3.08%
59.84 = 2.40%
74.64 = 0.34%
77.61 0.44%
80.24 0.22%
G-NOISYSIGN- VOTE
42.42 3.40%
57.32 3.42%
73.60 + 0.29%
77.18 0.30%
79.81 + 0.228
L-NOISYSIGN
45.26 3.19%
59.43 2.51%
74.91 0.55%
77.69 + 0.55%
80.28 0.23%
L-NOITYSIGN-VOTE
42.80 = 2.77%
55.42 2.56%
73.32 = 0.72%
77.00 + 0.32%
79.80 + 0.22%
Table CIFAR-10 Test Accuracy for Varying Privacy Requirements Per Communication Round (a 100)
0.8
1.6
4
8
16
GAUSSIAN NOISE
41.24 1.21%
48.60
0.53%
56.44 = 1.12%
63.63
0.79%
66.35 + 1.12%
G-NOISYSIGN
40.18 + 0.89%
47.90 0.64%
57.24 + 1.01%
63.18 + 1.27%
67.23 + 1.38%
G-NOISYSIGN-VOL VOTE
38.98 = 0.75%
0.67% 46.50
55.60 0.68%
61.87 - 0.91%
L-NOISYSIGN
40.39 + 0.97%
48.28
0.66%
57.73 + 0.93%
62.45 + 1.13%
66.82 1.71%
L-NOISYSIGN-VOTE
38.88 = 0.74%
46.76 1.02%
55.74 1.03%
61.65 + 1.20%
65.93 + 0.82%
Table Fashion-MNIST Test Accuracy for Varying Privacy Requirements with 5 workers selected Per Communication Round (a = 0.1)
1
0.04
0.08
0.4
0.8
1.6
GAUSSIAN NOISE
27.90 + 3.69%
43.00 = 3.63%
69.06 = 0.98%
73.15 + 0.60%
76.06 + 0.97%
G-NOISYSIGN
28.53 +: 4.42%
42.67 3.23%
68.93 + 1.33%
73.26 0.87%
76.37 + 0.59%
G-NOISYSIGN- VOTE
24.39 3.57%
37.81 2.08%
67.20 1.02%
72.33 0.78%
7..60
L-NOISYSIGN
25.86 - 4.71%
42.44 -2.5%%
68.78 = 1.13%
73.18 0.96%
76.31 0.70%
L-NOISYSIGN-VOL
24.17 = 4.75%
37.46 4.09%
66.92 1.25%
72.34 1.01%
75.69 + 0.55%
22


Reviews:
[{"review_id": "9XTPN2HISm", "reviewer": "Reviewer_AkDc", "summary": "This paper considers the privacy guarantees of Noisy SignSGD, an algorithm that adds noise to a value, then releases its sign.\nIt is shown that releasing the sign of the value, rather than the noisy value itself, amplifies the privacy guarantees.\nA method of majority vote for aggregating the sign gradient is also proposed.\nNumerical experiments confirm that the proposed method, despite its biased nature, is on-par with the classical DP-SGD algorithm.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer AkDc,\n\nWe appreciate your time and effort in reviewing our paper and providing constructive comments. Please find the response to the comments below.\n\n**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.\n\n**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$. \n\n**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\\%.\n\n**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.\n\n**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.\n\n[R1] X. Zhang, et al. Understanding clipping for federated learning: Convergence and client-level differential\nprivacy, ICML 2022.\n\n[R2] X. Chen, et al. Understanding gradient clipping in private SGD: A geometric perspective, NeurIPS, 2020\n\n**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. \n\n**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.\n\n**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.\n\n**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.\n\n[R3] M. Abadi, et al. Deep learning with differential privacy. ACM SIGSAC conference on computer and communications security, 2016.\n\n[R4] Q. Zheng, et al. Federated f-differential privacy. AISTATS, 2021\n\n[R5] J. Dong, et al. Gaussian differential privacy. Journal of the Royal Statistical Society: Series B, 2022\n\nWe hope that your comments have been addressed adequately. Please let us know if there are any questions.", "claims_and_evidence": "Theoretical claims are provided with full proofs, and empirical claims are in line with the empirical results.", "methods_and_evaluation_criteria": "Benchmark datasets and the used baselines make sense.", "theoretical_claims": "Not in all details, but derivations presented in the main text seem correct.", "experimental_designs_or_analyses": "Experimental design is rather sound, with reasonable choice of datasets and problems and a wide range of hyperparameter choice.\n\nHowever, clipping threshold is set arbitrarily to $C=1$ or $C=2$, which may have an important impact on the behaviour of the algorithm, especially since it relies only on the sign.\n\nThe statement \"We run all the algorithms for 5 repeats and present the best results\" is slightly concerning, as it is a bit unusual in my opinion.\nGenerally, one would rather report the average and standard deviation rather than maximum and standard deviation.", "relation_to_broader_scientific_literature": "Related work with respect to sign SGD and to differential privacy are discussed.", "essential_references_not_discussed": "Not to my knowledge.", "other_strengths_and_weaknesses": "**Strengths**\n1. The paper shows that Sign SGD can enhance privacy guarantees, which is in line with the intuition that releasing only the sign can improve privacy guarantees as less information is released.\n2. Numerical experiments show that the proposed methods is on par with DP-SGD for a given privacy guarantee.\n\n**Weaknesses.**\n1. While it is shown that privacy guarantees are amplified, the amplification is rather small. This should rather be referred to as a \"tighter evaluation of the privacy of sign SGD\" rather than proper amplification. This is in line with Figure 1, which shows that the analysis is tighter rather than shows amplification (e.g. with noise to add divided by the magnitude of the gradient).\n2. Majority voting as an aggregation procedure is interesting, but almost systematically decrease accuracy in experiments, which is a bit disappointing.\n3. Theoretical guarantees for noisy sign SGD are rather weak, and do not account for clipping, although one could expect that clipping has a somewhat important impact on the result. \n4. Experiments only highlight marginal improvement from sign SGD in comparison with DP-SGD with Gaussian noise. Moreover, step size is heavily tuned: in sign method, this may lead to \"guessing the scale of the gradient by hyperparameter tuning\". Tuning this hyperparameter may have less impact on DP-SGD.", "other_comments_or_suggestions": "It seems that sign SGD could allow gradients not to be clipped before applying the sign function.\nFor instance, one may add noise to the gradient (possibly using the gradient's scale). This does not provide privacy in itself, but this could be enforced later using mechanisms like randomized response to perturb the sign of the gradient.\nThe resulting procedure could allow to give DP guarantees without requiring to know the scale of the gradient before-hand.\nAs such, no clipping is required when computing the gradient, while privacy is preserved by randomized response.\n\nI understand this is a complicated question, and mention this as a potential direction for future research, but would it be the case that randomizing the sign of the algorithm could further improve the privacy guarantees and help to have additional amplification?", "questions_for_authors": "1. It seems that \"amplification\" is rather small: are there settings where one can obtain arbitrarily large gains, or is amplification bounded by a constant factor? (In which case I would rather talk about \"tighter analysis of DP guarantees of noisy SignSGD\".)\n2. How important is the hyperparameter tuning step for noisy Sign SGD, in comparison with DP-SGD? In particular, is one of the two algorithms more sensitive to hyperparameter tuning than the other?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "jLQnit5Nvf", "reviewer": "Reviewer_Jupt", "summary": "SignSGD is a technique to compress a gradient in order to reduce its communication cost. It is typically applied in decentralized or federated SGD where the transmission of gradients is a regular operation. The key idea behind it is to transmit the sign of each component, reducing the communication cost to one bit per dimension. \n\nThe paper studies the differential privacy (DP) guarantees of SignSGD. Current techniques to make SignSGD differentially private rely on the addition of noise before compression. They focus on making the uncompressed gradient differentially private which, by post-processing, implies the differential privacy guarantees of the compressed gradients. However, these techniques ignore  the privacy amplification obtained by the sign compression. The current contribution quantifies this amplification, showing that less noise is required to obtain DP, which results in more accurate models. \n\nUnder the framework of $f$-DP, the paper shows that Noisy SignSGD using Gaussian or Logistic noise achieves similar performance than the uncompressed version despite the 32x improvement factor in compression.\n\n## update after rebuttal\nAuthors have clarified my concerns. Therefore I keep my score supporting acceptance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Jupt,\n\nWe appreciate your time and effort in reviewing our paper and providing a positive evaluation. Please find our point-by-point response below.\n\n**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. \n\nOn 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.\n\nWe will add a literature review and the corresponding discussions in related works in the revised version.\n\n**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.\n\n**Third sentence of the abstract:** We will revise and break it down into two sentences for clarity.\n\n**The font size of Figure 2:** We will revise accordingly. \n\nWe hope that your comments have been addressed adequately. Please let us know if there are any questions.", "claims_and_evidence": "Appropriate theory and experiments back the claims of the paper.", "methods_and_evaluation_criteria": "The evaluation setting is reasonable for the current problem.", "theoretical_claims": "I have checked the proofs of Theorems 1 and 2, which seem correct.", "experimental_designs_or_analyses": "The experiment design is reasonable. However, it would have been more informative to show the convergence across iterations to have an impression of the convergence speed of the evaluated techniques instead of just the final accuracy in Table 1.", "relation_to_broader_scientific_literature": "The paper seems to reasonably address its relation with respect to sign based compressors. However, it does not position itself with respect to other compression techniques under privacy constraints such as [R1-R5] listed below. \n\nReferences: \n\n[R1] Triastcyn, Aleksei, Matthias Reisser, and Christos Louizos. \"Dp-rec: Private & communication-efficient federated learning.\" arXiv preprint arXiv:2111.05454 (2021).\n[R2] Bassily, Raef, and Adam Smith. \"Local, private, efficient protocols for succinct histograms.\" Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015.\n[R3] Feldman, Vitaly, and Kunal Talwar. \"Lossless compression of efficient private local randomizers.\" International Conference on Machine Learning. PMLR, 2021.\n[R4] Shah, Abhin, et al. \"Optimal compression of locally differentially private mechanisms.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n[R5] Liu, Yanxiao, et al. \"Universal exact compression of differentially private mechanisms.\" Advances in Neural Information Processing Systems 37 (2024): 91492-91531", "essential_references_not_discussed": "To the best of my knowledge, there are no essential references missed in the paper.", "other_strengths_and_weaknesses": "I have enjoyed reading the paper. It is in general well written and provides clear explanations of each key concept.", "other_comments_or_suggestions": "I have only minor comments: \n- The third sentence of the abstract is a bit long and complicated. It could be reformulated for clarity\n- The font size of Figure 2 is too small and should be increased", "questions_for_authors": "Please address the broader positioning to other privacy preserving compressors mentioned in the review.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iknoOFfeWw", "reviewer": "Reviewer_t9hH", "summary": "This paper investigates how sign-based gradient compression–specifically, Noisy signSGD–can inherently amplify differential privacy. \nIn a distributed learning scenario, the authors introduce theoretical analysis for the privacy guarantees under the f-DP framework and compare to two variants: G-NoisySign and L-NoisySign.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer t9hH\n\nWe appreciate your time and effort in reviewing our paper and providing constructive comments. Please find our point-by-point response below.\n\n**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.\n\n**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.\n\n**Additional experiments**: We perform additional experiments on FMNIST with $\\alpha = 100$ to simulate homogeneous data, and the results (10 repeats) are given below.\n\n|$\\mu$|0.04|0.08|0.4|0.8|1.6|\n|--------|-------|-------|-------|-------|-------|\n|Gaussian Noise|$45.47\\pm3.25\\\\%$|$59.21\\pm2.25\\\\%$|$74.29\\pm 0.42\\\\%$|$77.57\\pm0.23\\\\%$|$80.31\\pm 0.27\\\\%$|\n|G-NoisySign|$45.46\\pm3.08\\\\%$|$59.84\\pm2.40\\\\%$|$74.64\\pm0.34\\\\%$|$77.61\\pm0.44\\\\%$|$80.24\\pm0.22\\\\%$ \n|G-NoisySign-Vote|$42.42\\pm3.40\\\\%$|$57.32\\pm3.42\\\\%$|$73.60\\pm0.29\\\\%$|$77.18\\pm0.30\\\\%$|$79.81\\pm 0.28\\\\%$\n|L-NoisySign|$45.26\\pm3.19\\\\%$|$59.43\\pm2.51\\\\%$|$74.91\\pm0.55\\\\%$|$77.69\\pm0.55\\\\%$|$80.28\\pm0.23\\\\%$\n|L-NoisySign-Vote|$42.80\\pm2.77\\\\%$|$55.42\\pm2.56\\\\%$|$73.32\\pm0.72\\\\%$|$77.00\\pm0.32\\\\%$|$79.80\\pm0.22\\\\%$\n\nWe also perform more experiments on CIFAR-10 (5 repeats due to limited time) with $\\alpha = 100$.\n\n|$\\mu$|0.8|1.6|4|8|1.6|\n|--------|-------|-------|-------|-------|-------|\n|Gaussian Noise|$41.31\\pm1.11\\\\%$|$48.67\\pm0.41\\\\%$|$56.65\\pm0.92\\\\%$|$63.95\\pm0.86\\\\%$|$67.07\\pm1.30\\\\%$|\n|G-NoisySign|$40.47\\pm0.78\\\\%$|$48.13\\pm0.78\\\\%$|$57.48\\pm1.03\\\\%$|$63.41\\pm0.45\\\\%$|$67.21\\pm0.50\\\\%$ \n|G-NoisySign-Vote |$38.91\\pm0.44\\\\%$|$46.75\\pm0.59\\\\%$|$55.87\\pm0.67\\\\%$|$61.67\\pm1.09\\\\%$|$66.38\\pm0.69\\\\%$\n|L-NoisySign|$40.85\\pm0.33\\\\%$|$48.55\\pm0.50\\\\%$|$57.32\\pm0.91\\\\%$|$62.63\\pm1.15\\\\%$|$67.79\\pm0.75\\\\%$\n|L-NoisySign-Vote|$39.08\\pm0.68\\\\%$|$46.45\\pm1.07\\\\%$|$55.10\\pm0.90\\\\%$|$62.06\\pm0.53\\\\%$|$65.70\\pm1.00\\\\%$\n\n**Fewer workers**: We perform more experiments on FMNIST (10 repeats) with 5 workers selected in each round with $\\alpha = 0.1$.\n|$\\mu$|0.04|0.08|0.4|0.8|1.6|\n|--------|-------|-------|-------|-------|-------|\n|Gaussian Noise|$27.90\\pm3.69\\\\%$|$43.00\\pm3.63\\\\%$|$69.06\\pm0.98\\\\%$|$73.15\\pm0.60\\\\%$|$76.06\\pm0.97\\\\%$|\n|G-NoisySign|$28.53\\pm4.42\\\\%$|$42.67\\pm3.23\\\\%$|$68.93\\pm1.33\\\\%$|$73.26\\pm0.87\\\\%$|$76.37\\pm0.59\\\\%$ \n|G-NoisySign-Vote| $24.39\\pm3.57\\\\%$ |$37.81\\pm2.08\\\\%$|$67.20\\pm1.02\\\\%$|$72.33\\pm0.78\\\\%$|$75.60\\pm0.85\\\\%$\n|L-NoisySign|$25.86\\pm4.71\\\\%$|$42.44\\pm2.95\\\\%$|$68.78\\pm1.13\\\\%$|$73.18\\pm0.96\\\\%$|$76.31\\pm0.70\\\\%$\n|L-NoisySign-Vote|$24.17\\pm4.75\\\\%$|$37.46\\pm4.09\\\\%$|$66.92\\pm1.25\\\\%$|$72.34\\pm1.01\\\\%$|$75.69\\pm0.55\\\\%$\n\nIt can be observed that G-NoisySign and L-NoisySign attain comparable performance with the Gaussian mechanism in all the experiments above.\n\n**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.\n\n**Number of repeats & essential references:** We will increase the number of repeats and add the reference as suggested in our revised version.\n\nWe hope that your comments have been addressed adequately. Please let us know if there are any questions.", "claims_and_evidence": "Privacy amplification via compression: The paper rigorously shows that the act of discarding the gradient magnitudes via the sign operator amplifies differential privacy. In the theoretical analysis, the authors derive tight privacy bounds that quantify this effect.", "methods_and_evaluation_criteria": "The methods and the experimental results are appropriate to the problem at hand. However, the number of repeats (5) is small for generalization.", "theoretical_claims": "All the theoretical analyses are well written; however, the reviewer raises an issue in the error analysis (lines 233-), the comparison of the **estimation error**. For more details, please refer to the additional comment section.", "experimental_designs_or_analyses": "In the experiments, the authors show that the proposed approach achieves the privacy-utility trade-off comparable to the classical DP-SGD. The experimental design makes sound.", "relation_to_broader_scientific_literature": "There have been many papers for DPSGD and signSGD. The reviewer thinks that this paper provides a very tight bound for the DP + signSGD.", "essential_references_not_discussed": "The key contribution of this work is to propose f-DP-based federated learning. Since the idea of the f-DP with federated learning is also discussed in the paper below, the reviewer recommends to cite one additional paper. \n\n```\n@inproceedings{zheng2021federated,\n  title={Federated f-differential privacy},\n  author={Zheng, Qinqing and Chen, Shuxiao and Long, Qi and Su, Weijie},\n  booktitle={International conference on artificial intelligence and statistics},\n  pages={2251--2259},\n  year={2021},\n  organization={PMLR}\n}\n```", "other_strengths_and_weaknesses": "**Strengths**: This paper provides a tight bound based on the neyman-pearson Lemma. Due to the tight bound, the proposed method in the experimental results achieves (or outperforms) the DP-SGD, whereas previous studies have a slightly lower accuracy compared to the DP-SGD. \n\n**Weakness**: Despite their theoretical contributions, the performance gap between the proposed method and the baselines are marginal/", "other_comments_or_suggestions": "- I think the analysis with the linear mean estimation (Eqs. (14)-(16)) is not an appropriate method because it is not optimal. For example, if we have $E[f(x)] = x + 0.1 x^2$, $x\\in[0,1]$, we may not treat the $x^2$ term as an error. If we use a proper linear estimator, the relative magnitude of the second term in the mean is not an error. \n- In Figure 3, like dithering, a proper amount of the additive noise is helpful for successful aggregation. In that situation, the aggregation is always wrong if $\\sigma_{DP}$ is near zero. Inversely, it seems like G-NoisySign offers larger noise std compared to L-NoisySign if $\\sigma_{DP}$ is small. Can you please add a discussion for this result?\n- Also, regarding Figure 3, the reviewer suggests adding figures for more general cases. Ex)10 workers are selected for each round, $x_m=-1.0 + \\mathcal{N}(0,1)$ for $m<7$ and $x_m= -1.0 + \\mathcal{N}(0,1)$ o.w.\n- The reviewer suggests the authors add **more repeats** for the experimental results. \n- The authors mentioned that the G-NoisySign is more suitable for distributed learning with heterogeneous data. The reviewer suggests adding experimental results for **the homogeneous dataset (i.i.d.) setting** for verification, like Tables 1 and 2.\n- The reviewer suggests adding more results with a smaller number of participating workers. For example, 5 workers are participating in each communication found, like Tables 1 and 2. \n- (Optional) Consider deeper neural networks with more complex datasets (e.g., cifar100).", "questions_for_authors": "- In the numerical results (e.g., table 1), they said that they run all the algorithms for 5 repeats and **present the best results**. What is the correct one.. However, it seems like **mean accuracy** is reported. The reviewer guesses they run 5 repeats and present the mean results and the error bar (std) of the results. Is it really the best results with 5 repeats?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VBIKEYvmKU", "reviewer": "Reviewer_nyXX", "summary": "The authors study the privacy benefits of the map $sign(x)$ when combined with additive Gaussian noise in the Noisy SIGNSGD algorithm. They show that since $sign(x)$ drops the magnitude information, it indeed “amplifies” the privacy. The results show that the use of logistic noise may not be superior to using $sign(x)$ with additive Gaussian noise as reported in prior works when such a privacy amplification effect is considered. The claim is supported by both theoretical analysis and experiments on image classification tasks.\n\n## update after rebuttal\n\nI thank the authors for their explanation. I have no further questions, and I will keep my rating. I do think adding the comparison and discussion in the related works will further improve the manuscript.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear reviewer nyXX\n\nWe appreciate your time and effort in reviewing our paper and providing a positive evaluation. Please find our response below.\n\n**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. \n\nOn 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.\n\nWe will add a literature review and the corresponding discussions in related works in the revised version.", "claims_and_evidence": "Yes. I find the main claim is well supported.", "methods_and_evaluation_criteria": "Yes. The main claim on the privacy benefits of $sign()$ is well supported by not only theoretical analysis but also numerical results to illustrate the resulting privacy bound compared to the one leveraging logistic noise.", "theoretical_claims": "I did not check the proof in the appendix but the proof sketch provided in the main text makes sense to me.", "experimental_designs_or_analyses": "The experiment results show that using Noisy SignSGD can give comparable utility while saving 32x communication overhead since only one bit is transmitted.", "relation_to_broader_scientific_literature": "The finding is quite generic. Given that 1-bit quantization (i.e., signSGD) is indeed important in some settings, I believe the result of the paper can benefit the community.", "essential_references_not_discussed": "I wonder how the Noisy SignSGD  (i.e., 1-bit compression) is compared to the sketching-based approaches, such as [1] and the relevant literature? I feel it is interesting to also see the trade-off along the communication complexity aspect in greater detail. Nevertheless, I think it is also fine to just focus on the Noisy SignSGD-based method. This question is just out of curiosity. \n\n### References\n[1] Optimal compression of locally differentially private mechanisms, Shah et al. AISTATS 2022.", "other_strengths_and_weaknesses": "The paper is well-written, and the problem is very well-motivated. While the analysis is not super technical, I like the fact that the authors summarized their ideas in a way that the general privacy audience can understand. It is a joyful read for me. I do not find any major weaknesses in the work.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Maybe the question is out of the scope, but I wonder how Noisy SignSGD, especially when adopting the improved privacy analysis from the authors, compared to the sketching-based approaches? What is the corresponding privacy-utility-communication trade-off? It is totally fine if the authors cannot answer this question for now, but I feel this is a very interesting question to think about for distributed learning with DP constraints in general.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper analyzes a noisy variant of SignSGD that adds Gaussian noise for differential privacy before applying sign compression. The authors show that the sign operator enables slightly stronger privacy guarantees than standard post-processing. Most reviewers found the setting and results interesting, though they requested clarifications on several points. The rebuttal addressed many of these concerns and included new experiments demonstrating utility gains from the improved analysis, directly responding to one of Reviewer AkDc’s key concerns.

Considering the reviews, rebuttal, and discussion, I find this a solid contribution and recommend acceptance.
Decision: Accept (poster)