$z$-SignFedAvg: A Unified  Stochastic Sign-based Compression for Federated Learning
Authors: Zhiwei Tang
Yanmeng Wang
Tsung-Hui Chang
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated averaging
compression
communication efficiency
signSGD

Abstract: Federated Learning (FL) is a promising privacy-preserving distributed learning paradigm but suffers from high communication cost when training large-scale machine learning models.  Sign-based methods,  such as SignSGD \citep{bernstein2018signsgd},  have been proposed as a biased gradient compression technique for reducing the communication cost. However,  sign-based algorithms could diverge under heterogeneous data, which thus motivated the development of advanced techniques, such as the error-feedback method and stochastic sign-based compression, to fix this issue.
Nevertheless, these methods still suffer from slower convergence rates. Besides, none of them allows multiple local SGD updates like FedAvg \citep{mcmahan2017communication}.  In this paper,  we propose a novel noisy perturbation scheme with a general symmetric noise distribution for sign-based compression, which not only allows one to flexibly control the tradeoff between gradient bias and convergence performance, but also provides a unified viewpoint to existing stochastic sign-based methods.  More importantly,  we propose the very first sign-based FedAvg algorithm ($z$-SignFedAvg). Theoretically,  we show that $z$-SignFedAvg achieves a faster convergence rate than existing sign-based methods and,  under the uniformly distributed noise, can enjoy the same convergence rate as its uncompressed counterpart. Last but not the least,  we remark that adding random noise to the local gradients has a double benefit: it protects the clients' privacy by, e.g., the Differential Privacy. Extensive experiments are conducted to demonstrate that the $z$-SignFedAvg can achieve competitive empirical performance on real datasets. 

Under review as a conference paper at ICLR 2023
2- Z-SIGNFEDAVG: A UNIFIED STOCHASTIC SIGN-BASED COMPRESSION FOR FEDERATED LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Federated Learning (FL) is a promising privacy-preserving distributed learning paradigm but suffers from high communication cost when training large-scale machine learning models. Sign-based methods, such as SignSGD (Bernstein et al., 2018), have been proposed as biased gradient compression technique for reducing the communication cost. However, sign-based algorithms could diverge under heterogeneous data, which thus motivated the development of advanced techniques, such the error-feedback method and stochastic sign-based compression, fix this issue. Nevertheless, these methods still suffer from slower convergence rates. Besides, none of them allows multiple local SGD updates like FedAvg (McMahan et al.) 2017). In this paper, we propose a novel noisy perturbation scheme with a general symmetric noise distribution for hign-based compression, which not only allows one to flexibly control the tradeoff between gradient bias and convergence performance, but also provides unified viewpoint existing stochastic sign-based methods. More importantly, the unified noisy perturbation scheme enables the development of the very first sign-based FedAvg algorithm (>-SignFedAvg) to accelerate the convergence. Theoretically, we show that z- SignFedAvg achieves faster convergence rate than existing sign-based based methods and, under the uniformly distributed noise, can enjoy the same convergence rate as uncompressed counterpart. Extensive experiments are conducted demonstrate that the z-SignFedAvg can achieve competitive empirical performance on real datasets and outperforms existing schemes.
INTRODUCTION
We consider the Federated Learning (FL) network with one parameter server and clients (McMahan al. 2017 Li et 2020a), with the focus on solving the following distributed learning problem
min f(x) = - PER
- f((x),
fi(x)
where fe(-) is the local objective function for the i-th client, for i 1,..., n2. Throughout this paper, we assume that each fi is smooth and possibly non-convex. The local objective functions are generated from the local dataset owned by each client. When designing distributed algorithms to solve (.. a crucial aspect is the communication efficiency since massive number of clients need to transmit their local gradients the server frequently (Li et al., (020aa. As of the most popular FL algorithms, the federated averaging (FedAvg) algorithm (McMahan et al. 2017 Konečný et al. 2016) considers multiple local SGD updates with periodic communications to reduce the communication cost. Another way is to compress the local gradients before sending them to the server (Li et al. 2020a] Alistarh et al., 2017, Reisizadeh et al.) 2020). Among the existing compression methods, simple yet elegant technique to take the sign of cach coordinate of the local gradients, which requires only one bit for transmitting each coordinate. For any æ E R, we define the sign operator as: Sign(x) = 1 if x 2 0 and -1 otherwise.
has been shown recently that optimization algorithms with the sign-based compression can en- joy great communication efficiency while still achieving comparable empirical performance as uncompressed algorithms (Bernstein et al.] [2018) Karimireddy et al., 2019) Safaryan & Richtárik 2021). However, for distributed learning, especially the scenarios with heterogeneous data, i.e.,

---

Under review as a conference paper at ICLR 2023
fi * fy for every i + j. naive application of the sign-based algorithm may end up with divergence (Karimireddy et al. 2019 Chen et al.) 2020a Safaryan & Richtárik (021).
A counterexample for sign-based distributed gradient descent. Consider the one-dimensional problem with two clients: milgERR (x A)2 (æ - A)2. where A >> 0 is some constant. For any E (-,,,, A], the averaged sign gradient is Sign(æ: A) + Sign (x: A) 0, i.e., the algorithm never moves. Similar examples are also discussed by (Chen et al. [2020a] Safaryan & Richtárik 2021). The fundamental reason for this undesirable result is the uncontrollable bias brought by the bign-based compression.
There are mainly two approaches to fixing this issue the existing literature. The first one the stochastic sign-based method, which introduces stochasticity into the sign operation (Jin et al. 2020
Safaryan &Richáárik] 2021 Chen et al.] 2020a), and the second one is the Error-Feedback (EF) method (Karimireddy al. 2019; Vogels et al. 2019 Tang et al., 2019). However, these works are still unsatisfactory. Specifically, on one hand, both the theoretical convergence rates and empirical performance of these algorithms are still worse than uncompressed algorithms like (Ghadimi & Lan 2013] Yu et al. 2019). On the other hand, none of them allows the clients to have multiple local SGD updates within one communication round like the FedAvg, which thereby are less communication efficient. This work aims at addressing these issues and closing the gaps for sign-based methods.
Main contributions. Our contributions are summarized as follows.
(1) A unified family of stochastic sign operators. We show an intriguing fact: The bias brought by the sign-based compression can be flexibly controlled by injecting a proper amount of random noise before the sign operation. In particular, our analysis is based on a novel noisy perturbation scheme with general symmetric noise distribution, which also provides a unified framework to understand existing stochastic sign-based methods including (Jin et al., 2020 Safaryan Richtárik [02T Chen et al.) 2020a).
(2)
The first sign-based FedAvg algorithm. In contrast to the existing sign-based methods which do not allow multiple local SGD updates within one communication round, based on the proposed stochastic sign-based compression, we design a novel family of sign-based federated averaging algorithms (z-SignFedAvg) that can achieve the best of both worlds: high communication efficiency and fast convergence rate.
(3) New theoretical convergence rate analyses. By leveraging the asymptotic unbiasedness property of the stochastic sign-based compression, we derive series of theoretical results for z-SignFedAvg and demonstrate its improved convergence rates over the existing sign- based methods. In particular, show that by injecting sufficiently large uniform noise, z-SignFedAvg can have a matching convergence rate with the uncompressed algorithms.
Organization. In Section 2, the proposed general noisy perturbation scheme for the sign- ign-based compression and its key property, i.c., asymptotic unbiasedness, are presented. Inspired by this result, the main algorithms are devised in Section 3 together with their convergence analyses under different noise distribution parameters. We evaluate our proposed algorithms on real datasets and benchmarks with existing sign-based methods in Section Finally, conclusions are drawn in Section 5
Notations. For any x E Rd, we denote =r()) as the j-th element of the vector x. We define the 4n-norm for p 2
||~|| j |)) We denote that || || || 112, and || maxje(f1..... [.) For any function f(r), we denote f(x)(z) as its k-th derivative, and for a vector (x(1) xr (d)) T E IRd, we define Sign(r) = [Sign(x(1)). Sign(z(d)))
1.1 RELATED WORKS
Stochastic bign- method. Our proposed algorithm belongs to this category. Among the existing works (Sataryan & Richtárik 2021 Jin et al. 2020 Chen al. 2020a), the setting considered by (Sataryan& & Richtárik (222)) is closest to ours since the latter two consider gradient compression not only the uplink but also in the downlink. Despite of this difference and the use of different convergence metrics, the algorithms therein achieve the same convergence rate O(r-1), where is the total number of gradient queries to the local objective function. Compared to existing works, our proposed z- z-SignFedAvg requires a slightly stronger assumption on the mini-batch gradient noise, but achieves a faster convergence rate O(7 ( 4) or even O(7 $), with the standard squared L no-morm of gradients the convergence metric.
2

---

Under review as a conference paper at ICLR 2023
Error-Feedbact method. The error-feedback (EF) method is first proposed by (Seide et al. 2014) and later theoretically justified by (Karimireddy et al. 2019). Then, (Vogels et al. 201 9 Tang et al. 2019 2021a) further extended this EF method into distributed and adaptive gradient schemes. The key idea of the EF-based methods is to show that the sign operator scaled by the gradient norm is a contractive compressor, and the error induced by the contractive compressor can be compensated. However, such EF-based methods cannot deal with partial client participation otherwise the error residuals cannot be correctly tracked. Besides, the EF-based methods have a convergence rate 3 + + d'r '), where is the dimension of the gradients, and therefore is not competitive for high-dimension problems.
O
Unbiased quantization method. Apart from the sign-based gradient compression, another popular way of compression is the unbiased stochastic quantization method adopted by (Alistarh et al. [017] Reisizadeh et al.) 2020 Haddadpour et al. 2021). A key assumption made by this category of methods is that the quantization error is bounded by the norm of the input, which however does not hold for bign-based compression, and therefore the existing convergence results therein do not apply to sign-based methods. Besides, as shown in (Alistarh et al. 2017 Reisizadeh et al.) 2020), these methods usually have degraded convergence speed when fewer quantization bits are used.
As mentioned, some of the existing sign-based methods like (Chen al.. 2020a Safaryan & Richtárik 2021) do not adopt the standard squared f2-norm of gradients as the metric for the convergence rate analysis. Thus, it is tricky make a fair comparison between them and the proposed z-SignFedAvg In Appendix A we provide a detailed discussion and summarize the convergence rates of some representative algorithms in Table 2
SIGN OPERATOR WITH SYMMETRIC AND ZERO-MEAN NOISE
In this section, we introduce a general noisy perturbation scheme for the sign-based compression and analyze the asymptotic unbiasedness of compressed gradients. The results serve as the foundation for the proposed algorithms subsequent sections.
Key observation. Let & be random variable that is symmetric, zero-mean and has the p.d.f p(t). If p(0)= * and p(t) continuous and uniformly bounded on (-o0, +o0), then it holds that
a-+ p(0) J. p(t)dt= =d
lim to 2p(0) R[Sign(æ + aE)] = lim
In other words, the perturbed sign operator is an asymptotically unbiased estimator of the input x when oc. Furthermore, assume that p(t) is uniformly bounded on (-o0, +00) and differentiable for an arbitrary order. Then, with the Taylor's expansion, we can have o Jo² p(t)dt = z + p(O]
(k+1)lo* = x Et (0)0 (o-*). Therefore, suppose that K is the largest integer such that (0)) - O...,, (0)
p(0) E (0)2+))
The LHS of (2) will converge to x with the order (k+1).. This observation motivates us propose the following family of noise distribution parameterized by a positive integer: z E Z4.
Definition (z-distribution). A random variable & is said to follow the z-distribution if its p.d.f
2x
(1(
21}=
where 71 2 (1 (1+g0 1 and [(z)= So +o0 f--1e dtt is the Gamma function.
It can be verified p. (t) in B is valid p.d.f. When 1, it corresponds the standard Gaussian distribution. In addition, one can also show that (1) converges to the p.d.f of the uniform random variable the interval [-1, 1] when = - +oo (see Lemma in Appendix BB. This z-distribution has a nice property that can be leveraged to bound the bias caused by the bagnd compression, as stated in the following lemma.
Lemma 1. For any E R and > 0.
||
1s+2
| (Sigu(x + oEx)] -
(4)
4(2z + 15
where E1(1),..,, (dd follow the i.i.d. z-distribution.
3

---

Under review as a conference paper at ICLR 2023
Remark 1. One can that the RHS of 4 involves the term (||=]| /0)) Thus, long as
a >> || the LHS of (4) converges to zero when & - +o0. Since Lemma 2 implies that Eso follows the i.i.d uniform distribution on |-1,1] is interesting to remark that the stochastic sign operators proposed in Jiin et al. 2020 Safaryan & Richtárik 2 are exactly the sign operator injected by the uniform noise, and (Chen et al. 2020a
obtain oE [Sign(x + xā
long as > | oc-
also considered the use of a symmetric noise for gradient perturbation. Thus, sign-based compression with the z-distribution offers unified perspective to understand the relationship among the existing stochastic
methods.
3 2-SIGNFEDAVG ALGORITHM
In this section, based on the analysis Section 2 we propose the following sign-based FedAvg algorithm, termed as e-SignFedAAg. While FedAvg-type algorithms with gradient compression are also presented in (Haddadpour et al. 202T), they require unbiased compression and are not applicable to sign-based methods. The details of z-innneeAAvg are presented in Algorithm [] A prominent difference between the proposed z-SignFedAvg and the existing sign-based methods lies in that clients are allowed to perform multiple SGD updates per communication round (E > 1) before applying the stochastic sign-based compression. Like the FedAvg algorithm, is anticipated that z-SignFedAvg can greatly benefit from this and has significantly reduced communication cost.
Note that in practice we only consider z 1 and z +oo for the z-SignFedAvg since they correspond to the Gaussian distribution and uniform distribution, respectively. Nevertheless, we are interested in the convergence properties of 2 z-SignFedAvg for a general positive integer 2 as provides better insights on the role of for the convergence rate.
Algorithm 2- evd (or 2 2-SignSGD when E 1)
Require: Total communication rounds T. number of local steps E, number of clients n, clients stepsize server stepsize 7/ noise coefficient o, parameter of noise distribution
I: Initialize 27-
for = 1 to T do
3: On Clients:
4: for = 1 to do
5: 44-1,0 2:-1
6: for to F. do
7:
gi- = 1, where ge(:) the mini-batch gradient oracle of i-th client.
8:
- कं 1, 791 1,a-
end for
11-1-2t-110 + o5s
10:
Ai-1 Sign
where where (.(1), ((() (f()) i.i.d.
11:
Send Ai-1 to the server.
12: end for
13: On Server:
14: Jt Ft-1 77 E Ai
15: Broadcast zy to the clients.
16:
end for
17:
return 27.
We first state some standard assumptions for problem I
Assumption 1. We assume that each fe(x)) has the following properties:
A.I We can access mini-batch gradient oracle that is unbiased and has bounded variance, i.e., E[gs(x)] = V fx)) and EEllg: - ff((x) <²
A.2 Each fi is smooth, i.e., for any x,y E Rd. there exists some non-negative constants Li.... Las such that f fx) < (V)()). x) E. L((())=(j))*
A.3 There exists some constant f such that [(x) 2 f Va E Rd.
A.4 There exists a constant G such that [+)(( < G. Vi 1, ..., n, and gd Assumption A.2 more fine-grained assumption on the function smoothness than the commonly used one and is also used by (Bernstein et al. 201 8: Safaryan & Richtárik 202T). For the convergence rate analysis, we consider two cases, namely, the case with z +00 and the case of oc.
4

---

Under review as a conference paper at ICLR 2023
3.1 CASE 1:
to0
As we can see from Lemma 1 there always exists some gradient bias when < +00. In order to bound it, we further assume that a higher order moment of the mini- mini-batch gradient noise is bounded. Assumption 2. There exists constant Q= 2 0 such that for any I E IRd, we have
(c) V fe(()) 12422 I Q2-
(5)
Theorem 1. Suppose that Assumption
7 and hold. Denote Di.s Ei= sh and Linax max; Teg. Then, for 1j = 1]=0, 7 S Lmaa and z < +00 in Algorithm
1 we have
E
21 (1r)) - -1 7
(E 1)EL max (C2 G2)
TE Σ
TEy
n
(a) Standard terms in FodAvg
(6a)
2 E V22 G4+t2 12* (Q= + G+2+2) L
V2(2z + 1)02=
2(2z + 1)204=
Bias
(6b)
4 70² ビj=1 Lا
(6c)
En
(c) Variance term
When is the bound non-trivial? Since we assume that the &2-norm of gradient is bounded by G, all the terms in the RHS of (6 should be no larger than G For example, to have the first term in (6b)
less than G², one requires to be greater than 21+ de E (Q./G + G*=) /(22 + 1)
Bias-variance trade-off. An interesting observation from Theorem is that there exists a trade-off
between the bias and variance terms. One can see that the terms in (ob) is caused by the gradient bias of the sign operation (see (4) and an infinitesimal of a with O o 2²), while the term in (6c) is due to the injected noise and is in the order of O (yo²). Specifically, the first term in (6b) only depends the noise scale a and mostly affects the final objective. Meanwhile, the variance term in (6c) mainly affects the convergence speed because a smaller stepsize is required for to diminish.
Theoretically, can choose iteration- dependent noise scale so as to make the algorithm converge to a stationary solution. To see this, let us denote T = TE as the total number of gradient queries per client, and present the following corollary.
Corollary (Informal). Let 7 = min ( 2577, Lmbx] and a = (nT) in Theorem | and e12
let F <
1r+2 7 1542, We have
E MΣ
E
IV 1=
=0 ((nt)- -xÍx)=
Achieveing linear speedup. From Corollary | we can see that the z-SignFedAvg needs (nr) ax42 communication rounds to achieve a linear-speedup convergence rate. Particularly, when z = 1, the corresponding convergence rate is (((nr) $) and the required communication rounds is (nT) To the best of our knowledge, the previous works have never shown the sign-based method can achieve a linear-speedup convergence rate.
Relationship to (Chen et al., (2020a). The work (Chen et al. 2020a) also considered the use of a symmetric and zero-mean noise for the sign-based compression and proved that the algorithm has convergence rate ( 4)). However, their results have three differences from z-SignFedAvg and Theorem M First, (Chen et al.) 2020a) considered gradient compression both in the uplink and downlink communications. In addition, the convergence metric they used is not the standard squared norm of gradients and is hard to interpret. Second, their analysis is rooted in the median median-based algorithm, whereas we judiciously exploit the property of the sign operation and hence provide general analysis framework for the stochastic sign-based methods. Last but not the least, unlike our z-SignFedAvg, (Chen al. 2020a) cannot allow multiple local SGD updates.
5

---

Under review as a conference paper at ICLR 2023
3.2
CASE 2: t00
When 2 +00, the injected noise & in the z-SignFedAvg is uniformly distributed on [-1. 1]. From Remark [] we have learned that the gradient bias can vanish as long as the noise scale sufficiently large. To quantify this threshold, we need the following assumption which is a limit form
of Assumption 2
Assumption 3. There exists constant a 2 0 such for any E RR, with probability 1,
l19.(x) Vi(i))l & Qx0
(8)
Theorem 2. (Informal) Suppose that Assumption 1 and hold. For min min -mmaa 1 we have
+00, E S n 7 and
E(G + 2x)) ) in Algorithm
([( =0 ((
E
(9)
==
However, if S E(G+ 2oo), there exists problem instance for which Algorithm ! cannot converge. Remark Note that Theorem Sennrem@immn iimplies that oo-Sign SigAAe has matching convergence rate as the uncompressed FedAvg. The reason why so-SignFeAAvg cannot converge when E + Qxx is simply that the uniform noise has a finite support and cannot always change the sign of gradients. For example, if for some A >> 0, then we have Sign(x + oE...) Sign(z) for any x 2 A.
Relationship to (Jin et al., 2020; Safaryan & Richtárik, 2021). As mentioned in Remark both the stochastic sign operators in (Jin et al. 2020 Safaayan & Richtárik] (02T) are equivalent to the sign operator injected by the uniform noise. Nevertheless, there are still two distinctions when compared with our oo-SignFedAvg. First, while (Safaryan Richtárik, (02I)) shows their
algorithm has a O(T 1) convergence rate, it is based on the εz-norm of gradients and cannot imply
the same rate that in O (see Appendix [A]. Second, although (Safaryan & Richtárik 2021) does not need Assumption 3 it relies on an input-dependent noise scale which, unfortunately, often slows
the algorithm convergence in practice especially when the problem dimension is large.
More theoretical results and proof's are relegated to Appendix and C Below, we have two more remarks.
Table Comparison of Case and Case 2.
Convergence rate
Threshold
Assumption gradient noise
Case
Remark 3. (Bounded minibatch gradient noise) While both As- slightly stronger than the commonly used second-order condition the minibatch gradient noise, they are still justifiable since unbounded minibatch gradient noise is rarely to happen in practice.
< +:00 O(r 2
ō ((* ( + d
Assumption
sumption 2 and
2 +00
O O(T-
Ö(Q
Assumption
Remark 4. (Minibatch gradient noise works as noise perturbation) When the minibatch gradient is used as the input of the sign operator in (2). the minibatch gradient noise itself may function as the perturbation noise. In particular, as shown in (Chen et al.) (0200) the minibatch gradient noise approximately follows symmetric distribution. Therefore, in practice large noises as suggested by Theorem 2 since the minibatch gradient noise can also help mitigate the bias due to sign-based compression. This also explains why small noise scale is sufficient for 2 e-SignFedAyy to achieve good performance in the experiment section.
may not need to inject as
3.3 COMPARISON OF CASE AND CASE 2
We summarize the results of Case and Case 2 in Table I where Ö(.) hides some constants that do not affect the comparison. Especially, we can see that when the manc-batch gradient noise has a long tail such that Q./G & Q4=, Case 1 requires a less amount of noise than Case 2 for guarantecing convergence. Despite of the difference in theory, we will see in Section 4 that z-SignFedAvg under Case and Case 2 have almost the same behavior in practice.
3.4 IMPLICATION ON DIFFERENTIALLY PRIVATE FEDERATED LEARNING (DP-FL)
Beyond the convergence issue, remark that adding Gaussian noise to the local gradients is also a common practice for privacy protection, especially in DP-FL (Geyer et al. 2017 Agarwal et al.)
2021 2018). With this observation, it is straightforward to propose differentially- prrivvate variant

---

Under review as a conference paper at ICLR 2023
of SiggFedAAvg, which term DP- DP-SignFedAvg. More details and comparison results between giggingeed and the uncompressed DP- DP-FedAvg (Geyer et al. 2017 Kairouz et al.) (021 under different privacy budgets are given in Appendix
EXPERIMENTS
In this section, we present the experiment results on both synthetic and real problems, and all the figures in this section are obtained by 10 independent runs and are visualized in the form of medn
Noise scale as a hyperparameter. of 2-SignFedAvg depends on the noise scale in the previous section, we treat a tunable hyperparameter in the experiments. This is because, on one hand, the theoretical lower bound for are difficult to compute since it is impossible to access the moment condition of the minibatch gradient noise. On the other hand, as we have discussed in Remark 4 minibatch gradient noise, we can use much smaller noise scale than the theoretical one in practice.
Although we explicitly characterize how the performance
owing to the presence of the
Aside from the experiments presented in this section, we also compare our algorithm to another popular family of unbiased stochastic compressed FL algorithms, namely, the QSGD in (Alistarh et al. 2017 and FedPAQ in (Reisizadeh et al. 2020). For detailed results, we refer readers to Appendix
4.1 A SIMPLE CONSENSUS PROBLEM
In this section, we verify our theoretical results in Section 3 by considering the simple consensus problem with 10 clients: minggr* 1 Σ || - y:ll² where y/. V/o E IRd are generated using i.i.d standard Gaussian distribution, and d is the problem dimension. We implemented the following algorithms: GD (Gradient descent), Sto Sto-SignGGD (Safaryan & Richtárik 202I]. SignSGD (Algorithm with 1. E and 0), L-SignSGD (Algorithm with 2 and E' = 1.), so-SignGGD (Algorithm [ with = +oo and E = 1). For all the algorithms, we considered the full gradient (no mini-batch SGD), and used the same stepsize 0.01 and initialization by zero vector.
Results. As we can see from Figure T the vanilla SignSGD fails to converge to the optimal solution whereas the others can. Besides, 1-SignSGD and oo-SignSGD have roughly the same convergence speed which is slightly slower than the uncompressed GD. It is also observed that the input-dependen noise scale adopted by (Sataryan & Richtárik 202T) could slow the convergence when the problem dimension is high, as discussed in Section 3.2
Cbccae value
Obpervve valin
GD
SigraGo
Obectre
1-5ig/000 - 2)
StoSign5GD
une Communicatio rOUndS
Communicatio rounds
Commun CeOOn roundS
(a) d = 10
(b) d 100
(c) d 1000
Figure 1: Performance of tested algorithms under diffeernnt problem dimension.
Figure 2 displays the results of 1-SignSGD
0
and oc- -i-SinnSGD with various noise seales. We can see that there is clear bias- variance trade-off for different noise scales and it corroborates our analysis after The-
Cijectvv Vake
0.5
Oijectrv Value
0-2 10
0-2
orem I is also worth mentioning that the best choice of a for Algorithm ( shown in Figure 2 is much smaller than the one predicted by the theorems.
Communiction
sia
20
180
rounds
(a) I-SignSGD
(b) SigSinnGDD
Figure 2: SSgnnSGD under various noise scales.
4.2 2- SIGNSGD ON NON-LLD MNIST
In this section, we consider extremely non-i.i.d setting with the MNIST dataset (Deng 2012), Specifically, we split the dataset into 10 parts based on the labels and each client has the data of one digit only. A simple two-layer convolutional neural network (CNN) from Pytorch tutorial (Paszke et al. (017)) was used for the learning task. The following algorithms were implemented: SGDwM (Distributed SGD (Ghadimi & Lan 2013) with momentum), FFFSSignSGDWM (Distributed
7

---

Under review as a conference paper at ICLR 2023
SignSGD with error-feddbcc and momentum (Karimireddy et al., 2019 Vogels et al. 2019)), ) and
Sto- Soo-SignSGDWM Sto-SiinSGDD with momentum (Safaryan & Richtárik] (022)) )). For each of the algorithms, selected its best hyperparameters, including the stepsize, momentum coefficient and the noise scale, via grid search (see Appendix [.I).
Results. One can observe from Figure 3a 3b that again the vanilla SignSGD does not converge well. The proposed 1 1-SignSGD and co- co-SignSGD clearly outperform the existing EF-SignSGDWM and Hio-SignGGDw, and perform closely to the uncompressed SGDwM. The reason for the slow convergence of Sto-SignSGDw is that the injected noise is too large due to the input-dependent noise scale. Figure 3e further displays the testing accuracy of all methods versus the accumulated number of bits transmitted from the clients to the server. One can see that the proposed algorithms achieve the state-of-the-ar performance on this task. More results for 1-SignSGD and oc-SignSGD under different noise scales are presented in Appendix D.I
SCDwll
Tossing Accurayy
EF SignsDDWM
Thaming lost
Sto SigndDDer
80
8
Siy5500/p 0)
Sgg80DDp
300
100
200
800
503
25 73 10.0 1S0 17.5
lage
+1
(a) Training Loss
(b) Test Accuracy
(c) Test Accuracy w.r.t bits
Figure 3: Performance of various SignSGD algorithms on non-i.i. MNIST.
4.3 2- SIGGNFEDAVG ON EMNIST AND CIFAR-10
In this section, we evaluate the performance of our proposed z z-SignFedAvg two classical datasets: E.MNIST(Cohen) et al. 2017) and CIFAR-10 (Krizhevsky & Hinton 2010). In particular, the proposed and = = a are benchmarked against the uncompressed FedAvg (McMahan ct al. 2017 Yu et al. 2019). Since 1-SignFedAvg and oc-SiinFedAAg behave similarly, we only report the results of SignFedAAg in this section and relegate the others to Appendix [.2] For
Fvd with
EMNIST, we use the same 2-layer CNN as the one in Section 4.2 For CIFAR-10, we used the
ResNet18 (He et al. 2016) with group normalization (Wu & He 2018)
Settings. For both the experiments on EMNIST and CIFAR-10, we followed a setting similar to (Reddi et al., 2020). We also considered the scenario with partial client participation. For the EMNIST dataset, there are 3579 clients in total and 100 clients were uniformly sampled in each communication round to upload their compressed gradients. For the CIFAR-10 dataset, the training samples are partitioned among 100 clients, and each client has an associated multinomial distribution over labels drawn from a symmetric Dirichlet distribution with parameter 1. In each communication round, 10 out of 100 clients were uniformly sampled. The same noise scales for I-SignFedAAv and oo-SiinFedAAv were used: = 0.01 for EMNIST and o = 0.0005 for CIFAR-10. More details about the hyperparameters are referred to Appendix D.2
Results. We can see from Figure 4 and Figure Sa that both uncompressed FedAvg and 1-SignFedAvg can benefit from multiple local SGD steps. More surprisingly, I-SignFedAvg can even outperform the uncompressed FedAvg. This is probably because the EMNIST dataset is less heterogeneous than the used in Section 44.2 The results on the performance of 1-SignFedAvg and oo-SignFedAvg under various choices of noise scales are relegated to Appendix D.2 which are also consistent with our theoretical claims in Section
20
Testing Testing-ccce Accuracy
Tooding Ausumcy
Fiddong of
1.
Fecchag i
22
Feddyn 25
1.0
Feehug
Sign (f 10t
05
Feddug - 20)
60
Sight Eddiug
logCommuntttion rounds
kgCooruntaaion rounds
logTTronsmmmad
Bits der diene
(a) Training Loss
(b) Test Accuracy
(c) Test Accuracy w.r.t bits
Figure Performance FedAvg and 1-SignFedAvg on the EMNIST dataset.
8

---

Under review as a conference paper at ICLR 2023
Festlp 0f
8.75
Te5tn Accumm
Teasire Accunacy
2 1.00
Festleg (1
3.Rgr 05
1.00
Festla (f 10)
677
3 J-9gr (5-
0d0
1100
2000
3000
633
5600
1000
2000
3000
400
300
15 15
20
21
22
24
BRA rounds
Communccaion rounds
log
Itgtreeemitedd per cleett
(a) Training Loss
(b) Test Accuracy
(c) Test Accuracy w.r.t bits
Figure 5: Performance of FedAvg and 1-SignFedAvg on the CIFAR-10 dataset.
4.4 PLATEAU CRITERION FOR TUNING THE NOISE SCALE
From previous experiments, we have learned that the noise scale has to be properly chosen for the algorithm to perform well. However, it could be time-consuming to select the optimal noise scale via grid search. Therefore, here we introduce a simple yet useful strategy that can tune the noise scale adaptively during the training process. Eegure@indicatee that the noise scale should plays a similar role as the stepsize when training a neural network: Small noise scale leads to fast convergence at the beginning, while large noise scale guarantees better final performance. This suggests that should use an increasing noise scale during the optimization process. We can also see this from Corollary [ because that the noise scale a is proportional to Besides, it has been shown that the gradients of
neural network tend to he sparser during the training process (Karimireddy et al.) (019). Therefore, as
studied in (Isik & Weissman 2022), from the rate-distortion theoretic aspect, the noise scale should
be increasing as the compression becomes more aggressive. Motivated by all of these insights, we propose the following Plateau criterion for adapting the noise scale.
Plateau criterion. We denote few parameters bound 2 Onii > 0, K E Z4. > O. We first start Algorithm T with a small noise scale mit, i.e., 0 = Tiis and then update the noise scale via a = _a, where 3 E [1.5, 2]. whenever the objective function stops improving for π communication rounds. We stop updating a it has already been greater than a relatively large number Tbound-
Results. We demonstrate the efficacy of the Plateau criterion by comparing the performance of SSignSGDDI-Signeeddaal
with the optimal noise scale found in previous experiments and the ones with Plateau criterion. Figure shows the results under the three different settings used in Section 4.2 and 4.3 We can see that, the Plateau criterion could results in a slower convergence speed than the optimal noise scale in the middle phase of optimization, because it requires some time for the algorithm to adapt to a suitable noise scale. But eventually it can lead to the same objective value obtained by using the optimal noise scale. For more details like the hyperparameters for Plateau criterion and the evolution of noise scale, we refer readers to Appendix D.3
1-SgrSGD(e - 0.05)
1-Signf addugyplina..
23
1.8ggFodAugg pittesu
1-Signiiosuugla 0.01)
1.3
1-8ggiFoduugle 0.00051
Tranin lxs
1-1
100
200
30.0
432
1
2331
2000
300
4XD
MED
Communicatin rounds
Iog(Communicaion rounds + 1)
Communicatoon rounds
(a) Non-ii.d MNIST
(b) EMNIST
CIFAR-I0
Figure 6: Evaluating the efficacy of Plateau criterion three different datasets.
CONCLUSION
In this work, we have proposed the z-SignFedAvg: a FedAAggtyype algorithm with the stochastic sign- based compression. Thanks to the novel noisy perturbation scheme in Section 2 the proposed z-SignFedAvg provides a unified viewpoint to the existing sign-based methods as well as general framework for convergence rate analysis. Through both theoretical analyses and empirical experi- ments, we have shown that the z-SignFedAvg can perform nearly the same, sometimes even better, than the uncompressed FedAvg and enjoy significant reduction in the number of bits transmitted from clients to the server. As a final remark, the stochastic sign-based compression proposed in this work can be of independent interest and can be conveniently combined with other adaptive FL algorithms or gradient sparsification techniques such as those in (Karimireddy et al.) 2020 Reddi et al. 2020 Basu et al. 2019), to further improve the communication efficiency.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, al. (TensorFlow): system for [Large-Scale] machine learning. In /2th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-283, 2016a.
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016b.
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMahan. cpsgd: Communication-effiiceen and differentially-privnn distributed sgd. Advances in Neural Information Processing Systems, 31, 2018.
Naman Agarwal, Peter Kairouz, and Ziyu Liu. The skellam mechanism for differentially private federated learning. Advances in Neural Information Processing Systems, 34:5052-5064, 2021.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communication- efficient sgd via gradient quantization and encoding. Advances in neural information processing systems, 30, 2017.
Saba Amiri, Adam Belloum, Sander Klous, and Leon Gommans. Compressive differentially-privac federated learning through universal vector quantization. 2021.
Shahab Asoodeh, Jiachun Liao, Flavio P Calmon, Oliver Kosut, and Lalitha Sankar. Thrre variants of differential privacy: Lossless conversion and applications. IEEE Journal on Selected Areas in Information Theory, 2(1 21):2208222, 2021.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas Diggavi. Qsparse-local-se Distributed sgd with quantization, sparsification and local computations. Advances Neural Information Processing Systems, 32, 2019.
Jeremy Bernsteinn Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar, signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pp. 560-569. PMLR, 2018.
Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3): 334-334, 1997.
Zhiqi Bu, Jinshuo Dong, Qi Long. and Weijie J Su. Deep learning with gaussian differential privacy. Harvard data science review, 2020(23), 2020.
Xiangyi Chen, Tiancong Chen, Haoran Sun, Steven Z Wu, and Mingyi Hong. Distributed training with heterogeneous data: Bridging median-and mean-based algorithms. Advances in Neural Information Processing Systems, 33:21616-21626, 2020a.
Xiangyi Chen, Steven Z Wu, and Mingyi Hong. Understanding gradient clipping in private sgd: A geometric perspective. Advances Neural Information Processing Systems, 33:13773-13782. 2020b.
John Chu. On bounds for the normal integral. Biometrika, 42(1/2))263-265 1955.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. 2017 international joint conference on neural networks (IJCNN), pp. 2921-2926 IEEF, 2017.
Laurent Condat, Kai Yi, and Peter Richtárik. Ef-bv: A unified theory of emor feedback and variance reduction mechanisms for biased and unbiased compression in distributed optimization. arXiv preprint 2:XX1:2205.04180 2022.
Li Deng. The mnist database of handwritten digit images for machine learning research [best of the web). IEEE signal processing magazine, 29(6):141-144 2012. 2012.
10

---

Under review as a conference paper at ICLR 2023
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society, 2021.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Found. Trends Theor: Comput. Sci., (3-4))211-400) 2014.
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients-how easy to break privacy in federated learning? Advances in Neural Information Processing Systems, 13:16937-16947, 2020.
Robin C Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv: 1712007577 2017.
Saeed Ghadimi and Guanghui Lan. Stochastic first- and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341 2013. doi 10.1137/12088081
URL https: wtt.:/...///......... 111.1118212108111111 /ttp::///....ooo110..11111111111
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mchrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 1350-2358, PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Yangsibo Huang, Samyak Gupta, Zhao Song, Kai Li, and Sanjeev Arora. Evaluating gradient inversion attacks and defenses in federated learning, Advances in Neural Information Processing Systems, 1472222-7241, 2021.
Berivan Isik and Tsachy Weissman. Learning under storage and privacy constraints. arXiv preprint arXiv:2202.02892. 2022.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for federated learning with theoretical guarantees. arXiv preprint arXiv:2002. 10940, 2020.
Peter Kairouz, Ziyu Liu, and Thomas Steinke. The distributed discrete gaussian mechanism for federated learning with secure aggregation. In International Conference on Machine Learning, pp. 5201-5212. PMLR, 2021.
Leonid Vitalevich Kantorovich and Gleb Pavlovich Akilov. Functional analysis. Elsevier, 2016.
Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In International Conference on Machine Learning, pp. 3252 3261. PMLR, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143, PMLR, 2020.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05492. 2016.
Alex Krizhevsky and Geoff Hinton. Convolutional deep belief networks on cifar-10 10. Unpublished manuscript, 40(7):1-9, 2010.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-65 60, 2020a.
Yiwei LI, Tsung- Hui Chang, and Chong- Yung Chi. Secure federated averaging algorithm with differential privacy. In 2020 IEEE 30th International Workshop on Machine Learning for Signal Processing (MLSP), pp. 1-6. IEEE, 2020b.
11

---

Under review as a conference paper at ICLR 2023
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication--ffiiiienn learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282. PMLR, 2017.
Ilya Mironov. Rényi differential privacy. In 20/7 IEEE 30th computer foundation symposium (CSF), pp. 263-275, IEEE, 2017.
Iya Mironov, Kunal Talwar, and Li Zhang. R enyi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 1908. 10530, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprint arXiv:2003.00295, 2020.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communication-effiiiee federated learning method with periodic averaging and quanti- zation. In International Conference on Artificial Intelligence and Statistics, pp. 2021-2031. PMLR, 2020.
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, pp. 9224-9234. PMLR, 2021.
Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5973-600 6006,, 2016.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- aatta-praalel distributed training of speech dnns. In Fifteenth annual conference of the international speech communication association. Citeseer, 2014.
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochastic gradient descent with double-pass error- prror-compensated compression. In International Conference on Machine Learning, pp. 6155-6165. PMLR, 2019.
Hanlin Tang, Shaoduo Gan, Ammar Ahmad Awan, Samyam Rajbhandari, Conglong Li, Xiangru Lian, Liu, Ce Zhang, and Yuxiong He. 1-bit adam: Communication efficient large-scale training with adam's 's convergence speed. In International Conference on Machine Learning, pp. 10118-10129 PMLR, 2021a.
Zhiwei Tang, Tsung-Hui Chang, Xiaojing Ye, and Hongyuan Zha. Low-rank matrix recovery with unknown correspondence. arXiv preprint arXiv:21 2021b.
Tim Van Erven and Peter Harremos. Rényi divergence and kullback-leibler divergence. IEEE Transactions on Information Theory, 60(7):3997-3820, 2014.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradient compression for distributed optimization. Advances in Neural Information Processing Systems, 32, 2019.
Janny Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal of Machine Learning Research, 22, 2021.
Lun Wang, Ruoxi Jia, and Dawn Song. D2p-fed: Differentially private federated learning with efficient communication. arXiv preprint 2006 2020.
Yanmeng Wang. Yanqing Xu, Qingjiang Shi, and Tsung-Hui Chang. Quantized federated learning der transmission delay and outage constraints. IEEE Journal on Selected Areas in Communications, 40(1 40(1):322 33233333,,4,, 2021.
12

---

Under review as a conference paper at ICLR 2023
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference computer vision (ECCV), pp. 3-19, 2018.
Hao Yu, Sen Yang. and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 5693-5700, 2019.
Xinwei Zhang, Xiangyi Chen, Mingyi Hong, Zhiwei Steven Wu, and Jinfeng Yi. Understanding clipping for federated learning: Convergence and client-level differential privacy. arXiv preprint arXiv:2106.13072 13673, 2021.
Qinqing Zheng, Shuxiao Chen, Qi Long, and Weijie Su. Federated f-differential privacy. In International Conference Artificial Intelligence and Statistics, pp. 2251-2259. PMLR, 2021.
Shuai Zheng, Ziyue Huang, and James Kwok. Communication--ffiiceen distributed blockwise momentum sgd with frror-fee Advances in Neural Information Processing Systems, 32, 2019.
APPENDIX
A COMPARISON WITH EXISTING STOCHASTIC SIGN-BASED METHODS
Table SablleSsummnnn summarizes the key features of few representative stochastic sign-based methods and the proposed z-SignFedAvg, including the convergence rate, metric used in the convergence rate analysis, extra assumptions other than A.1-A.3 in Assumption I and whether the algorithm can achieve linear speedup and allow multiple local SGD steps.
For communication complexity, we focus on the uplink communication cost, i.e., the number of bits transmitted from the clients the server in each communication round. We assume that all the uncompressed algorithms use 32 bits to represent single float number as it is the most common setting in Tensorflow (Abadi et al. 2016a) and Pytorch (Paszke et al. 2017).
While most of the existing methods use the squared f--norm of gradients as the convergence metric, the work (Safaryan & Richtárik] 2021) adopts the f2-norm of gradients. The work (Chen al. 2020a) uses convergence metric mixed with squared fy-norm and & -norm of gradients due to the compression in both uplink and downlink.
Among the works in Table 2] the setting considered by (Safaryan & Richtárik 202 is closest to ours. (Safaryan & Richtárik, 2021 proposed algorithm that achieve the convergence rate O(r 4) with the 22-norm of gradients as the metric. We remark that this is inferior to the convergence rate
(r-2)) 1) with the squared -n-mr as the metric. To illustrate this point, we denote series of vector {ai,.... an. with a, Rdd If now
=
(10)
in the worst case, we can only guarantee that
Σ 1a.l13 ST
ST
1
||a8|||
(11)
As simple example, the equality in holds if and only if there is exactly one non-zero term in {ai,... ).
On the contrary, if it holds that
|a O(7-2),
(12)
13

---

Under review as a conference paper at ICLR 2023
Algorithm
Convergence rate/ metric
Num. per cummun, round
Assumption??
achieve linear speedup?
multiple local steps?
O(r 21 squree 82
Chadimi & Lan
2013
McMalan el 2019
O(r ) squaeed
gradient
Karimiredly et al
2019 O(r
-1)
di + 32
Bounded grodient
x
sqsrred f2
O(T $) 8/
Richnänk k 2021
( +)
Bounded gradient an mumber
Fin ct
2020
squaeed
O(r $
Rounded gradient an odd aunther
Clee et all
2020a
x
mixed
O 4
Alistarn 2017
squared
[luddlalpour et al
2021
O }
ad + 322
gradient dissimilarity
squeee
Siggateed/ (ALG)
O t) squared
Rounded gradient Bounded 6th of gradient noise
oo SignFedAAg (ALG This work
O(r #) squared &g
Rounded support of gradiest noise
Table 2: Summary of representative stochastic sign-based methods.
then we have
|asl| S
|a.|| 0(7-1). 0((-))
(13)
Thus, the convergence results in (Safaryan & Richtárik] 2021) cannot imply the rate in Theorem 2 Besides, the algorithm in (Sataryan & Richtárik (021) equivalent to our Algorithm with == and a = llgi- -.-ll This input-dependent noise scale is linearly increasing w.r.t the problem dimension and too conservative for practical applications. From Figure I aand Figure 3 we have already seen that this input-dependent noise scale could result in an extremely slow convergence for high-dimensional problems.
Except for the previous sign-based compression methods, another type of compressed FL algorithms, such as AAlistrr that satisties Q x [| < C| for some constant C' >> O. We remark that such property is
2017) and (Haddadpour al.) 2021). adopt a unified unbiased compressor Q(-)
fulfilled by any of the existing sign-based compressors. Thus, the theoretical results therein cannot be applied to sign-based methods. A specific example of such unbiased compressor is described below.
Definition 2 (Unbiased quantizer). For any variable Rd, the unbiased quantizer Q() Rd - Rd is defined as below
(( s) Sign(x2){(x2))
( ||0||2
(14)
Sign(xa)
14

---

Under review as a conference paper at ICLR 2023
where E(2,, 8) is random variable taking value 1+1 with probability Here, the tuning parameter 8 corresponds to the number of quantization levels and E [0, s) is an integer such that |x,L
| I and & otherwise. T
T0 E +
In Table 2. we assume both (Alistarh et al. 2017) and (Haddadpour et al. 2021 adopt the quantizer (T4). Generally speaking, this type of unbiased quantization usually y requires much more bits than sign-based compression to obtain a good performance, which is also verified empirically in Appendix E It is also worthwhile to mention that the FedPAQ in (Reisizadch et al. 2020) and the FedCOM Haddaddour et al. 2021) equivalent in algorithm, but only the latter one considers the heterogeneous scenario theoretically.
DETAILED THEORETICAL RESULTS
We first state the result on the limit z-distribution.
Lemma 2. The 2-distribution weakly converges uniform distribution on [-1, when +o0.
The following corollary is the formal version Corollary
Corollary 2 (Formal version of Corollary 1. For 7 min 2 25t1,
2+1 and a = (nT) ast2
Lmaax
in Theorem 7 we have
21 f*]
L2Lmax (NT) 2011 (nT) 2x+1
4(E - 1) 22 L max (52 + G2)
E
V [f(
3r 2x41
22 1 E v Q2 + G42+2G
+ 242 + G 242+2) L
v2(2z + 1) () I.lI
2(2z + 1)2 .. 1 2017
2 Ej=1 bij
(15)
(( यमम
242
Furthermore, if F < n Joiz 7 J072,
the upper bound above becomes
2 (Fr)) 8 Tmma
2
412 max
( + G2)
E
V [
(NT) 2+43 (NT) 25+1
3(nT) 1547
22 122 /Q= G4++2G
24 g4=++=+1(0 (Q= + G42+2) Lmax
+
V2(2z + 1) 1) I
2(2z + 1) 7 2011
30+1
4m2 2Ø=1 Lj
(16)
E(nT) x.ाI
The formal version of Theorem 2 is given below.
Theorem (Formal version of Theorem 2). Suppose that Assumption and 3 hold. For y S Lime'
7 = 0, == too and o > E(G + Qoe) in Algorithm 7 we have
f f41 TE7
2 Lmax 11(E-1)ELa. (52 G2)
TE
n
t=1
Standard serms in FedAvg
4702 E Loj +
(17)
En
Variance
15

---

Under review as a conference paper at ICLR 2023
Otherwise, if S E(G + Qoc), there exists problem instance for which the algorithm cannot converge. If we further choose ? min 2 "mmae we have
T
E
21E f 14]
L2 (nT)
4(E - E)En (52 G2
[
(NT)
37
2 2j=1 Lj
(18)
E(
Furthermore,
E Annne ă the upper bound above becomes
T
E
2E[f(20) - f4]
L
4L2 max (c2 + G2)
E
V[(
+
+
(NT)
(nT)
3(1T)
40 ΣØ Lg
(19)
E(nT)
which recovers the convergence result of the uncompressed FedAvg algorithm (Yu et al. 2019
In particular, since the third term in the RHS of (8 is O(E hence when E S n i this
term becomes ()
C PROOFS
C.1 PROOF LEMMA 1
We first state a useful inequality on the c.d.f of the z-distribution:
Lemma 3. For any R, it holds that
|x 2=+1
V (x) S |z|
(20)
2(2z + 1)
where
Vz(r) def. { c dt.
22
Similar to the sign operator, for any vector x =
Rd, we define
V (x)
With the presence of Lemma 3 have
| [Sign(x + of)]] - =|| - oV, (-) 1
Σ x(1) - 00
d
xx())
(m(1)) 1x+2
|| 4242
(21)
4(2z + 1)201
4(2z + 1)2
Proof of Lemma
Without loss of generality, we consider x 2 0. First,
f E di 5
22
1dt S x.
(22)
Now we define F(x) del. F(x) 2 0 by
for e x + 2(2=11)
20
2011
Note that F(0) = Then, it suffices to show
2z
F'(x)
-1
0.
(23)
2
It is true since the inequality et - 1 + 1 2 0 for any 1. 0.
16

---

Under review as a conference paper at ICLR 2023
C.2 PROOF OF LEMMA 2
Now we denote the p.d.f of the uniform distribution as
(o)
2
| <
1,
(24)
0
>
Without loss of generality, for any x > 1 and 2 E Z_, we have
1 21/
1 :22
2 dt / Poo (t)dtt
eeee
22
2
Poo (t)
dt
21z
1
/
dl
+
e
2
dl.
(25)
27/
2
27/
For any 0 < < min(1, (0
1}, we have
.2
1
6
dt
dt +
6
dt
21/²
2
0
21
2
-l-c
21/=
2
(1
1
<
tc.
(26)
217²
2
(1-e)
Since lim 1 lim,
2n.
2 ++
2
and lim, +oc
1, there exists an integer
Z1 such that if Z1, we have
(1-))2 2
1
Se
21/=
2
Similarly, we have
1
2x
1+e
2x
20
T
dt
dt +
e
dt
21Tx
27/s
211²
1+t
(1te)
+
(x
c).
(27)
21a
2= 2
Since lim c
0, there exists an integer Z₂ > 0 such that if 2 > Zz, we have
22 dt <.
(28)
2T²
In all, for any 6 < min(1, - 1}, if is sufficiently large, we have
22 dt - _ Poo (t)dt) s 4c.
(29)
000 27z
Taking 0 and 0c, have
+ dt I Poo = -00
lim
(30)
20000
21/2
C.3 PROOF OF THEOREM
I
We denote the aggregated update H, Zt 1. First, we state two technical lemmas: Lemma 4. Suppose that Assumption and 2 hold. For the t-th (1 < t T) communication round in
Algorithm 7 if 12 and < +00, have
B[f(z)) f(ā+)) < 722 F-2-1 QQ= G4++2G 2211 1 2 G1++22 T
22 + 2)
4(2z + 1)2
200 ΣØ=1 L.j
(31)
17

---

Under review as a conference paper at ICLR 2023
Lemma 5. Suppose that Assumption hold. For the t-th (1 S t S T) communication round in
Algorithm 1 if Σ Immax we have
22 [
2 1
1 max (C² + G²)
[()( f(xx-1))
VV
2n
3
(32)
By combining Lemma 4 and Lemma
we have
Elf(x)) - [3+]] E(((E) - -(xe-1)]
2 2
1)B2 L (C2
G2
$ s 7 Σ
V Vf 1,0 1.0-1 1)1
+
2
2n
22 E2 QQ= + G42+2
7224 E42
(Q: 2)
2((2z + 1)020
1(2z 1))00t
n 02 > d
jj= Lj
(33)
n
33 Rearranging the incquality
have
[ (x)- - s(x))] Tm
11FE2
max (C2 + G2)
(f
111
+
+
E
Ey
3
2 1 E VQ= + Glz+2G
+ 222 (Q=
G G42+2 Lmax
V2(2z 1)o2:
2(2z + 1)2
4n2 2 Σj= Lj
(34)
En
Finally, by a telescopic sum, we obtain
f [m)) -f-
Lmax
4 - 1)EL (52 + G2)
TET
n
222+1 E /Q= + Glz+2G
+ g22= (Q2 + G42+2) L
+
22 + 1)02z
2(2z 1)2
4m Σ1 Lj
(35)
En
Proof of Lemma 4 First, know from function smoothness that
f(x) f(t.) < (V)(()), 2z) E/=1 L, (ze(i) xc(i))²
(36)
As can be seen from (36). we need to study the Ie. - Tr order to obtaining the upper bound for
f(x,) - f(āt). Note that
E o6:
E
T1
1 Σ
n
Σ
Bi,
Σ
Di.s
(37)
For ease of presentation, we define that
E
A def.
Sign
Σ
gr.
o6z
(38)
18

---

Under review as a conference paper at ICLR 2023
By taking the expectation over the random vector É., for any j = 1, ..., d, we have
22
n
Ee, (()
-x()))
Be.
A Σ gl,
(39a)
7²
E
Be.
Ai(i) Es. [A(O] + Be. [AG)]]
Σ
gh. (i)
n²
(39b)
2
(A(G) - Be. (42G11)
Be
(39c)
n2
E Bg. [A(0)] - E (i.aG)) )) ==1
22
+
Ee.
(39d)
n2
where the last inequality is obtained because Eim1 (A:(i) - Ee. [A((]] is zero-mean and inde-
pendent of Ex=
i= Egg [A:()] - EF=rgi, (i))
From
38
it is easy to check that [,4 I n² Hence, for the RHS of (39c), we have
IEg.
Σ (ALG) - Ee. (4861))
(a)
Σ
Bs
(A:0) Es. [4(G)))*]
1=1
LEg. (A461)* + +EEg. [4())))*)
S 2
< 4nnza
(40)
where equality (a) true because A! (T) are independent each other.
Therefore, from 39 and 40 we have
Eg.
Σ T (x+(i) =x(0)²²²
Σ Be (sx(0)) [1)77
(41a)
4n 20 EE Lj
n
27
L Lg
Σ
Eç. [A(0) - Σ Eoi.0o0)
n² j=1
(41b)
4n 7 20 nd
jj= L.j
n
72 Lmax Ee.
Σ
Ee. [4:]
Σ g
(41c)
2
19

---

Under review as a conference paper at ICLR 2023
To bound the RHS of (41c). we have
E
E
27
Es.
Σ
Bs.
[A:]
Σ
Mi. 8
S m
Egg
Ee. [4d
gi
1=1
E Σ
12+2
n
gi.s
(42)
4(2z + 1)2013
==1
1x+2
where the last inequality is due to Lemma Now need to bound
1
1++2
Σ
9
1++2
where the expectation is taken over both &s and the mini-batch gradient noise. To this end, need the following lemma about the lp -orm.
Lemma 6. For any M E Z4,, > and vectors Ti, JM E Rd, we have
M
M
M
(43)
As direct application of Lemma o obtain
E
43+27
E
E
Σ
fi
< E
E
91,8
1++2
4++2
E
+
E
|
4++2
12+2
(44)
1++2
Then we can bound the RHS of
as
E
|
4=+2 4
g V.fl
V.fi.. 4x+2
16+2
(a)
22=+1 | V/ii(a V 1114+ 1=+1
V 1,
8, 1)
42+27
42+2
2 2*=+1
Q= + 2 [[ 12+2
2 (Q, )
(45)
where inequality (a) follows Lemma inequality (b) due to Assumption 2 due to A.4 of Assumption I
and inequality (c)
Combing
and (45)
we have
E Σ
E Σ s=1
Σ Eg.
[A:]]
gi
E
Σ
Eg. [A:]
gi.s
n221s 2 (Q= + G1o+2)
2(2x + 1)204z
n224 F2a+1 V(2= + G4++2)
(46)
22(2> 1)02c
and
4n 202 ΣØ T.j
7 I E
E
Σ L, (zi(3) - =c(1))2
Σ
Eg, [A4]]
L
2
4m2 20 j==1 Lig
22 2 + G42+2) 2 Linax
(47)
n
4(2z 1)2
20

---

Under review as a conference paper at ICLR 2023
Hence, we have
B[S(a)) ((x)) ST
V (Tte)
7 Σ
Re, [Ai]
Σ gi.s
n 1=1
Σラ 1:g (x)( - mz(i))²
+ E
E
[
7 Σ
Eg. [Ai]
Σ
gi.s
1=1
==1
2i=1 Lg (Dx(i) 3+(1))²
+E
2
222 F22+1 VQz GAz-2
72213 121=)tt-21Q2 + (xtxt2)
V2(2z + 1)022
4(22 + 1)2
27 Σド=1 يا
(48)
Proof of Lemma 6
To prove this lemma, need classical result on the monotonicity of Ep
norm:
Lemma 7.
Kanntrrvvih & Akilov 2016) For any x E Rdd and < r < p. we have
| S ||~||| S d= d $1111p1
(49)
Now from the definition of l, norm we have
M
P mi(i) )²
Σ Σ mx0ii]
Σ
p
Σ
(1),
EaM (T) (F)l IF
3=1
(0)
MP-1
Σ
|| (I,,
jm1
-MP-1
(ot()))P
jml
= -MP1
||>;; l1p
(50)
where inequality (a) is due to Lemma 7
21

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 5 local steps.
First we unroll the difference f(æ)) f( into telescopic sum across E
E
f(z.) f(1)-1) = ((
f(1
Σ ((( f((
(5la)
E
Lmax
1
-V - I(-1,) +
1 - Zz- 11-1,8-11 11
2
(51b)
7VV
Σ
li 1,3)
Lmax
1
Σ g
n
72
2
n
s=1
(51c)
where the inequality is due to the smoothness assumption. Taking expectation over the mini-batch gradient noise 1,51, Oe 1,s+ for the first terms in (51c), we obtain
1 12
Σ 10 )|=
E
V
=
V [
V Vi(lz
(52a)
|
[ )|(
f
V
2
2
(52b)
1
n
1,) )
+
2
V
ff
fi
(52c)
n
For the second terms in (51c), we have
1
E
9
1,0-1
1)
17
n
1
1
E
9
1,8-1)
+
(1
n i=1
12
2
E
V fi
[ 1,
1,3
+
[1(
1=1
1=1
(c)
2
(53)
n
where equalities (a) and (b) are true because the mini-batch gradient noise is independent, and inequality (c) due to A. of Assumption |
Notice that owing to the function smoothness, we have for arbitrary y E Rdd.
fw0) < (VI(x), x) Lmax I1y 1=12
(54)
which is equivalent to
[V(() - vf(v)) L lly - =||.
(55)
22

---

Under review as a conference paper at ICLR 2023
Now to bound the term in (52c), for every s, we have
f [8t 1.5-))
V
i=
1 n
(1(22-1,011
n
12
L
181-1,8-1
11-1-8-11 |
7
7 L
mmxx
-1-1- 1. vi-1.
(s 1)7 22 max
5
g1 1.9
91-1.9
=1
2
2(s
2 max
+ +119i-1.911 1. 11
g 1.0
n
2(s 1)7 L max
g 1.9
+
+11oi-1aal"
(56)
For any f 1, ..., T, 1,.... and g 1, ..... s 1, taking expectation over mini-batch gradient
noise, we have
11sb Vf +) V Vf |||]
= E
1,9
< E
< 2 + G².
(57)
Substituting (57) into (66,, we have
1
V V
Vf 4(s - L2 + G2).
(58)
Further substituting
53
52
and
58
into
51) and by rearranging the terms, we obtain
Bff(z,) f(1r-1))
Σ
v
ff
22 Limxx
1
fz (1
2
2
1=1
1=1
E
Lmax
1V (1
V 1,,)) 1)1?
2n
#=1
(a)
E
T
Tenax
[V
2
2n
E
Σ 2(s - 1)2231 1 1 (52 + G2).
(59)
where inequality (a) is by TT2xmxx - 5.
23

---

Under review as a conference paper at ICLR 2023
Note that
12E
-1)
(E-1)4 E)
1)²
(60)
6
3
==1
By applying it to 59
we finally have
E
Ex? Lmax
2x L)
max (52
+ G²)
[(f(2() f(r(-1)) v
V
2
2n
3
==1
(61)
C.4 PROOF OF THEOREM 3
We need a lemma similar to Lemma
Lemma 8. Suppose that Assumption 7 and 3 hold. For the 1-th (1 S tt S T) communication round in
Algorithm 7 if a and 2 +oc, and a E(G + 2.0), then
2-20" Σj Li
-(f(z)) f(a)] S
(62)
Following the similar idea as in the proof of Theorem we have
[[f(x;) f(z, [[f(x;) f(2,)) + Elf(E,) f(1+11)]
=² Lmax
7 Vf(
2
2n
2x
1)E?
12 max (52 G2)
2720² ΣØ Li
+
(63)
Rearranging the terms, we have
1
F
21E (x] 11a1)3
- f(x)]]
2
Vf
E
Ey
422(E- - -1)E12
(C2 + G2)
470²
2j-1 Lا
+
max
(64)
3
En
Form the telescopic sum, we obtain
2R [ - -f"]
Y5 L
E
V (f
TE
TEy
n
4-2(E 11)EE 1)EL (52 G2)
470² Ej= (65)
3
En
Here we provide simple example to show that when a < E(G + Qoc), the algorithm cannot converge. Consider E = 1, Qoo 0 and the problem
min(x zER
A)2 + (x ()+
where A 0 some positive number. If we choose the initial be 3o 4. As see, the gradient at do for the two parts the objective function are - A and 34, respectively. We denote that Eoc as the random noise following uniform distribution at [-1, 1]. If now < A, we have A + x Sign o 0,
Sign(-A
(66)
i.e., this algorithm never update the variable.
24

---

Under review as a conference paper at ICLR 2023
Proof of Lemma 8 We first note that, when +00, have
at E [-1, 1],
ooo
(2)
-1 -1,
(67)
I
>
Again, from the smoothness assumption (A.2 in Assumption [ have,
Ej=1 L (oe(i) =z(i))
f(z))- f(ā,) < (V.(()), a -x,) +
(68)
Taking expectation over Soc.
E Sign
E
Eg, [2, - Rzl = B mm
E9.
gi.s + 0500
Σ
Le
im1
Σx
E
F
(a)
7
Dh.s
0 00
Fi,s
i=1
s=1
It,s
gr.s
0,
(69)
71
where equality (a) is because for any IRd, Eg,. [Sign(x + a(oo)] = (z0(o/)). equality (b) is due to > | ll almost surely and the property of the function Vi (.) in 66
For ease presentation, we define that
B def.
Sign
Lh + 0600
(70)
From 69
we have learned that Es,. [B:]] = >x Ph.e. Thus, for any j 1,.... d, we have
2
EE_
- ((xx(())
BE
Σ (Bi(i) - EE [B(()))
n2
22 n
Esg (B8(() BB... [B)()]])
n
2>2
(Eg.
(1B(6))² + (Bem [B:))])²
n
i=1
2
(71)
n
Finally, substituting (69 and (71) into
668
and taking the expectation over both &oo and the mini-
batch gradient noise, we have
Σd (xx(1) - -x(())²
B[f(x, f(a))) B(V((
24- E
2
20 Σd Lj
(72)
n
25

---

Under review as a conference paper at ICLR 2023
D EXPERIMENT DETAILS
D.1 DETAILS FOR THE EXPERIMENT IN SECTION 4.2
In 3 provide the tuned hyperparameters for all the tested algorithms non-ii.d MNIST. Specifically, we tuned the hyperparameters via grid search: [0.1, 0.05, 0.01, 0.005] for stepsize, [0, 0.3, 0.5, 0.7, 0.9) for the momentum coefficient, and [0, 0.02, 0.05, 0.01, 0.03, 0.05, 0.1, 0.3, 0.5] for the noise scale.
Algorithm
Stepsize
Momentum coefficient
Noise scale
SGDwM
0.05
0.9
EF-SignSGDWM
0.05
0.9
Sto-SignSGDWM
0.01
0.9
SignSGI
0.01
0
1-SignSGD
0.01
0
0.05
So-SignSGD
0.01
0
0.05
Table 3: Hyperparameters used for FL on non-i.id MNIST.
In Figure 7 we visualize the performance of 1-SignSGD and oo-SignSGD under different noise scales. As we can see, the results for 1-SignSGD and oc-SignSGDD are almost the same, except that the oo-SignGGD is slightly better than 1-SignSGI when the noise scale is large.
1-Sensea0te = 0.02)
3
SigSS00pp 6.03)
100
1 SignSCD0g c.1)
Segns000e 6.3)
Training loss
2
SignSC00
60
Test
40
1-9gr600D0
1-@gr60Dee- - 0.3)
Sig
20
100
200
300
400
500
100
200
300
500
Communication rounds
Communication rounds
(a) Training Loss: -SignSSD
(b) Test Accuracy: SiggnSSD
6
SinnSC20e 0.02)
100
SignSC2oo= p.1)
Training loss
4
Sip 0.3)
Accuracy
80
3
60
SignSCD:0 - 2.02)
2
SkgngoD 2.05)
SkgnScD:0 2.13
SignSCD0p - 2.5)
100
200
300
400
500
100
200
300
400
500
Communication rounds
Communication rounds
(c) Training Los::oD-SignGGD
(d) Test Accuracy.oe-SignSG
Figure 7: z-SignFedAvg under different noise scales non-i.i.d MNIST
D.2 DETAILS FOR THE EXPERIMENT IN SECTION
We denote the noiseless case, i.e., Algorithm with 0 SignFedAvg.
26

---

Under review as a conference paper at ICLR 2023
EMNIST: For the experiment EMNIST, fixed the client stepsize 0.05. We tuned the server stepsize, noise scales via grid search: [1,0.5, 0.1, 0.05, 0.010 0.005] for step- size, [0, 0.005, 0.02, 0.05, 0.01, 0.03, 0.05, 0.1, for noise scale. The comparison between 1- SignFedAvg and ox-SinnFedAvg on EMNIST is shown Figure X The used hyperparameter the We also visualize the performance of 1 1-SignFedAvg and So-SinneedAvg under various noise scales and local steps in Figure and Figure [0]
Figure @ A are summarized in Table 4
CIFAR-10:
For the experiment CIFAR-1O, we fixed the client stepsize 0.1. We tuned the server stepsize, noise scales via grid search: [10", 100, 10-0.1, 10-1, 10-1., 10-2
10-25, 2.5 10-31 for the stepsize, [0, 0.0001, 0.0005, 0.001, 0.005] for the noise scale. The comparison between 1-SignFedAvg and
00 So-SignFedAAg on CIFAR- 10 is displayed in Figure [T] The used hyperparameter in the Figure 5 and 11 are summarized in Table 5 We also visualize the performance of 1-SignFedAvg and -iv under various noise scales and different numbers of local steps in Figure 12 and An interesting phenomeNon-in Figure 12 amd Figure [3 that the more local steps are, the less impact the additive noise has the convergence performance.
Figure 13
1-SignFedAvg 2)
1-SignFedAvg 5)
1-SignFedAvg (E 10)
1-SignFedAvg (E 20)
=-SignFedAvg (E == 2)
SignnFeeAAv (E 5)
SignFedAvg (E= 10)
ce SignFedAAvg 20)
100
leainng Aocunccy
2.0
9
legiCommunecatton
KolCoomunicattoo
(a) Training Loss
(b) Test Accuracy
(c) Test Accuracy w.r.t bits
Figure 8: Performance of 1-SignFedAvg and oc-SignFedAvg on EMNIST dataset.
Algorithm
Server stepsize
Noise scale
1-SignFedAvg
0.03
0.01
0.03
0.01
SignFedAAg
0.03
O
Table 4: Hyperparameters for tested Algorithms on EMNIST.
SignFedAvg
SignFedAvvgo 0.02)
L-SignFedAvglo 0.1)
1-SignFedAvg(o= 0.00))
L-SignFedAvgoo 0.05)
1-SignFedAvg(o 0.2)
Thanerg lee
Treeeig
&
8
2
5
lngiCommumkasonn
(a) =
(b) E 5
(c) E = 10
(d) E = 20
Accueeyy
3
(c) =
(0) E 5
(g) E 10
(b) E 20
Figure 9: EMNIST: I-SignFedAvg under different noise scales and different numbers of local steps
27

---

Under review as a conference paper at ICLR 2023
SignFedAvg
SignFedAvg(o 0.01)
SignFedAvglo 0.1)
SignFedAvg(o 0.005)
SignFedAvg(o 0.05)
SignFedAvggo 0.2)
% 3
Traning koe 5
Trantrgg bree 5
E
Trassing
VyrCammumkaiion lounds
lspiCon Tosioaatioooooonooommmo Iounds
SgrCammunionn rounds
legCCnnuniition nunds
(a)
(b) E
(c)
(d) 20
batioommmn colon rounds
bgtcommnn caloo r0U 10
lagiommmnndden rounds
LegCommmnnaioo rounds 13
(e) E' 2
(1) E
(g) E 10
(h) E' 20
Figure 10: EMNIST: co- so-SignFedAvg under different noise scales and different numbers of local steps
Algorithm
Server stepsize
Noise scale
I-SignFedAvg
0.0032
0.0005
Se-SignFeddAyy
0.0032
0.0005
SignFedAvg
0.0032
Table 5: Hyperparameters for tested Algorithms on CIFAR-10.
1-SignFedAvg (E 2)
1-SignFedAvg (E 55
1-SignFedAvg (E = 10)
o SignFedAvg (E = 2)
so- SignFFeAAAv (E 5)
oe SiigFFedAvv (E = 10)
Testing Accuracy
Tesiin Accuracy
1.25
1.00
1000
2000
3000
4000
5000
1000
2000 Communication rounds
3000
1000
5000
37.5 38.0 185 1008 19.5 20.0 205 21.0 $700
Communication rounds
oogTrrmsmited Bits per client 1)
(a) Training Loss
(b) Test Accuracy
(c) Test Accuracy w.r.t bits
Figure 11: Performance of 1-SignFedAvg and oc-SinFFedAvg CIFAR-10 dataset.
28

---

Under review as a conference paper at ICLR 2023
SignFedAvg --SignFeeAAggoo=000000001
1-SignFedAvglo 0.0005)
1-SignFeziAvglo 0.005)
1-SignFedAvg(o 0.001)
2.25
2.00
2.00
1.75
1.75
1.75
3.30
Trainning loss
3.50
Trainnnn
3.25
3.25
3,00
1.00
0.75
0.50
6.25
5000
Communication
Comm rounds
Commrnnniation rounds
(a) 2
(b) E=
(c) E = 10
80
20
Testing Accurncy
70
Testing Accuracy
70
500
80
5
30
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
1000
2000
3000
4000
5000
Communicasion rounds
Communication
Communication rounds
(d) F =
(c)
(f)
10
Figure 12: CIFAR-10: 1 1-SignFedAvg under different noise scales and different numbers of local steps
SignFedAAg
SigneedAggoo 0.0005)
wi.ginneeAAggl 0.005)
ei-SinnFedAuglo - 0.0001)
SignFedAvglo = 0.001)
2.00
2.0
1.8
Trainning lose
Trainiing lass
1.50
Training
1.4
3.25
3,00
3,00
0.75
0.75
ca
0:50
0:30
0.25
0.25
Communication
Comm Unication
(a) E' 2
(b) E'
(c) E 10
Testing Acturcy
Testing Accuracy
60
80
30
80
30
2000
5000
2000
5000
1000
2000
4000
Commurication rounds
Communication rounds
Communication rounds
(d) E =
(e) E
(I) E 10
Figure 13: CIFAR-10: co-SignFedAvg under different noise scales and different numbers of local steps
29

---

Under review as a conference paper at ICLR 2023
D.3 DETAILS FOR THE EXPERIMENT SECTION 4.4
For the experiment results shown in Figure 6 except for the noise scale, both I-SignSGD/1- SignFedAvg and 1-SignSGD- LLGGD--latea/111 Siigned/Avgglaateeeeee previous experiments. In Table O we show the hyperparameters of the Plateau criterion for the adaptive noise scale, which are chosen by few rounds of trial and error. Besides, we also show the corresponding test accuracy Figure and how the noise scale evolves over communication
used the same hyperparameters found
rounds in Figure 15
Dataset
Finit
Obound
k
G
Non-ii.d. MNIST
0.01
0.5
30
1.5
EMNIST 0.0001
0.1
10
2
CIFAR-10
0.001
0.1
200
1.5
Table 6: Hyperparameters of Plateau criterion for three different datasets.
100
100
80
Accuracy
Tosting Accuracy
80
Testing Accuracy
70
60
00
1- SiggnnGDDo = 0.05)
a- eoAvg-pltteu
SignFFddAug plateau
20
--SiinSGD-plleeen
1-Sig Fog - 0.01)
1-SignFedAvgío 0.0005)
Communication rounds
log(Communication rounds + 1)
Communication
(a) Non-i..d. MNIST
(b) EMNIST
(c) CIFAR-10
Figure 14: The corresponding test accuracy to Figure 6
0.25
0.30
110000
0.20
Nose scale
0.08
Nose scale
0,0005
0.15
0084
0.0003
0.02
0.0002
0.00
100
200
900
400
500
100
200
400
500
1000
2000
3000
4200
5000
Communication rounds
Communication rounds
Communication rounds
(a) Non-i.idd MNIST
(b) EMNIST
(c) CIFAR-10
Figure 15: The corresponding trends of noise scale to Figure
COMPARISON WITH UNBIASED STOCHASTIC QUANTIZATION METHOD
In this part, we compare our Algorithm the QSGD Alistarh al. 2017 along with its extension
to FedAvg, i.e., FedPAQ (Reisizadeh et al. (020). As we have shown that --SignSGD//-SSinFeed/eee with the Gaussian noise and uniform noise behave very closely, here we only consider 1-SignSGD/1- SignFedAvg for comparison. We use the unbiased quantizer in (14) for both QSGD and FedPAQ.
We can see that the quantization level s plays as a key role the performance and communication efficiency of QSGD and FedPAQ. In rough sense, also represents the number of bits needed to transmit for a single coordinate. Thus, we will compare our algorithms to them with different choices of s. We remark that, even in the most extreme case, i.e., s 1, it still needs three alphabets 1, for communication, while sign-based method only uses -1 and 1.
Setting, Again, we consider the three different datasets used in Section 4.2 and Specifically, compare the 1-SignSGD with QSGD on the non-i.i.d. MNIST dataset, and compare L-SignFedAvg with FedPAQ on EMNIST and CIFAR-10. For all the algorithms, the client's stepsize and batchsize
30

---

Under review as a conference paper at ICLR 2023
reuse the previously found optimal hyperparameiers. For QSGD, we tune the server stepsize via grid search on [0.1, 0.05, 0.01, 0.005]. For FedPAQ. tune the server stepsize via grid search on [1, 0.5, 1, 0.05, 0.01, 0.005]. The chosen server stepsizes for QSGD and FedPAQ under three datesets presented in Table 7
set the same values used in Section 4.2 and 4.2 For I-SignSGD/1-SignFedae
Algorithm
Non-iid. MNIST
EMNIST
CIFAR-10
QSGD(s 1)
0.01
QSGD(s 2)
0.05
QSGD(s 4)
0.05
FedPAQ(s 1)
FedPAQ(s 2)
FedPAQ(s 4)
FedPAQ(s 8)
Table The chosen server stepsizes for tested QSGD and FedPAQ on three datasets.
Results. From Figure 16 we can see that, our proposed sign-based compressor is consistently superior to the unbiased stochastic quantization method in low precision region (1 bit to 8 bits), except the only case that QSGD with s = 4 slightly better than our 1-SignSGD on the non-i.i.d MNIST dataset. These results again, (Bernstein et al. 2018 Karimireddy et al. 2019) did, show that the biased compressor, or more specifically the based compressor, can be a strong competitor those unbiased quantizer due to reduced variance. Our contribution in this work is to provide generic framework that bridges the unbiased compressor and the biased one, which allows one to conveniently seek an optimal trade-off between the compression bias and variance.
1-9ignS0D:0 0.05)
QSCDDS
2,0
FedPAQ
FedF/QQS 11
Training
050DG-2
056D6
Training loss
1.5
FedPAQ
FedPAQ 4)
Training loss
FedPAQQs
FedPAQ 4)
F-SigrFoddkg
L-SignFedAvg
2.
2.00
0.75
0,50
0.25
Communication rounds
log|Communicatio rounds
(a) Non-i.id MNIST
(b) EMNIST
(c) CIFAR- 10
100
100
Testing Accuracy
Texning Accuracy
00
Testing Accuracy
az
80
FedPAq (5 1)
L-ggSGDpp 0.05)
55
FedPAQ (5 2)
FedPr10s = 1)
QSGDo 1)
FecPAq(s
OSGDYs 2)
FedPAQ (5 4)
FcdPACYs - 8)
20
QSGDgy
1. 1iSignFodAvg
1-5grFedthgg
100
200
400
500
1000
2000
3000
4000
5000
Communication rounds
log(Communication rounds +
Communication rounds
(d) Non-i.i. MNIST
(e) EMNIST
(I) CIFAR-10
Figure 16: Comparison of 1 1-SignSSDD1--SggneedAAg with QSGD/FedPAQ on three datasets.
F DIFFERENTIAL PRIVATE FEDERATED LEARNING ON EMNIST
Let us first review the definition of DP.
Definition 3 (Approximate DP (Dwork et al. 2014)). ). A randomized algorithm M that takes as input a dataset consisting of individuals is (s, - diffferentially private for any pair of datasets S,S' that differ in the record of single individual, and for any event E.
P[M(S) F) P
(M
(73)
31

---

Under review as a conference paper at ICLR 2023
The value is regarded as the privacy budget, and the smaller it is the stronger privacy the algorithm
provides. The quantity is usually set to 1. The most popular mechanism to achieve DP is the
Gaussian mechanism (Dwork al.) 2014). Specifically, similar to (Agarwal et al. 2021: Kairouz
et al. 202T), here we consider client-level DP guarantee for Federated Learning. i.e, we regard each Besides, we also adopt the local version of DP gurantee, i.c., each dataset in Definition 3 contains only one data point. Such DP guarantee do not assume that
client single data point in Definition
3
2021 Kairouz et al. 2021). For more details on DP and its application in FL, we refer readers to (Dwork et al. 2014
the server trustworthy and hence is commonly used in practice (Agarwal al.
Mironov 2017 Abadi et al. 2016b Geyer al. 2017).
Here we describe the differential private version of Algorithm | which we term DP- Up-SignFedAvg (Algorithm [
The only difference between DP-SignFedAAvg and z-SignFedAvg that = is chosen (Gaussian noise), and the norm of local gradients is clipped before perturbing it by the noise and applying the sign compression. To obtain the client-level privacy guarantee, we adopt the privacy accounting method in (Mironov et al. 2019)
Algorithm 2 DP- SP-SignFedAAg
Require: Total communication rounds T, Number of local steps E, Number of clients n, Client sampling ratio Clients stepsize y, Server stepsize y), Noise coefficient a, Norm clipping coefficient C.
1: Initialize zo and for i = L,..,
2: for 1 to T do
3: Sample set of clients S with size qn for current round.
4: On Clients:
5: for in S do
6: x²-1.0 = 5t-1
7:
for s 1 to E do
8:
gi gi-1,- 1,. = g: (x where g-(-) is the mini-batch gradient oracle of the i-th client.
9:
x|_1,- = xt 11,1- 79
10:
end for
1- 1/0) +N(0002(21)
11:
A = Sign max
12:
Send Ai to the server.
13:
end for
14:
On Server:
15:
21 = -1-1- n ΣT_ A
16: Broadcast x, to clients.
17:
end for
18:
return 2T.
Now investigate the empirical performance of the DP-SignFedAvg EMNIST, and compared it with the uncompressed DP-FedAvg used in (Agawall et al. 2021 Kairouz et al. 2021
Settings. We followed a setting similar Kairouz al. 202 for the experiment on EMNIST. We adopted the client-level differential privacy, i.e., to treat each client as single data point, and perturbed the local gradients before sending them server. We also used the technique of privacy amplification by client sub-sampling in (Kairouz et al. 2021 Geyer et al.) 2017). For both DP-FedAWe and DP-SignFedAvv. the same CNN in Section 4.2 was used, and the maximum norm for clipping was set to 0.01. We sampled 100 clients each communication round and ran both algorithms for 500 communication rounds. Similar to (Kairouz et al. (02T), we run the experiments under the privacy budgets and Ded for all levels of privacy budgets. Unlike previous experiments, the noise scales used in this experiment were determined by the privacy budget and the privacy accounting method in (Mironov et al. 2019).
[1, 2, 4, 6, 8, 10). In Table g we provide the hyperparameter for DP-FedAvg
It can be from Figure 17 that DP-SignFedAvg is only slightly inferior to the uncompressed DP-FedAvg for various levels of privacy budget. It is worthy to note that the work (Kairouz et al. 2021) conducted similar experiment and showed that the compressed De-FedAvg
Results.
32

---

Under review as a conference paper at ICLR 2023
Privacy budget
7) for DP-FedAvg
1 for DP-SignFedAvg
Noise scale
1.0029
0.03
2.77
2.0171
2
0.05
1.57
4.0459
5
0.05
1.02
6.0135
0.05
0.845
8.0336
0.05
0.75
9.9996
0.05
0.685
Table 8: Hyperparameters for DP Algorithms on EMNIST.
with bits for each gradient coordinate can far worse than the uncompressed DP-FedAvg. It strong contrast to our Di-SinnFedAvg which uses only 1 bit for each coordinate.
De-SiggFedAvg DP-FedAvg
Training loss
Test Test Accuracy
86
2.6
80
DP-SignFedAvg
78
DP-FedAvg
02
1
2
4
6
8
10
1
2
(a) Training Loss
(b) Test Accuracy
Figure 17: Performance DP-SignFedAvg and DP-FedAvg
33


Reviews:
[{"review_id": "w9Vggcbjqb", "reviewer": "Reviewer_M8Jc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper studies stochastic 1-bit (sign) quantization in federated learning. Particularly, the stochastic quantization is achieved by adding a random noise to the value and then taking the sign. The authors considers a general noise distreibution parameterized by $z$ with Gaussian ($z=1$) and uniform ($z=\\infty$) as special cases. Convergence rates of applying this compressor to FL gradient uploading is provided. Experiments are conducted to show the effectiveness. The authors also discuss combining DP with the proposed algorithm at the end of the paper.", "summary_of_the_review": "The paper considers an interesting problem of using stochastic unbiased sign in FL. Some new results are developed for the noise distribution in the quantizer. However, the theoretical analysis is existing in literature and same result has been reported before. The experimental evaluation misses an important unbiased quantization baseline, and the 'extra' section of DP approach seems incomplete. Thus, currently I'm biased to rejection.", "strength_and_weaknesses": "S1. Stochastic 1-bit quantization, though being a popular compression strategy in many applilcation, has not been well investigated in FL. Thus, the paper provides a good application of such compressor to FL.\n\nS2. The unified noise distribution is interesting and provides a general framework.\n\n========================================================\n\nW1. Adding Gaussian noise ($z=1$) leads to biased compressor, which in some sense loses the advantage of stochastic quantization. From the experiments we also see that it is alsmost always worse than uniform noise with $z=\\infty$. This makes the practical implication of Gaussian noise limited.\n\nW2. The theoretical results are not surprising and has been reported in literature. Basically, when the compression is biased ($z<\\infty$), we have a bias term in the rate. If it is unbiased ($z=\\infty$), then the rate can be $O(1/\\sqrt{nTE})$. In the paper the authors stated \"To the best of our knowledge, the previous works have never shown the sign-based method can achieve a linear-speedup convergence rate.\" Yet, the same convergence rate has been reported in literature, for example, \n\n[1] Federated Learning with Compression:Unified Analysis and Sharp Guarantees, Haddadpour et al., AISTATS 2021.\n\nTherefore, this claim is not true. In fact, the algorithm in this paper is also the same as that in the reference [1], except that in this paper stochastic sign is used instead of a general compressor. But since $z=\\infty$ results in unbiased compression, the result in this paper is actually covered by the result in [1].\n\nW3. In the experiments, I think the paper missed QSGD as an important and popular baseline method, since it is another way for unbiased compression. Also, how did you tune the learning rates? Could the slow convergence of sto-SignSGD in Figure 1 due to too large or small learning rate?\n\nW4. Section 4.4 on DP variant seems unnecessary and incomplete. There is no formal analysis of the DP guarantee, nor the choice of noise variance, etc. I feel that this section may distract the main focus and contribution of the paper, plus this section itself is not well justified.\n\n=====================================================\n\nQuestions:\n\nQ1. The noise scale $\\sigma$ in the paper seems important, since different $\\sigma$ gives very different performances. How to properly tune this parameter in practice?\n\nQ2. In Algorithm 1, line 10, why don't you multiply the Sign by $\\eta_z\\sigma$ as in (4)?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "s499bKQxJn0", "reviewer": "Reviewer_xh3m", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper considers sign-based compression for federated learning (FL). It proposes a stochastic sign-based compressor, where first a random noise from (the proposed) $z$-distribution is added and then a sign operator is applied. The $z$-distribution covers Gaussian and uniform noise as its special cases. The sign-based compression is applied on top of the classical FedAvg, where clients use local SGD to compute model updates and the server computes a weighted average of updates. SignFedAvg can be viewed as an extension of SignSGD in [Bernstein et al. 2018] to FedAvg.", "summary_of_the_review": "The analysis of sign-based compression with $z$-distribution noise is interesting. At the same time, the convergence analysis relies on very strong assumptions and leaves open several questions. Further, the DP part needs to be fleshed out. Therefore, the paper is not yet ready for publication.", "strength_and_weaknesses": "**Strengths:**\n1. Applying sign-based compression on top of model updates is a natural extension of signSGD [Bernstein et al. 2018], where compression is applied on gradients. This is conceptually simple and can be practically useful. \n\n**Weaknesses:**\n1. For the case of $z = +\\infty$, i.e., when the injected noise is uniformly distributed on $[-1,+1]$, Assumption 3 seems very strong. It is also required for the theoretical result that the variance of the noise should be substantially large, i.e., $\\sigma > E(G + Q_{\\infty})$. This large variance in noise, in turn, results in a large variance term of the convergence result (Theorem 3 in Appendix B, formal version of Theorem 2). Remark 2 claims that SignFedAvg has the same order-wise convergence rate as that f uncompressed FedAvg. However, it is crucial that the large variance of Theorem 3 is discussed. \n\n* More specifically, the variance term in Theorem 3 is $\\frac{4\\gamma\\sigma^2\\sum_{j=1}^{d}L_j}{En}$. The theorem requires that $\\sigma > E(G + Q_{\\infty})$, which implies that the variance term is at least $\\frac{4\\gamma G^2 (E + Q_{\\infty})^2 \\sum_{j=1}^{d}L_j}{En} \\geq \\frac{4\\gamma G^2 E \\sum_{j=1}^{d}L_j}{n}$. \n\n    * When $L_j$’s are constant, the variance terms is dimension dependent. Since large neural network have significantly large $d$, the variance would be quite substantial. \n\n   * It is not clear why the variance term behaves as $O((n\\tau)^{-1/2})$ if $E \\leq n^{-3/4}\\tau^{1/4}$. It is important to give further details.\n\n   * The authors compare the convergence result with [Yu et al. 2019], but the variance term in that paper is proportional to the variance of SGD operator. On the other hand, in Theorem 3, the variance term depends on $d$ and $Q_{\\infty}$, which can be really large.\n\n2. The noise variance $\\sigma$ is considered as a hyperparameter, and for EMNIST and CIFAR values of $\\sigma$ chosen via hyperparmater tuning are quite small (0.01 and 0.005). Theorem 3, on the other hand, shows counter-examples that the algorithm cannot converge for small values of $\\sigma$. This seems to indicate a gap between theory and experiments. More discussion on this point would be really helpful. \n\n3. In DP-SignFedAvg (Algorithm 2), the DP noise is added only on the local update. This will give client-level privacy and not item-level privacy. In other words, DP guarantee on the aggregate model at each round against adding or removing a client should. The paper does not mention any of these details, but only has Definition 2, which is generic and does not specify how to apply it to FL. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DWXb_BH6xT", "reviewer": "Reviewer_ExtX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "", "main_review": "", "summary_of_the_paper": "The authors propose a new Federated Averaging algorithm, called z-SignFedAvg, that compresses the model updates to their signs after perturbing them with noise. They show both theoretically and empirically that z-SignFedAvg enjoys a faster convergence rate than existing sign-based compression methods. The authors further exploit the noise injection mechanism and propose a modified algorithm that has differential privacy guarantees. They demonstrate their findings on EMNIST and CIFAR-10 datasets.", "summary_of_the_review": "Overall, I enjoyed reading the paper and found the findings interesting. The proposed algorithm is also very promising, although it could be improved to pick the best noise scale at each iteration. I listed some of my ideas and suggestions above. \n\n**Post rebuttal:** I think the new experiments on additional baselines improved the paper's empirical claims. The discussion on the noise scale also strengthened the paper. And I hope to see further investigation on this point in future work. After reading other reviews and authors' responses, I have decided to keep my original score 6.", "strength_and_weaknesses": "Strengths:\n\n- The authors study an important problem and their findings shed light on the success of other stochastic sign-based methods as well.\n- The paper is theoretically sound, and the experimental results are consistent with most of the theoretical findings. \n\nWeaknesses:\n- By looking at Figure 2, it seems that the value of the noise scale should be very carefully adjusted to enjoy both a good convergence rate and a final performance. The paper misses a recipe on how to pick a good noise scale for a particular task with a particular architecture. The plots in Figure 2 also suggest that the performance could be improved with an adaptive strategy to update the noise scale. For instance, $\\sigma=0.5$ has a faster convergence rate at the beginning of the training, but later it increases the loss, while $\\sigma=2$ is slower in the beginning, but it reaches the best objective value at the end. So it would make sense to start with $\\sigma=0.5$ and then gradually increase it to $\\sigma=2$ for the best result. A recipe on how to pick the best noise scale and how to update it throughout training seems necessary to make the algorithm more practical. Perhaps the prior work [1] on how to match the noise and the compression level for the best utility of the data may help authors gain more intuition on this. It's probably hard to apply the idea in [1] (matching the entropy of the injected noise to the target distortion at the compression stage) to this problem directly since sign-based compression is not a \"good\" compressor in the rate-distortion theoretic sense. But it may still give an idea for a heuristic approach. \n\n- It has been shown in many papers that the gradients tend to get sparser during the training, both in federated and centralized training. I believe this is another motivating factor to update the noise scale during training because the compression rate changes through iterations due to increasing sparsity. Again, please refer to [1] to see why the noise amount should be increased as the compression becomes more aggressive, or vice versa. \n\n- It could be interesting to see how the proposed method performs compared to QSGD -- another famous stochastic quantization method. \n \n\n[1] Isik, Berivan, and Tsachy Weissman. \"Learning under Storage and Privacy Constraints.\" arXiv preprint arXiv:2202.02892 (2022).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject