$\beta$-Stochastic Sign SGD: A Byzantine Resilient and Differentially Private Gradient Compressor for Federated Learning
Authors: Ming Xiang
Lili Su
Venue: Submitted to ICLR 2023 (2023)
Keywords: distributed systems
differential privacy
communication efficiency
convergence rate analysis
robust optimization

Abstract: Federated Learning (FL) is a nascent privacy-preserving learning framework under which the local data of participating clients is kept locally throughout model training. Scarce communication resources and data heterogeneity are two defining characteristics of FL. Besides, a FL system is often implemented in a harsh environment -- leaving the clients vulnerable to Byzantine attacks. To the best of our knowledge, no gradient compressors simultaneously achieve quantitative Byzantine resilience and privacy preservation. In this paper, we fill this gap via revisiting the stochastic sign SGD \cite{Jin2020}. We propose $\beta$-stochastic sign SGD, which contains a gradient compressor that encodes a client's gradient information in sign bits subject to the privacy budget $\beta>0$. We show that as long as $\beta>0$, $\beta$-stochastic sign SGD converges in the presence of partial client participation and mobile Byzantine faults, showing that it achieves quantifiable Byzantine-resilience and differential privacy simultaneously. In sharp contrast, when $\beta=0$, the compressor is not differentially private.  Notably, for the special case when each of the stochastic gradients involved is bounded with known bounds, our gradient compressor with $\beta=0$ coincides with the compressor proposed in \cite{Jin2020}. As a byproduct, we show that when the clients report sign messages, the popular information aggregation rules simple mean, trimmed mean,  median and majority vote are identical in terms of the output signs. Our theories are corroborated by experiments on MNIST and CIFAR-10 datasets.

Under review as a conference paper at ICLR 2023
B B-STOCHASTIC SIGN SGD: A BYZANTINE RESILIENT AND DIFFERENTIALLY PRIVATE GRADIENT COMPRES- SOR FOR FEDERATED LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Federated Learning (FL) is a nascent crivacy-preservin learning framework un- der which the local data of participating clients is kept locally throughout model training. Scarce communication resources and data heterogeneity are two defining characteristies of FL. Besides, FL system is often implemented in a harsh envi- ronment, leaving the clients vulnerable to Byzantine attacks. To the best of our knowledge, gradient compressors simultaneously achieve quantitative Byzan- tine resilience and privacy preservation. In this paper, we fill this gap via revisit- ing the stochastic sign SGD Jin al. (2020). We propose 3-stochastic sign SGD, which contains a gradient compressor that encodes a client's gradient information in sign bits subject the privacy budget 8 > O. We show that f-stochastic sign SGD converges in the presence of partial client participation, mobile static and adaptive Byzantine faults, and that it achieves quantifiable Byziinine-resilience and differential privacy simultaneously even with non-IID local data. We show that our compressor works for both bounded and unbounded stochastic gradients, i.e., both light-tailed and heavy-tailed distributions. As byproduct, we show that when the clients report sign messages, the popular information aggregation rules simple mean, trimmed mean, median and majority vote are identical in terms of the output signs. Our theories are corroborated by experiments on MNIST and CIFAR-10 datasets.
INTRODUCTION
Federated Learning (FL) is a nascent learning framework that enables privacy sensitive clients to collectively train a model without disclosing their raw data McMahan et al. (2017); Kairouz et al.) (2021). Expensive communication overhead and non-IID local data are two defining characteristics FL. A variety of communication--avv
techniques have been introduced, including periodic av- eraging McMahan et al. (2017). large mini-batch sizes [in et al. (2020), and gradient compressors Xu et al. (2020)] Alistarh et al. (2017): [Bernstein et al. (2018) 2019): Jin et al. (2020); Safaryan et al. 2021 Wang et al. (2021). However, challenges remain.
A FL FL vulnerable to unstructured faults such as Byzantine faults Lynch (1996). Moreover, FL clients privacy-sensitive. Despite clients" privacy is partially preserved via denying raw data access, quantitative privacy preservation still desirable. Observing this, Bernstein et al. (2019) proposed signSGD with majority vote which is provably resilient to Byzantine faults. However, even in the absence of Byzantine faults, SignSGD fails to converge in the presence of non-IID data (afaayan & Richtárik (2021): Chen et al. (2020), and is not differentially private. To handle non-Ill) data, Uin et al. (2020) proposed stochastic sign SGD and its differentially-rrivat (DP) variant, whose gradi- ent compressors are simple yet elegant. Unfortunately, their DP variant does not converge and (shown in our Theorem I]. We will discuss the relations between Jin al. (2220) and our work in the related work.
system is often massive in scale and is implemented in harsh environment leaving the clients
their standard stochastic sign SGD is not differentially-
TTheir Theorem analysis contains major flaws.

---

Under review as a conference paper at ICLR 2023
Contributions. In this paper, we revisit the elegant compressor in Jin et al. (2020). We propose @-stochastic sign SGD, which contains a gradient compressor that encodes a client's ' gradient infor- mation in sign bits subject to the privacy budget 3 O, and works for unbounded and mini-batch stochastic gradients. A parameter B > 0 is chosen carefully to clip the unbounded gradients.
We first show (in Theorem 1 that when 3 = 0, the compressor is not differentially private. In sharp contrast, when B > 0, the compressor is d log ((2B + -difeertttl private, where d is the gradient dimension. We provide a finer characterization of the differential privacy preservation (in Theorem 2 and Corollary D. In addition, to help the readers interpret our DP, we show (in Proposition 2) that our compressor with / >> 0 can be viewed as a composition of a randomized sign flipping and stochastic sign SGD compressor. To the best of our knowledge, this is the first result to establish DP with signed compressors in FI..
We show (in Theorem B-stochastic sign SGD works for both bounded and unbounded stochas- tic gradient. Specifically, convergence bounds are derived for both light-tailed and heavy-tailed stochastic gradients. In addition, we show (in Theorem 4 the convergence of ß-stochastic sign SGD in the presence of partial client participation and mobile Byzantine faults, showing that it achieves eyzantine-resiliene and DP simultaneously. Both static and adaptive adversaries are considered.
As a byproduct, we show (in Proposition D that when the clients report sign messages, the popular information aggregation rules simple mean, trimmed mean, median, and majority vote are identi- cal in terms of the output signs. This implics majority vote is a counterpart of "middle-sceking" Byzantine resilient algorithms in the realm of sign aggregations.
Our theoretical findings are validated with experiments on the MNIST and CIFAR-10 datasets
2 RELATED WORK
Communication Efficiency. Communication is a scare resource in FL McMahan et al. (011
Kairouz et al. (2021). Numerous efforts have been made to improve the provable communication efficiency of FL. FedAvg the most widely-adopted FL algorithm and its Algorithm| T> save com- munication via performing multiple local updates the client side McMahan et al. 2 Wang
& Joshi (2019): Stich (2019): Li et al. (2020a). Large mini-batch size is another communication- saving technique yet its performance turns out be often inferior to FedAvg Lin et al. (2020). Gradient compressors Xu et al. (2020) take the physical layer of communication into account and are used to reduce the number of bits used in encoding local gradient information. Quantized SGD (QSGD) Alistarh et al. (2017) is lossy compressor with provable trade-off between the number of bits com- municated per iteration with the variance added to the process. However, its performance is shown to be inferior to simple compressor such SignSGD Bernstein et al. (2019), which, based on the sign, compresses a local gradient into a single bit. Nevertheless, SignSGD fails to converge in the presence of non-IID data Safaryan & Richtárik (202I); Chen et al. (2020), and is not differentially private. This is because SignSGD neglects the information contained in the gradient magnitude.
Byzantine Resilience. Despite its popularity, FedAvg is vulnerable to Byzantine attacks on the par- ticipating clients Kairouz et al. 202T);] Blanchard et al. (2017): Chen et al. (2017). This is because that under FedAvg the PS aggregates the local gradients via simple averaging. Alternative aggrega- tion rules such as Krum Blanchard et al.] (2017), geometric mediariChen et al. (2017), coordinate- wise median and trimmed mean Yin et al. (2018) are shown be resilient to Byzantine attacks though different in levels of resilience protection with respect to the number of Byzantine faults, the model complexity, and underlying data statisties in the presence of IID local data. Assuming the PS can get access to sufficiently many freshly drawn data samples in each iteration, Xie et Xice al.] (2099) proposed an algorithm Zeno that can tolerate more than 1/2 fraction of clients to be Byzantine. Unfortunately, their analysis is restricted to homogeneous and balanced local data using techniques from robust statistics. However, it is not straightforward to extend the results to non-IID data, which stems from the difficulty of distinguishing the statistical heterogeneity from Byzantine attacks Li et al.) (2019). Many efforts have been devoted to mitigate the negative impacts stemming from heterogeneous data Ghosh et al. 2019); ; Karimireddy al. (2022). Ghosh et al et al. (2019) used robust clustering techniques whose correctness crucially relies on large local dataset and local cost functions to be strongly convex. Karimireddy al. Karimireddy al. 2022 derived
2

---

Under review as a conference paper at ICLR 2023
convergence under the strong assumption of bounded dissimilarity of local gradients, which often does not hold when the data efficiency is taken into account Su et al. (2022).
Privacy Preservation. FL is renowned for its capability to decouple model training from the raw data collections by communicating only model/gradient parameters McMahan et al. (2017) between the clients and the PS. However, recent results show that both weight and gradient sharing schemes may leak sensitive information iZhu et al. (2019): Phong et al.] (2018). Two notions of differen- tial privacy exist in FL TTuex et al. (2020): (A) central privacy, where a trusted server masks the data and shares the perturbed updates with the distributed clients, and (B) local privacy, where each client protects their data from any external parties, including the server. Most of the current works focus on the perturbed updates by adding Laplace Huang et al. (2015), Gaussiar\Wang et al. (2021), or Binomial perturbation Agarwal al. (2018). The former two are applied to traditional gradi- ents/updates, and the latter is applied to compressed gradients/updates whose values are represented in terms of bits. Focusing on distributed mean estimation problem, Agarwal et al. (2018) proposed communication--fficiii the Gaussian mechanism provided that the model dimension is at most comparable to the client population size. In this work, we focus on protecting local privacy.
vroblel,Aggarwal algorithm that achieves the same privacy and error trade-off as that of
Comparison with Jin et al. (2020). While we admit that 3-stochastic sign SGD and sto-sign com- pressor in Jin et al. (2020) are structurally alike, our results depart in significant ways: their theo- retical guarantees are flawed since no explicit forms are given for the residual terms and Byzantine resilience. They consider only full-batch gradients, which may not hold as edge clients in FL often with limited computing power and storage McMaaan et al. (2017). On top of all, no partial client participation is considered. In sharp contrast, our work contains quantitative characteriza- tion of the interactions between FL system hyperparameters such as client number M, mitc-batch size n, sampling rate p. etc. We show our work converges in the presence of both static and adaptive mobile Byzantine adversaries. We build upon our / compressor on mini-batch stochastic gradient and derive the convergence bounds under light-tailed and heavy-tailed noise using a variety of con- centration bounds, which is technically non-trivial. We also show our compressor works for partial client participation. We reserve a point-by-poin comparison in Appendix A
PROBLEM SETUP
We consider a cross-device FL. system, where large number of clients are involved Kairouz et al. The system consists of one parameter server (PS) and M clients that collaborate to minimize
2021.
M
min WERd
F(w)
= M m==
Σ fm((),
(1)
where [w) == ED.,, [f (w,, x. y)] is the local cost function at client m E [M] := {1, (1, M} with the expectation taken over heterogeneous local data (xr, y) ~ Dm-
Client unavailability. Clients are also heterogeneous in their computation speeds and communica- tion channel conditions, which result in intermittent clients unavailability. To capture this, following the literature Kairouz et al. (2021) I); Li et al. (2020b); Philippenko & Dieuleveut (2020). instead of full participation, we assume that, in each iteration, client successfully uploads its local update with probability p independently across rounds, and independently from the PS and other clients.
Mobile Byzantine attacks. In each iteration t, up clients suffer Byzantine faults. Denote by B(t) C [M] the set of clients are Byzantine in iteration f, which is unknown to the PS. Let rt)) = [B(())- We refer to the clients in B(t) as Byzantine clients iteration t. We consider both static and adaptive system adversaries. In the former, the system adversary does not know client unavailability in each iteration; in the latter, the system adversary adaptively chooses B(t) according to the client unavailability in each iteration t.
Differential privacy. In addition Byzantine resilience, we also aim provide quantitative privacy protection. Towards this, we use differential privacy framework.
Definition 1 (Definition 2.4 Dwork et al. (2014)). For any with domain NI21 is e-differentially private if {M(x) E 8) S exp(e))P (M(y) E 8} holds for all CRange(M M) and for all x, y E N1 such that || w/li S
0, randomized algorithm M
3

---

Under review as a conference paper at ICLR 2023
4 ALGORITHM
Due to the randomness in data (z, y). V,F(W, I, y) varies significantly across different realizations, and could even be unbounded. To cope with this, in Algorithm [ we clip the gradient coordinate- wise, which are then used to stochastically generate signs. Formal definitions are given next.
Definition 2. The clipping function with parameter B, denoted by clip B), projects g onto [-B, B3] as clip {g, B3} max {- B, min {B, (,gh).
Definition For any privacy budget 3 2 and any clipping parameter > we define gradient compressor MB,3
(MB.ak(g) == { -1,, -1.
with probability B+
2B428
(2)
otherwise,
where 9: and (Ma,sli(g) are the i-th coordinates of g and MB,s(g), respectively.
Algorithm 1: Federated Learning with B-Stochastic Sign SGD
Input: n7.,3. 3. n, B, and
Output: w(")
Initialization: w0) {- for each m [M], and the PS samples each client m [M] with probability p to form S(0);
for 1 = 0.....
do
/+ On each m E S(t) ((t) Get n stochastic gradients ghh (!), 9 (t);
for = 1, ,d do
(t) + with probability -+ n Σi o (1).))
Imi < -1 otherwise.
2B+28
end
Report Zm to the PS; /* On the PS
Wait receive messages u. (t) Rd from the sampled clients S(t)
g(t) < sign (agg 7 (f) : m E S(t))
Sample each client m [M] with probability p obtain S(t + 1);
11
Broadcast (t) to all clients;
/* On each client E S(t ()
12
Upon receiving (t): w(t + 1) + w(t) - ng(t);
13
end
Our algorithm is formally described in Algorithm 1 which takes T, 7, 8, n, B, and E Rd as inputs, where T' is the iteration horizon T. > 0 is the stepsize, 3 2 0 is the privacy budget, is the mini- batch size of local stochastic gradients, > 0 is parameter used to clip stochastic gradients, and serves as the initial values of (0).
In each iteration t of Algorithm I client m is selected by the PS with probability Let S(t) be the set of selected clients at time Since Byzantine clients can deviate from Algorithm arbitrarily,
lines 2-8 are executed at clients in S(t) B(t) only. In each iteration t, client m E S (t) B(t) first obtains n stochastic gradients g (t), ... (t). Then it passes -E= 9 (t) to clip f B}
coordinate-wise. and compresses the clipped gradient via the compressor MB,3 lines 5 and 6. For ease of exposition, let (t) [M Σj= (t)). Finally, client m reports (t)(t) to the PS. On the PS side (lines 12), it first waits receive messages ūn (t) from the sampled clients, for which 7. (4) Fm (l) if m & (((). Then the PS passes (Tm m E S()) to an aggregation function agg, and takes the coordinate-wic sign of the function output to obtained (t). Next, broadcasts g() to S(t + 1).
For convenience exposition, no message is received from a selected client m (which only occurs when E B())). then the PS treats 7m.. as O. Notably, if E B(t), the received @m (t) could take arbitrary value. Since Im E {=1]" for m & B(t), if D (t) & {-1, 1}, then must be true that client m B(t). Thus, (t) will be removed from aggregation by the PS. In other words, it is always a better strategy for a Byzantine client to restrict à E {=1]d. Henceforth, without loss of generality, assume that C. (1) E [+1]d d for all received compressed gradients.
4

---

Under review as a conference paper at ICLR 2023
4.1 AGGREGATION FUNCTIONS
Simple mean (i.e. naive averaging) is one of the widely-adopted aggregation rule of FL algorithms Kairouz al. (2021); Blanchard al. (2017), yet it is vulnerable to Byzantine attacks. Alter- native aggregation rules such as Krum Blanchard et al. (2017), geometrie median Chen et al. (0177), coordinate-wise median and trimmed mean Yin et al. (2018) are shown to be resilient to Byzantine attacks yet with different levels of resilience protection, we show that when the in- puts of the aggregation functions are a collection of binary vectors {=1]d, the signs of the outputs of the simple mean, trimmed mean, and median aggregation rules are identical. More- over, they are all equivalent to the coordinate-wise majority vote aggregation rule. We denote by agBavg' ag8trimmed, ag8median and agBmaj' the coordinate-wise mean, k-trimmed-mest me- dian, and majority vote aggregation rules, respectively, whose definitions are deferred to Appendix
B
Proposition 1. For any given S S [M] and any given im E {+1]² for m E S. the aggregation rules agEav agErrimmed,k. with is [1)2,, agEmediar and agEmaj are equivalent in terms of their signs.
PRIVACY PRESERVATION
In this section, we characterize the DP of our gradient compressor MB.s. Over the entire training time horizon, the quantification of the differential privacy preserved for any given client can be obtained by applying the composition theorem e-differentially private algorithms (Dwork et al. 2014 Corollary 3.15). We first show that / is enablor of DP for compressor.
Theorem 1. MB. is not differentially private. That is, there does not exist a ffnitee e > f which Desimition 7 holds. When 3 >> O, MA, is d log
2B+ ) DP for all grudients.
Theorem also implies that as long as B > O, .M ensures c-differential privacy for = (d) at any iteration This might be pessimistic the presence of a deep neural network. However, is possible to reduce the order (d), and we pave the way as outlined in Theorem 2 and Corollary T
Definition 4. For any given > 0, let CB == (-00, -B) U (B, (o). For each g E RR define dist (g, CB) ;= inf g'fg g/).
Theorem 2. Letg.g E Rd be an arbitrary pair of gradient inputs such that g' + g. and define 4 sensitivity as Ai = ga lgg g'll.. MM, is maxgeg E log (+idist DDP on 9 for 3 > 0.
A
Corollary 1. Given the same definitions as in Theorem MB is (
Remark 1. Theorem gives a finer characterization of the differential privacy preserved by MB.3 when B > O. Unfortunately, this maximum is often hard to find, so Corollary tells us that we can get rid of the order O (d) by controlling the L sensitivity Ar. One way is to let B = A//d.
Definition 5. DP-flip mechanism MB {+1} + {=1} is defined as: For any b E {+1).
b
with probability 2B+8 2(B+8)
M MB
otherwise.
can be easily checked that MB, fiip is log
2B+3 -DP.
3
Proposition 2. For any 3 > 0, MB.3 MB o MB where d denotes "equal in distribution".
In Proposition we decompose our MB,3 as a composition of MB,0 and MB tip to help the readers interpret the realization of our DP. A simple example of the equivalence in Proposition given in Fig Under MM.us an occurrence of -1 in any round of one of experiments suggests its rather than g. Even if constrain the set of gradients, the ensured differential
input gradient privacy is not controllable (implied by the proof of Theorem In contrast, under M one can manipulate 3 ensure controllable privacy quantification per Theorem
5

---

Under review as a conference paper at ICLR 2023
Mu
Mil
M2
0.1
9 0.1
g' -0.05
g -0.05
(b)
Given B =
with probabiiity
with probability
3/4
with probability
5/8
with probability
1/4
with probability
Figure 1: d = 1, B 3 0.1 and two gradients g 0.1 and g' -0.05.
CONVERGENCE ANALYSIS
Our analysis is derived under the following technical assumptions that are standard in non-convex optimization Shalrt- & Ben-Davic (2014).
Assumption (Lower bound). There exists F* such that F(w) 2 F for all w. Assumption (Smoothness). There exists some non-negative constant L such thut F(w1) & F(w2) (VF(w>) wi - w2) + 2 ||l -u2l2 (isfoo for all wi; W2. Assumption (Bounded true gradient). For any coonlinate E [d], there exists B; > 0 such that < [m))]
B, for all E [M.] Let Bo maxield Bi.
Stochastic gradients can have significantly wider range than the true gradients.
Example (Norm discrepancy between true and stochastic gradients). Let a ~ (O, Ia) be stan-
dard Gaussian random vector. Let f(w, x) (w, x)) + &, where & is some unknown observation noise. It can be checked easily that for any E Rd it holds that V ff(w) VE [f[[[, (w, æ)] E [x] O, whereas the natural stochastic gradient V f(w, xx) = x. whose support the entire TR...
Assumption 4 Subb-Gaussianity). For given client m [M], at any query E Rd, the stochastic gradient 9m (w) is an independent unbiased estimate of f that is coordinate- wise related to the gradient V fm(w) as gmi(w) fm)(w) + Emi Vi [d], where Emi is zero-mean Omii-ub- Asub-Gaussian, i.e, E [Emis] O, and the two deviation inequalities P {Emi 2 21 S
exp
20 and TP {Emi S -t} 2 exp 20 hold. Let 0² == (e) Pn
Assumption (Heavy-tailed noise). Let Emi defined in Assumption 4 be zero-mean random vari- able, [<?m s a², and E <mal' [mal''] < My < xo for p' 4.
Notably, the class of sub-Gaussian random variables contains bounded and unbounded random vari- able as special cases. Tighter convergence bounds can be obtained under boundedness or Gaussian- ity assumptions on the noise: see Appendix C.I for details.
Following the road-map used in Bernstein et al. (2019); Jin et al. (2020); Safaryan & Richtárik 20021, we first establish an upper bound for the probability of gradient sign errors P (gi(t) * sign (V, (V,F (((())))) and then bound 7 Σ [[[V
((v()( to conclude convergence. Recall that gm (t) vm (w(t) denotes the true local gradient at client
Theorem 3. Choose co(n. p) max
8a2 log
B(
and B (1 (o) co log 3-36
Fix 2 1 and E [d]. Let > 0 be any given constant such that e 2(B++)) r(t). + cofn.p) and (1) 3( BB + B) z(1l coln.) JM
3 Define (t
z(1
P
VM
P (g) * sign (V.P(u(()) w()) 1-c
SabbGaassian noise): Suppose Assumption and hold, and > B. Eq. holds if
(V.F(((t))] 2 (t) + 2(B + (3) exp (-#). when the system adversary adaptive, or when is static but with r(t) < 3/z log S, and if [vF(((tt)) 2 82(t) + 2(B + 3) exp (-H) when is
static with 7(1) 2 log
p

---

Under review as a conference paper at ICLR 2023
M
(Heavy-tailed noise): Suppose Assumption 3 Jand hold, and en (VV()(()(()) 61(t)= + 41B+8) when the system adversary is adaptive, or when is static but with r(t) - p log e. and if 2 62(t) + 4(B+8) when is static with r(t)
Eq. holds for p' 2 4
Ba
n
3 p
log e
Theorem 3 says that when [.F(((t))] is large enough, the sign estimation at the PS in each iter- ation is more likely to be correct. This crucial in ensuring the convergence because Theorem implies that when | (.((((()) is large enough, in expectation, Algorithm pushes w(() towards a stationary point of the global objective F. Additionally, small V.F((w(t) implies that w(t) is already near the neighborhood of a stationary point. Different from Safaryan & Richtárik (2021) and Din et al. (2020), we neither assume the sign error distributions across clients be identical, nor require the average probability of sign error to be less than 1 1/2. Instead, we show that it is enough to let the probability of population sign errors be small when the magnitude of the gradients is large.
Theorem 4. Suppose Assumptions
2 hold. Define 8, (t) 2(B+0) z(t) + paln.p), d2(t)
P M
vM
3(B + 3)
r(t) M + co(n.p)
VM (n)
B + exp (-2), and Ez(n) 4(B+8) For any given t,
n
B (1 + En) Bo and such that 0 < +. set the learning rate r VaT
and co(n.p)
max
S02 log G
8(++B)
log 3-b0
M Bo
a With Assumption for Eo
or 5 co
(p' 2 4),
Bo
when the system adversary is adaptive or when is static but with T(1) S 2
pr log 6 6'
Σ E EIIVF(w(()IL))
(F(w(()) - FF)
Vd
Lvd 2VT
+ 2dE
2d
Σ
5000
(5)
T
VT
T
or when the system adversary is static with r(1)>
2 log 0
6
pz
T-1 T E BIIVF(w(()))))
1 (F(w((0)) - FF*) Vd c
Lvd
2d T
+ 2d3
52(()
(6)
VT
2VT
We present the convergence results under unified framework, where E(m) = En() in the case of tab-Gaussian noise, and E(n) = En(n) in the case of heavy- -ailed noise.
Remark 2. (1) The convergence rates in Eq. 5 and Eq. 66) only differ in their Byzantine terms by multiplicative factor of 3p As long as (t) is sufficiently large, the impacts of p. the degree of partial client participation, on the convergence rate upper bound is limited. The lower bound requirement on r(1) might be an artifact of our analysis in simplifying the boundary case derivation.
(2) T() T for each then the Byzantine terms in Eq. 5 and Eq. (6) become 4(B+B)rd and pas
6(B 6(B+g)rd Now consider the asymptotics in terms of T and the client number M only. If T M5
o
(VM) then both 4(B+a)rd and
G(B+3)rd scale in M with order O (x)))) which is of the same 35
pM
order as the term sala.p) in Eq. (5) and Eq. (6). the consequences of weak signal strength of the JM
compressed gradients near a stationary point of the global objective F. We note that the impacts are limited as the contribution of one client is masked as one-bit sign instead of an arbitrary value, which is also verified in the following experiments. On the other hand, if ETD T(t) = O (VT). the Byzantine terms in Eq. and Eq. (6) scale as O( ( of the same order as the first two terms. In either case, due to the mobility of the Byzantine faults, it is possible that B(() = [M], i.e every client is corrupted at least once.
(3) The residual term E(n) is an immediate consequence of using mini- batch stochastic gradients rather than true gradient as in Jin el al. 2020 It turns out that this term have minimal impact on
7

---

Under review as a conference paper at ICLR 2023
the final convergence. In fact, as long as n = 22 (log Af) (sub-Gaussian noise) or n. = ( (heavy-tailed noise), this term becomes non-dominating.
(4) When r(1) = = (VM) and n of the same order as in (3), the convergence rates become
O 7 + AM)) approaching the convergence rate of the standard (centralized, non-private, and adversary-free) SGD
as M + cc. Luckily, M in FL is often large McMahan et al. 2017)
The bounds in Theorem Cean be tightened with more structured gradient noises. We defer our results on Gaussian-tailed and bounded stochastic gradients to Appendix C.2 All of the results have sim- ilar form and differ only in the noisy residual terms. detail, the residual term (esp(nn/2) in the convergence results of the Gaussian tailed stochastic gradients is scaled by a constant 1/4v 41/22 2nr, while no noisy tail term appears in the case of bounded stochastic gradients.
EXPERIMENTAL EVALUATION
In this section, evaluate the accuracy and convergence speed of our Algorithm in terms of the impacts of client sampling p. the differential privacy protection 3, and Byzantine attack resilience. More experiment setups and comparisons with Byzantine baselines deferred to Appendix. [ We list key elements of our experimental setup for comparisons with benchmark algorithm below.
Datasets: MNIST LeCun et al. 2009), and CIFAR-101 Krizhevsky Krizeevyy et al. (0099).
Models: Simple Multi-Laayer Perceptron (MI.) McMahan et al. 2017).
Clients Data: 100 balanced workers with a Dirichlet distribution Hsu et al. (0019)
Baseline algorithms: Sign SGD Bernstein et (018 and FedAvg McMahan et al. (2017).
Byzantine baselines: Krum Blanchard et al. (2017). Geometric Median Chen et al.
2017 001 Cen-
tered Clipping Karimireddy et al. 2021). Adversary models: Label flipping, Inner product ma-
nipulation Xie et al.
2020), and the "A little is enough" Baruch al. 2019).
0.9
FedAvg
0.8
0.8
0.8
0.8
8 0.8
3 0.5
2.7
0.5
0.6
0.7
0.7
0.7
Byzanthn=0000
Byzantine-0.0c
0.4
0.4
Byzentine=0.1
0.3
Byzanthe=03
0.2
0.2
Byzantine=0.5
0.1
0.1
Communication Rounds
Communication
Communication Rounds
Communication
(a)
Sampling p 0.1
Sampling p 0.3
Sampling p 0.5
Sampling p 1.0
1.0
1.0
1.0
1.0
0.9
0.9
0.9
0.9
0.8
0.8
0.8
0.8
SIGNSCD
Byzantine-0.0
Byzantine-B.00
0.5
Byzanthe=-
0.4
0.
0.3
0.3
Byzentine=0.3
0.2
0.2-
Byzanthne-0.5
0.1
0.1
100 200 300 400 500
0
100
200 300 400 500
100 200
300 400 500
0
100 200 300 400 500
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
(b) Sampling p 0.1
Sampling p 0.3
Sampling p 0.5
Sampling p 1.0
Figure 2: MNIST testing results under non-i.i.d distribution with different Byzantine fractions and (a) no differential privacy protection: _ = 0. (b) differential privacy protection 3 B.
DS
As a decreases, the local datasets become more and more non-llI) across different clients. For a fair competition, all the experiments are under the same learning rate and mini-batch size. Notably, we treat B as a hyperparameter and fine-tune from extensive experiments because allow the stochastic gradi- ents to unbounded and the true gradient is upper bounded by Bp.
MNIST
CIFAR-10
BS
32
89.2%
46.03%
64
88.6%
46.68%
128
89.8%
46.785
256
91.8%
46.54%
Table 1: Testing results on two datasets (DS)
with different mini-batch sizes (BS).
8

---

Under review as a conference paper at ICLR 2023
We train MLP under full client participation with 80 and 300 communication rounds in the first two comparisons for MNIST and CIFAR-10, respectively. For the client sampling and Byzantine resilience, we extend the time horizon to 500 communication rounds for both datasets. Mini-batch size. We compare the peak performances of our variant under different mini-batch sizes. It is observed in thhat the Algorithm i not sensitive to mini-batch size n. This meets
Remark
(3) n = Ω (log M) or = Ω
is enough for the term not to become dominant.
ă 0.335-
0.40
0.45
0.35
0.45
0.45
0.40-
0.35
SIGNSGD
FedAvg
Byzantine=0.0
0.30-
0.30
0.30
0.30
Bycantine=
0.25-
0.25
Byzantine-0.1
0.20
0.10-
0.15-
0.20
0.15
0.15
0.15
0.10
Byzantine=0.55
Byzantine-O 0.3
100 300
100
J00
Communicatinn Rounds
Communication Rounds
Cammunication Rounds
Communication Rounds
(a)
Sampling p 0.1
Sampling p 0.3
Sampling p 0.5
Sampling p 1.0
@ 0.35-
0.45
0.40
0.45
0.40
0.40
35
0.40
FodAvg
SIGNSGD
Byzantine-0.0
0.30-
0.30
0.30-
Ryzantine-0.1 05
j 0:20
0.25-
0.20
0.25
0.20
0.25
0.25
Byzantine-O.11
0.15-
0.15
0.15
0.15
Byzantine-0.5
Byzantine=0.3
0.10-
0.10
0.10
0 100 200 300 400 500
0
100 200 50o 400 500
0 100 200 300 400 500
0
100 200 300 400 500
Communication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
(b)
Sampling p = 0.1
Sampling p = 0.3
Sampling p = 0.5
Sampling = 1.0
Figure 3: CIFAR-10 testing results under non-i.i.d distribution with different Byzantine fractions 0, (b) differential privacy protection / = B.
and (a) no differential privacy protection:
Parameter and B. The peak performances are collected and listed in Table We can observe that the testing results drop as 3 increases. This matches a trivial observation from Theorem such that the increase of 3 pushes the bound farther away from stationary point, implying our variant suffers from the data-utill data-utility- utility-privacy trade-off. For any given B, the testing accuracy comparable when the differential privacy quantification 3s are relatively small such as B E {0.1B, B}. which is fortunate as we might not sacrifice too much data utility while ensuring a privacy quantification.
B/B
MNIST
0.1
(E = 3.04d)
(E 1.Id)
(.
= 0.34d)
10.0 = 0.18d)
1.0
64.0%
61.7%
41.0%
16.2%
0.1
83.1% 1
82.9%
81.4%
41.2%
0.01
89.9%
90.0%
90.3%
76.7%
3/B
CIFAR-10
0.1 (c = 3.04d)
[.0 = 1.1d)
(.0 = 0.34d)
10.0 (c = 0.18d)
1.0
23.6%
20.7%
17.0%
16.7%
0.1
35.1% 1%
32.4%
25.3%
23.2%
0.01
45.7%
43.7%
40.7%
38.0%
Table 2: Testing results on two datasets with different combinations of B and 3/B (e).
Client sampling and Byzantine resilience. Besides normal clients, we assume a constant fraction of the reporting clients are Byzantine and only send the negation of the reporting signs to PS, the ad- versary which we call adaptive mobile attackers. Though this is a constant fraction Byzantine experi-
ment, recall that our algorithm can tolerate up to O
(VM) constant or up =T= r(t) 0 (VT
time-varying Byzantine adversaries. It is observed in Fig 2 and Fig that the Algorithm D is not sensitive to client sampling. In particular, the Byzantine on MNIST and around 44% CIFAR-10, which is direct consequence of highly heterogeneous data distributions. The accuracy drops are almost negligible when the Byzantine fraction does not exceed 0.1. We can see sharper drop as the fraction increases. However, the testing accuracy mains stable during the final training stage when Byzantine clients account for 50% of the reporting clients except when the sampling rate p is small. Two bascline algorithms with no Byzantine clients are also evaluated for comparisons. It is observed that SignSGD slightly outperforms our variant in some cases with 3 > O; however, our variant is provable d log 3-differentially private. FedAvg is inferior to the other algorithms in all cases.
peak accuracy reaches around 96%

---

Under review as a conference paper at ICLR 2023
REFERENCES
Naman Agarwal, Ananda Theertha Suresh, Felix Xinnan X Yu, Sanjiv Kumar, and Brendan McMa- han. cpsgd: Communication-cffiieennn and interrentially-prvvata distributed sgd. Advances in Neural Information Processing Systems, 31, 2018.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. Qsgd: Communicationn-cficcentt sgd via gradient quantization and encoding. Advances in Neural In- formation Processing Systems, 30, 2017.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. Advances in Neural Information Processing Systems, 32, 2019.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In Jennifer Dy and Andreas Krause the 35th International Conference on Machine Learning, volume 80 of Pro- ceedings of Machine Learning Research, pp. 560-569, 10-15 Jul 2018
(eds.), Proceedings the
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadeneshelii and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In International Conference on Learn- ing Representations, 2019.
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learning with adversaries: Byzantine tolerant gradient descent. Advances in Neural Information Processing Systems, 30, 2017.
Xiangyi Chen, Tiancong Chen, Haoran Sun, Steven Z Wu, and Mingyi Hong. Distributed train- ing with heterogeneous data: Bridging median-and mean-based algorithms. Advances Neural Information Processing Systems, 33:21616-21626, 2020.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial set- tings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1-25, 2017.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3-4):211 2014.
Avishek Ghosh, Justin Hong. Dong Yin, and Kannan Ramchandran. Robust federated learning in heterogeneous environment. arXiv preprint /906. 2019.
Robert D Gordon. Values of mills' ratio area to bounding ordinate and the normal probability integral for large values of the argument. The Annals of Mathematical Statistics, 12(3):364-365 1941.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0633: 2019.
Zhenqi Huang, Sayan Mitra, and Nitin Vaidya. Differentially private distributed optimization. In Proceedings of the 2015 International Conference Distributed Computing and Networking, 2015.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for feder- ated learning with theoretical guarantees. arXiv preprint 2rXv:2002..10940 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems in federated learning. Foundations and Trends@ in Machine Learning, 14(1-2):1-22 1100, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for byzantine robust optimization. In International Conference on Machine Learning, pp. 5311-5319. PMLR, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Byzantine robuust learning on heterogeneous datasets via bucketing. In International Conference Learning Representations, 2022.
10

---

Under review as a conference paper at ICLR 2023
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Yann LeCun, Corinna Cortes, and Christopher JC Burges. The mnist database of handwritten digits (2010). URL http://yann. lecun. com/exdb/nmisst, 2009.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. Rsa: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544-1551, 2019.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. Proceedings of Machine Learning and Sys- lems, 2:429-455 2020a.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2020b.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini-hatches, use local sgd. In International Conference on Learning Representations, 2020.
Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1996.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication -fttuniiiaatoo--ffcientnt Learning of Deep Networks from Decentralized Data. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference Artificial Intelligence and Statistics, volume 54 of Proceedings of Machine Learning Research, pp. 1273-1282, 20-22 Apr 2017.
Florence Merlevède and Magda Peligrad. Rosenthal-type inequalities for the maximum of partial sums of stationary processes and examples. The Annals of Probability, 41(2):914 960, 2013.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-perforee perfforrrfrm deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Constantin Philippenko and Aymeric Dieuleveut. Bidirectional compression in heterogeneous set- tings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint arXiv:2006. 14591, 2020.
Le Trieu Phong, Yoshinori Aono, Takuya Hayashi, Lihua Wang, and Shiho Moriai. Privacy- preserving deep learning via additively homomorphic encryption. IEEE Transactions on Infor- mation Forensies and Security, 1335)11333-1355, 2018
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, pp. 9224-9234, 2021.
Mher Safaryan, Filip Hanzely, and Peter Richtarik. Smoothness matrices beat smoothness con- stants: Better communication compression techniques for distributed optimization. In M. Ran- zato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances Neural Information Processing Systems, volume 34, pp.
2021.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Sebastian U. Stich. Local SGD converges fast and communicates little. In International Conference on Learning Representations, 2019.
Lili Su, Jiaming Xu, and Pengkun Yang. Global convergence of federated learning for mixed re- gression. arXiv preprint arXiv:2206.07277 2022.
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wengi Wei. Ldp-fed: Federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop Edge Systems, Analytics and Networking, pp. 61-66, 2020.
11

---

Under review as a conference paper at ICLR 2023
Boxin Wang, Fan Wu, Yunhui Long, Luka Rimanic, Ce Zhang, and Bo Li. Datalens: Scalable privacy preserving training via gradient compression and aggregation. In Proceedings of the 2021 ACM SIGSAC Conference Computer and Communications Security, CCS 21, pp. 2146-2168, 2021.
Jianyu Wang and Gauri Joshi. Adaptive communication strategies to achieve the best error-runtime trade-off in local-update sgd. Proceedings of Machine Learning and Systems, 1:212-22: 229, 2019.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In International Conference Machine Learning, pp. 6893- 6901, 2019.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantine-tolerant sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270.PMLR, 2020.
Hang Xu, Chen- Yu Ho, Ahmed M Abdelmoniem, Aritra Dutta, El Houcine Bergou, Konstantinos Karatsenidis, Marco Canini, and Panos Kalnis. Compressed communication for distributed deep learning: Survey and quantitative evaluation. Technical report, 2020.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659, 2018.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-But Buch E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 32, 2019.
12

---

Under review as a conference paper at ICLR 2023
A COMPARISONS WITH JIN ET AL.
2020)
Jin et al. 2020
Our work
Batch-size
Full-batch (True Gradient) [Eq. (33)
Mini-batch Stochastic Gradient
Gradient
Sub-Gaussian (bounded subset) and heavy-tailed
Distribution
Bounded [Theorem 3]
(M) as a function client number M without explicit form [Theorem 2 and Remark 3].
Weak Signal Strength
cufm.p) VM
Implicit forms without quantitative results [Theorem and Remark 6].
(B+5) Ei m(6) TM
Byzantine
Residual
(exp (- ()) for Sub-Gaussian noise:
Gradient noise
No, since only bounded gradients are considered.
[1/n*) (p' 2 4) heavy-tailed
noise.
d dloo(1 + / for arbitrary gradients;
No for sto-sign compressor; flawed arguments for DP-sign compressor.
Differential Privacy
A for gradient pairs with bounded 1 sensitivity Å1.
Thcoretically and empirically verified, and build adaptive Byzantine adversaries on it.
Partial Client Participation
No.
Table 3: Point-by-poiin comparisons with Jin et al. 22020).
B ALGORIHTM
Definition 6. Let S S [M] and let Um E {+1 for m m
(A.1) The mean aggregation rule is defined as agBag ((üms m E S)) + Omm
(A.2) The coordinate-wise k-trimmed-mean aggregation rule, denoted by agEriimme takes k N and {Tm- m }} as imputs and aggregates each coordinate E [d] follows: (l) sort (Tmis m E S), where Uni is the i-th coordinate of Ums in an increasing order; (2) remove the top and bottom k. values, and denote the remained clients w. r. I. coordinate as Ri; (3) if R, =0, then agBrimmed,kk ({ūmy m E E = for (or-1) uniformly at random; otherwise, agEirimmed,kk (fums m S}) = T.. EmER, ūm-
(A.3) The coordinate-wise median aggregation rule, denoted by agBmediamr aggregates each coor- dinate i E [d] as follows: it first sorts the (Tmis m. E S} in an increasing order. If [S] is even, agEmedian, (fum, m S)) outputs the average of the elements whose ranks are [s] and [S] + 1.
Otherwise, agEmedion, (fūm, m E S)) outputs the element whose rank is [1.1
(A.4) The coordinate-wise majority vote aggregation rule, denoted by agEmaj aggregates each coordinate i E [d] as follows: If there are more than -1 in { (ūmir in E SS,, then agEmaj, (fum: m E S)) outputs 1. If there are more -1 than 1 in {ūmis E S), then agEmaj,i (fūm; m E S}) outputs -1. Otherwise, aggmedion, ((ām, E 8}) outputs 0.
C ALTERNATIVE RESULTS
C.1 ALTERNATIVE ASSUMPTIONS
The following two alternative assumptions on the randomness of stochastic gradients are of decreas- ing levels of stringency.
Assumption 6 (Boundedness). The l: norm of all possible stochastic gradients is upper bounded. Formally, let m E [M] be an arbitrary client and g be an arbitrary stochastic gradient that client m
obtuins. For any coordinate i E [d]. there exists B, > O such that [gal < B, Let B maxte(d] B;.
The following alternative assumption relaxes the boundedness requirement, and allows the stochastic gradients to be supported over the entire Rdd.
13

---

Under review as a conference paper at ICLR 2023
Assumption 7 (Gaussianity). For given client [M]. at any query R. the stochastic gradient 9m (w) is an independent unbiased estimate of V fm (w) that is coordinate-wise related to the gradient V (m(w) gmm(w) fmi(w) Emi Vi E [d],
where Emi ~ N (0, mms) Let o² = maXme|M],iele o
C.2 ALTERNATIVE CONVERGENCE RATES
Corollary 2. Suppose that Assumptions 3 and
hold. Choose B (1 + 6o) for en a Bo
and co(n, p) max {
8 6
log
8(B+3)
log 3-36
Fix t 2 1 and i e [d]. Let > 0 be any
given constant such that <
3
When the system adversary is adaptive or when the system adversary is static but with T(t) S
2 log 6 if (FF(((() 2 2 r(t) +
B+8 exp
(-3) + cu(a.p) then Eq. 44) holds.
p
2/2
VM
When the system adversary is static with r(t) > pa log c. if V.F(w(t)) Z 3(B+
+
B+8 exp (- saln.p), then Eq. holds.
2/2x
VM
Corollary 3. Suppose Assumptions 1
2
and 7 hold. For any given T, B (1 + Bo the learning rate Tj VeT and co(n,))
for 6D
Bo and such that 0
max
Suz
log G
18(+0022 V
log 3-50 5c
When the system adversary is adaptive or when the system adversary is static but with r(t) s 2. log 9 have
[[]VF((())I 1 1=0
(F(w(0)) - FF)
Lvd
d -BB B) exp (-2
E BIIVF
T
VT
2VT
/2
(n(
BB + B) ET=O T(t)
+2d
4d
VM
PTM
On the other hand, when the system adversary is static with 7(1) 2 log g. we have
E (I)))( 1 (F(w(O))
V') -(
Ltd. d
(B BB+ exp ( (-2
VT
2VT
V2T
+2d (),
(B + B) ET-1 r(t)
6d
VM
TM
Corollary 4. Suppose that Assumption
holds.
Choose B
B and ca(n,))
max
Sa2 log
G
8(B+0)
log 3- 5c
Fix 2 1 and E [d]. Let e > 0 be any given con-
stant such that <<?
When the system adversary is adaptive or when the system adversary is static but with 7(t) s 2(++))
2 log 6 if ((((((() 2 pM T(t) + ca(m.p) then Eq. 4 holds.
VM
When the system adversary is static with r(t)
2 log if (V.F((((()
>
3(B+ 7(1) +
B+ 2/26 cxp (-7) caln.))
VM then Eq. 4 holds.
Corollary 5. Suppose Assumptions and hold. For any given and c such that 0 < c
5
set the learning rate as = VeT and co p) = max {
G 2 8222 log
8(
log 3-50
6
14

---

Under review as a conference paper at ICLR 2023
When the system adversary is adaptive when the system adversary is static but with r(t) 1
p log we have
2 @
1 (F(w(D)) - VF Lvd
co(n.
(B 3) E1= T(t)
Σ t=0
+ 2d
+ 4d
T
VT
2VT
VM
PTM
On the other hand, when the system adversary is static with r(1)
3 log e. we have
p
(F(u(()) - PT*) vd
L Lvd
co(n.))) + 6d
(B (B 3) -1 -(1)
[[IVF(1((0)I)))
2d
T
VT
2V
VM
TM
t=0
D PROOFS
D.1 AGGREGATION FUNCTIONS
Proof. [Proof of Proposition (Equivalent to Majority Vote)] The intuition behind this proof is to show that the signs of all the aggregation rules mentioned in the theorem statement, given Um E {=1] for m S, are equivalent the sign of the b-trimmed-men mean aggregation rule.
We first show that for any k < SS//2, the signs of the outputs of the signs of the aggregation rule agGuimmed, are the same. When & |S| /2, it holds that R, # 0 for each E [d]. Thus, the [8|/2 deterministic.
aggregation rules agEuimmed.e with
For any given coordinate
[d]. if the sign of agSnimmed,k is O, by definition, know that there equal numbers of 1 and -1 in {umi m RR), and that the top (resp. bottom) A elements removed from { {ūmi m E } are 1 (resp. 1). That is, there are equal numbers of 1 and -1 in (ūmi: S). Hence, for any k' j k. as long as the remained set R2 after trimming nonempty (which is ensured by the condition that k' < S 22. it holds that a ({ūmi m E S}) = 0.
the sign of aggnimmed, is 1, we know that there are more -1 than 1 in {ūmm: : m E Ri). and that the bottom & elements in {ūmi : m E S} are all -1 whereas the number of in the top elements is at most k. That is, there are more 1 than in {ūmmi long as the remained set R2 after trimming is nonempty, the sign of agBuimmed,k' ({Tmi m E S}) is 1. Similarly,
S}. Hence, we know that for any k, as
show the when the sign of agSnimmed,k is 1.
The above argument, combined with the definition of ag8maj immediately implies that when k < ///2, the signs of agBuimmed,k and ag&maj are the same.
Finally, since agSivg is agBerimmed,0 and ag8median agg ب the signs of aggag: aggmedian and aggrimmed, for k < |S|/2 are all the same, proving the theorem.
D.2 PRIVACY PRESERVATION
2014 Corollary 3.15) Let M; Rd [t1]d be an e:differentiully private algorithm for [k). Then Mp((z) (M1(z), MM(xz) is Σt diiiferrentiall private.
Theorem 5. (Dwork et al.
Proof of Theorem (Necessity of (3. We first consider the setting when / = Let
G = (g E Rd; Di s.t. min(lg: - B), 1.l..+ + + < 1}.
Let E G. Without loss of generality, let us assume that [g: -B < 1, where gı is the first entry of
g. g1 2 B, then there exists g' E d such that g' + g. g (-B, B), and l|g -g'll S 1. Let
91 and 1 be the compressed values of gı and g under our compressor in Eq. 2 It holds that
P p( -1) 1
B (o
B - clip L3,
B - clip (g), B} B
2B
P [g] 1}
3-clip ( BB
B B-clip (gi,
15

---

Under review as a conference paper at ICLR 2023
If 91 (-B, B), then there exists g' E RR such that g' gg gi 2 B, and l g'll1 S 1. We have
P (gi -1] 1} B B-elip(g..B) [gi 1}
B clip (91. B}
B clip (gr, B} oo.
2B
B B B clip {g B}
B
2B
Since a finite differential privacy quantification does not hold for any pair of gradients and g'. no differential privacy implies per Definition] |
proving the first part of the theorem.
When / > O, for any 9, g E IR such that g' + and lgg - g'll S 1, and for each coordinate i [d], holds that
B+8- -+B-cli
9 = - P (9. -11
2B+20
B+ 8 clip {g', B}
2B +
B- B..
B +-3-- clip {g1, B}
3
2B+28
Similarly, we can show the same upper bound for (g/ = 1 ordinate, the compressor Ma, is coordinate-wise log
/P (g: = 1}. That is, for the i-th co-
2B+88 3
differentially private. By Theorem
5 we conclude that the compressor MB,3 is d log 2B++
differentially private for the entire
gradient.
Proof of Theorem 2 (Smaller Collection of Gradients). For each coordinate i [d]. it holds that
B48- (44
P ( 1}
B + clip (g/. B}
2B+23
P [ 11
B+3 BB
B + 3 - clip {g.. B}
2B+28
B + 3 - clip {gi, B} + clip {g:, B} clip (0/, B}
B + 3 clip {g., B3}
[g g
< 1+
B 3-
clip {g. B}
A
< 1 +
B - clip {gi, B}
A
$ 1 + 8 + dist (g., CB)
By Theorem we conclude that the compressor MA is maxges Σi log (1+ 3tdist differentially private for all gradients g E g.
Proof of Corollary (Bounded DP with Bounded Sensitivity). By Theorem
2 conclude that
the compressor MB.3 is maxges Σ log + 3+dist(g.Ce) differentially private for all gra- dients g E g. turns out that this bound can be relaxed, and we start the derivation from Eq.
A
9i g
0
Now consider the coordinate collection of the gradient pair, by Theorem 5 remains to bound
gg
g.
gil
log
+
dlog
[Jensen's inequality]
3
3
A
$ dlog
1+
d3
A
follows from log(1 + x) < a when 0.]
3
16

---

Under review as a conference paper at ICLR 2023
Proof of Proposition| 2 (Equivalent Composition). Let R be arbitrary gradient. To show this proposition, it enough to show P ([MB,sli(g) = 1} = [[M MB.uli(g) = holds for any i E [d].
To see this,
P B.ii (B,oli(g) = 1) = ()
= 1& (1) = =
+ +P((MB.))()))
M.pppp (-10- --1
+ clip (g:, B) 2B + 8
B clip {g., B3
8
2B
2 + 3)
2B
2(B + 3)
B 3 clip (gi, B}
2(++
P ([(M) 1).
D.3 CONVERGENCE RESULTS
Proposition 3 (Bounded Random Variable Variance Bound), Given random variable X and clipping threshold B 0, if = E [X] E [,B, then var (clip (X, B)) S var (X) = o².
Proof of Proposition 3
var (clip (X, B)) =E (clip(X, X, B) E [clipp (X, B)])
=E (clip(X, B) - [E 2 (E [clip(X, B) - =X)²
< (clip(X, X B) E [X])²]
(8)
For ease exposition, we assume admits a probability density function f(x). General distribu- tions of X can be shown analogously. It follows that
(clip(X, (X, B) - E [
00
[ (x ((=)))(())dr++ +
B
(B f))f(z)dr +
(-B f
-
(x 11) f())dr +
(x- - 11) f(x)dr
(x (x- (x=))){(z)dr
var (X) = 2
(9)
Combining and we conclude var (clip (X) I var (X) = 0².
D.3.1 SUB- SUB-GAUSSIAN AND HEAVY-TAILED DISTRIBUTIONS
Proof of Theorem (Light and Heavy-tailed Sign Error). Recall that
[MB.sle (+ Pme(t)
if m (N()));
gmi(1) (1)
if m BBt).
where * is an arbitrary value in {-1,1}. For any client E [M] and any coordinate E [d], let
Xmi (me((e)) 1 (Gmistsigu( # MMM }
and X (meste)) 1 [Im Ey oln (sigul t ΣM mm:)]
Notably, if B(t), then it is possible that Xmi # Xmii otherwise, Xmm Xmi-
Without loss of generality, we assume the true aggregation is negative, i.c., sign (V,F (w(t)) -1. The case when sign F (wo())) can be shown analogously.
17

---

Under review as a conference paper at ICLR 2023
For ease of exposition, we drop condition of w(() in the conditional probability expressions unless otherwise noted. holds that
M
M
|S(!)
IP
sign
Σ m==1
Imi
#
--1
S
P
X mi
M
2
m=1
|S(1)
P
X mi
Σ
X 2
2
mE)(()
mEB(!)
|S(t)
P
Σ
X
Σ
Xms
2
(EN(()
mEB(1)
M
S(())
< P
Σ
Xm
(10)
2
TV
mEB(()
Next, we bound Eme Xii and E Emett(r Xmi separately.
When the system adversary is static, i.e., the system adversary does not know S(t), corrupts clients independently of St). Hence,
Σ Xms S
Σ
1 (mES(()))
(11)
mEB(L)
mEB(1)
We know that if r(t) - nd log then EmEB(I) (mES(r)) at least 1 - - is true that EmeB(H) (mES(O) - 3 pt)).
2 log 6 Otherwise, with probability p2
On the other hand, when the system adversary is adaptive, it chooses B(t) based on S(t). In partic- ular, if [S(t)) < Tt)), then the adversary chooses B(t) = S(t). Otherwise, i.e., [S())] > r(t), the adversary chooses an arbitrary subset of S(t). In both cases, holds that
Σ Xmi S
Σ MEB((1)
[(me((0) I min(((tt) S r(t).
(12)
mEB(L)
For case of exposition, we first focus on adaptive adversary and will visit the static adversary towards the end of this proof. Observe that [S(t)] = EM= 1 (mES(t)) Let Yms Xmmi ((0)) Conditioning on the mini-batch stochastic gradients Imss P we have
E Yms
gmi
E
Xmi
g
p
p
clip
Σ
Pmis B
2
2B + 23
==1
Taking expectation over gimso
Pmm we get
E Ymi | ginss ... Imms
= E
E
Ymi
Pms
p 2B + 2B
pgmt 2B + 2,3
プド= Pmi
E
E
Vine
Imss"
...
Ims
p 2B + 23
pgmi 2B + 2/3"
(13)
turns out that E
Vmm
g ... Pmm
En gim
is small:
2B-22
-pp n -5=1 gin
E
E
Imni
.mm.
p
2B + 23
BP
1
E
2 B- BP
1 Σド= 1= J
S BB
E
1 E g (1 -
Σグ Lin. 2B]
2B + 2,9
2B + 2,3
(A)
(B)
18

---

Under review as a conference paper at ICLR 2023
We bound (A) and (B) for sub Gaussian and heavy-tailed noise separately. First, for sub-Gaussian distributions with Assumption we have
(A)
B
P
9ms
E
Fmi
B
Σ
Tms
2B + 23
71
11
n
j=l
B
(B- gmi)
2B + 28 exp
20 ms
B
B
exp
2B + 23
20 mi
1
2
exp
2
[since
>
Bu b.
and
E
1 2j== j=1 Iim 1 [1 - Bim. |2B]
(B)
2B 23
1
2=== Pmi <1) dl - 5000 P {
2aj=1 Pmi > 17
2B + 23
P
1
Σド= j= Pmm
E
Σø=ı Pmss
< -
E
1 n
プ== gmd) jat
11
n2
2B + 2,3
exp
(1- 1--gmil" 20ths/n
dt
00
Mill's ratio Gordon 1941)
2B + 2,3
B
20 mil/ /n
2 gmi)
gmi) 12
2B + 23 -00
(t
gmm)
20 20
exp
20 202.//n /n
dt
02
(t Imi)
(t
Imni)
(2B + 2.) (B + gmi)
20 nn
exp
20 2
mi In
dt
D
exp
nE6 B2B + 2,3)
2n ms
2
neo Bi
2nd B
exp
20 mi
[ > 0 and B = + 60) ()) Bo > Bo
1
exp
2n
2
where the last inequality follows from the choice of 60
6. Combining the bounds (A) and no
n gim 28+23
(B), we get E
E
Yms
p
S pexp ( - 2). Hence,
n (-m)
pmmi
B Y mi
S
pexp
(14)
2B + 23"
19

---

Under review as a conference paper at ICLR 2023
Second, for heavy-tailed distributions with Assumption
5
we have
B
(A) -
P
Fmst
E
g gm
B
E
mm
2B 23
n2
B
P
Imi
EB
Ims
n2
B
gmil
2B + 23
B
IE
Σ
j=1
gms
E Σ j=1 Ind
Markov's 's inequality)
2B + 2/3
ne
gmil
B BE TR
j=1
E
Fin gmms
+ B EE= Pim - E
Fmm
(2B + 23) |B gmni 1
Rosenihal-type inequality Merievede Peligrad 2013
n. + 11 Mp
[M S M for 2 4]
n² B gmll
Mp 1
mf d c Bg
and
1
Pmm
1 [ Ej P 128
BB)
2B + 23
B
Pus <1)
di
JB
4000
ーー Pmi > > de
1=
2B + 23
P
a
Imi
E
1
-Ø=1
< E 1 EE= Fmo dtt
2B + 23
2Mp
dt [similar argument as (A)]
2B 23
n 1t
F
Iml
1
2B + 23 11 11 BB
-p 1)n²
of (p'
1)n
MP Bo
where the last inequality follows from the choice of
Combining the bounds of (A) and
Σn gin
(B), we get E
Y mi
Imi
p
2B+23
Hence,
2p
Pmmi
+
(15)
ms
2B + 2/
n
Let us consider two mutually complement events E and Ez:
31-
M clip
gmms
1
clip
Imis
5 co(n, p)
VM
2(B + 8)
n
2(B + 3)
71
4(B + B)
1=1
M
M
co(n. p) 4(B + B)
E2
Σ
clip
Σ j=1
gine B
-B
clip
Σ
g'mc B
VM
2(B ()
2(B +
3)
m=
j=1
20

---

2M Under review as a conference paper at ICLR 2023
We have
M
[S(()
M
X mi
=(1)
S P
Σ
mi 2 -7(1) | E1 + P(2))
(16)
By Proposition
know that
Pms: B )
1 Σ
-op mit S 1
var
clip
S var
Tms
var (gms)
j=1
In addition, clip Ei= amii B) is bounded and thus Sub-Gaussian. Hence, we have
(r..p)
PP ( S Sexp
n
Since co p)
Sa
log e²
we have IP [ S 6.
For the first term in the right-hand side of Eq. (66, we have
M
P
Yi 2 (t)) &
m=1
M
M
mi
y
mi
Imii
2 -T(1) E
mi
Imi
Ims
1
(C)
Recall that E Ymmi
Ims
2B423 clip
E B)
We have
M
1
(C) & -r())- 2B + 228
Σ
clip
Pmis
B
E
m=1
j=1
M
(n,(1))) p)
2 -T(() E
clip
Σ 1=1
g B
VM
2B
23
4(B 3)
m=l
M
pco(n, p)
-t(t)) Σ
E
Y
M
1788
4(B + B)
m=1
-t(()) Mp exp (-%)
PM V (ww(()))
pca (x.p)
M [Sub-Gaussian Noise]
2B
2 (t) 2Mp
PM
V ((u(t)
(m)(p.))
M
[eaay--taildd Noise]
2
4(++3)
PM Recall that v,F(w(t) < O. When 2(+
v.F(w(t)) 2 T(1) + Mpexp (- 5 + pen(n.p) M
2
(sub-Gaussiaa noise) when
PM
v.P(w(()) 7(1) + 2M4p n + 2
pon(n.p)
MM
(heavy-tailed
2
noise), we get
pco VM &
Yms 2 -(t)
E3 <P
mi
E
mi
4(B + B)
S exp
8(B + B)2
3 5c
6
21

---

Under review as a conference paper at ICLR 2023
where the last inequality holds because co (1,
((B+3) p²
6 log 3-56"
Therefore,
for
adaptive
system
adversary,
choosing conclude that if PM
co(n, p)
max
S log
n
8(B+8)²
p
log 3-50
XB+3
VFF(w(()))
(t) + Mpexp (- +
pe.(n.)) 2(++B)
VM Suub-Gaussian Noise) or if 2(
pd
v,F(u(t))
M
(t)) + 2Mp + (n)(n.p)
VM (heavy-tailed noise), then
2(B+8)
M
1-c
sign
Σ
gml
* sign (V,F(w(t))) w(t) S
M
2
m=1
Otherwise, P
sign
Σ M
2 Imi)
# sign (V.F(w(t))) w(t)] } 1
It remains show the case for static adversary. When 7(1) 3 log _. we bound Eq. (10)
p-
M
S(()
|S(()
7(1) }.
P
X mi
Xmi
IP
2
mi
mE)(()
When r(t) >
Ts log 2. we bound Eqq (TO)
as
P
M
S(())
Σ
Xmi
<P
M
SS()]
3p
2
(()
+ c
2
mi
2
6
m=11
mEB
m=1
The remaining proof follows the above argument for adaptive adversary.
Proof of T'Thorem (Sub-Gaussian and Hcavy-tailed Convergence Rate). By Assumption we have
L 2 ww + -) w()l?
F (w(t 1)) F (w(t)) = (VP(w(t)) +) -w))(())
= FF(w(())) (gg (V.F(w(0))))
Ld
VF(w(()) Loi (V.F(w()))) +
2 17²
Ld "
-//lV(((((t)) + 2n FF / (()(()))))) +
where VF(((()), is the i-th coordinate of VF(w(())). Then, by conditioning on parameter w(t).
get
E F (w(t: + 1)) (w(tt) [w()]
$ n/ (F((()) + 2n Σ FF (VF(())(( + Ld
d
2 1
d
Ld -" 1 2n -->)\((((()]]
V vF(((())) sign (VF(w(t):))
Recall that E (n) 2BB B + exp exp (-7), and Ez(n) 1(++0) Define
A v,F(w(t)]
2B+9)
PM r(t) + co(n.))
+2 + 3) exp (-
VM
A2 v.F(w(()) > 2(++9)
PM r(t) co(n.p)
4[++3)
VM
22

---

Under review as a conference paper at ICLR 2023
In the following proof, denote A A1, [(n) (n)n) for tub-Gaussian noise and A A2.
[(n) = =2(n) for heavy-tailed noise.
We now have two cases:
First, when the system adversary is adaptive or the system adversary is static but with r(t) -
2 2 log g then
[ (wo(t + 1)) F (w(()) [c(()]
Ld 12 + 2n
""
V FF VF((())))P(. + sign (V.F(w(())) ((A)
21
VP(c((t) (ā. + sign (V.F(w(t)))) {Aa}
Ld " (F(o(()))
(F(1 1-c (A}
21
2(B + (1)(())
pM + co(n.p)
+ {(m) Foot
2m
VM
< {-nd]VF(u((t) + Ld
2 1²² + 2nd co(n,p)
(B + 3)r(()
+ 4nd
+ 2nd3(n).
VM
PM
Therefore, by Assumption | we have
F' - FF((()) < E F (w(TT) F (w))
T LOT
co(n.p) VM
(B + 3) ΣT- T(()
s nc
E
(F
+ 2ndT
+ 2nddT(() + 4nd
2
PM
Rearrange the inequality and plug in 1) Var get
< F + LAT
co(n, co(,))
(B +.)) T- r(t)
E
+ 2ndr
+ +2ndTE(n) + 4nd
VM
pM
[[]VF(<(() 1 (F(u(0)) - FT) Vd
LVd
2d (o(.p) 4d (B+ 11+ 1- T(t)
1==
+ 2dE(n)
VT
2VT
VM
pTM
Second, when the system adversary is static with r(1) we get
p log 6 follow similar proof as above,
[[]VF((()) 1 (F(w(0)) - -F)) Vd
LVd (o(p..))
+ 2d 20
+6d (B (B+ 3)+ (B+ r(t)
+ 2
VT +
T t=0
2 VM
TM
D.3.2 GAUSSIAN DISTRIBUTION
Proof of Corollary 2 GGusssia Tail Sign Errors). Most of the proofs are the same with Theorem
We start from Eq. 13
23

---

Under review as a conference paper at ICLR 2023
turns out that I
Ymm
Imss :. [ms]]
- p
# Ei Iiii
2 -
is small:
(B gms) P Ej=1 gmi 2 B
> j=1 gmi
Ym
gmis:
Fiii
-p 2B
p
2,8
2B 23
(A)
(B + gms) P { E Pine S -B
2B + 2/3
(B)
E (((- / P + gml
1 (I 2 8 128
2B + 28
(17)
We have,
(2B (2)+
Omi/ Vn
(B gmal )²
Oms/ Vn
(B gmi)²
SB -gmi)
eep
exp
B gmi
2TT
2 (o VT))
22T
2 (om VT)
(2B + 23) (B)
B B-gmi dms/ v
(- (B gmmi)²
(B gmi)
exp
B gms ams/ VT
+1 2t
(ami/ VTi)
(amil VT)
Tmil Vn
(B gms) )2
exp
(B 92 + (ami/ VT))
2m
(amii vn)
(2B + 23) (C)
=- S
=-
x Imi
exp
(- (x Imi)2
dr
B
Imc
cxp
(x gmi)?
dr;
22Tomi/ Vn
20mmi// vTi2
2 /n
2 (ami/ vn)²
Umi/ V
(B + 9mi)²
(B gmi)
exp
exp
2
2 (ami/ VT))
2 (ami/ vn
where (A) and (B) follow because of Mill's ratio Gordon (941)
Combining (A), (B), and (C), get
p (ammi/ Vn)
(- (B + gmi)) )2
Pgmi
17
<
exp
+
/2T (2B + 2,8)
(B + gmi)² 2 (ami/ mTj
2 (0 vTi²
2B + 28
p (ami/ Vn)
cBBBg
Pgms
exp
V 2T (2B + 2,))
B + (ams// Vn)²
2 2@mmi \mmi//nn)
2B + 2/3
p
71
mg
exp
+ 2B + 23
4
2
where the last inequality follows because co
B, and B Bg + En eg Bo-
24

---

Under review as a conference paper at ICLR 2023
For the first term in the right hand side of Eq. (16), we have
M
P
mi 2
-t() & E
m=1
M
M
M
=P
mi
Σ m=1
mi
gmis ... Imi
2 -(()) E
mi Imi ...
Imi
E1
m=1
(D)
Recall that E Ymm
Ims
:Ims
2B clip
IB+23
1 و Pmi. B)
We have
M
( 1=1==-(())
p
Σ
clip
Σ
Tmiis
2B + 2,3
n2 j=l
2 -T(() E
P
clip
n
gmi BB
peo(n. p) VM
2B + 2,8
71 j=1
4(B + 3)
peu(n. p)
= -T(( - Σ
E
mi
VM
4(B + +B)
m=1
2 -t()
Mp
exp
n
p
M
gmi
4(B + 3) VM
peu(n. p)
4v2TT
2
2(B + B)
m=1
Recall that V.F(w(()) < O. When
Mp
v.F(w(()) 2 7(1)
V
Mp 4/2m
exp (-
pnn(n.p) VM, 2(++B)
2(++B)
get
M
M
M
pco(n.p) p) VM &
Ym 2 -(t) | & <P
Y mi
E
Σ m=
Yms
, 2
4(B + B)
m=1
m=1
p² c
< exp
8(B + 182
5c
6
where the last inequality holds because (o(n,p) 2
6 B(++0) log 3
The remaining proof follows the arguments in Theorem
Proof of Corollary 3 Gaussian Tail Convergence Rate), This proof follows from Theorem We also consider two cases here.
First, when the system adversary is adaptive or the system adversary is static but with r(t) <
2 log C plug [vF(((())) 2 2(B+9) Mp T()) 2/27 exp
(B+L)
(- + so(u.p) we get
p
VM
ELIIF( (F(w(0)) - Vd Lvd. co(n.))
d
2d
(B BB+ exp
expxxp
(-r
T
VT
2/T
VM
22T
BB + 3) Σi'-1 7(1)
+4d
pTM M
25

---

Under review as a conference paper at ICLR 2023
Second, when the system adversary is static with r(t) ((B+
>
pa log et plug in (.F((((t))
2
(B+2) exp (-n/2) + so(n.)) get
2v2x
VM
1 (F(w(0)) - F') Lvd co(n.p)
_m)
E [[]V
2VT 2d
+
(B exp
T t=0
VT
VM
2
(B + 3) Ef= T(t)
+6d
TM
D.4 BOUNDED STOCHASTIC GRADIENTS
Proof of Corollary 4 (Bounded Gradient Sign Errors). This proof follows from Theorem No-
tably, if we choose B B, clip 1 2j=1 Pmi: B)
= Pirt by Assumption 6 Thus, the
bias introduced by the tail bound will be gone.
For the first term in the right-hand side of Eq. T6), we have
M Ym 2 -T)) &
P
m=11
M
M Pii .. Pimi 2 -(() - E
M
=P
mi
Σ m
Yms
Y Ymi
Fmir
Imi
| Eع
m
(A)
Recall that E Ymme Ims:
. 2B423
1 2j=1 Pnd. We have
(A) &A)
Ims &
2B + 2/3
n
2 -T((1)
P
Σ
M
n
Imi
pcn(n. p)
VM
2B + 23
4(B +
===1
j=1
M =-((1) Σ
4(B + 3) VM
pCo (n, p)
TH
m=1
M
2 -T((
p
pco(n, p) VM 4(B + 3)
9mi
2B + 3
m=1
Recall that v.F(w(t)) < O. When v,F(w(t))
2(B+8)r(() Mp
+
ca(p.p) VM
we get
M
M
M
pco(n. p)
Ym 2 -(t)
<P
mi
E
Yms
Imi
2 4(B + B)
VM
El
m=1
m=1
m==1
( p)
A exp
8(B + 8)3
3 5c
6
The remaining proof also follows the arguments in Theorem 3
Proof of Corollary 5 (Bounded Gradient Convergence Rate). This proof follows from Theorem
We also consider two cases here.
26

---

Under review as a conference paper at ICLR 2023
First, when the system adversary is adaptive or the system adversary is static but with r(t) 1 log c. plug [F((((t)) 2 2(B+8)7(1) co(n.p)
Mp VM
we
get
!
(F(w (0)) FT) Vd
Lvd
2d co
(B+ + 3) Et=o T(1)
E [[V[(((())
+ 4d
T
VT
2VT
VM
pTM
Second, when the system adversary is static with r(1)
>
log oe plug in V,F(w(())) 2
p
3 ((++))r(1)
ca(m-p)
we get
M
VM
(F(w(())- F²) F*) vd
Lvd
2d 2d co(n.p)
+ 6d (B 3) 21 7(t)
Σ [[]VF(((()I]]
T
VT
2VT
VM
TM
E EXPERIMENT DETAILS
E.1 DATASETS AND PREPROCESSING
MNIST LeCun Le et al. 2009). MNIST contains 60, 000 training images and 10, 000 testing images
of 10 classes.
CIFAR-10 10 Krizhevsky et al. 2009).. CIFAR-10 contains 50, 000 training images and 10, 000 testing images of T0 classes.
Implementation. We build our codes upon PyTorch Paszke et (2019). We run all the experiments with 4 GPUs of type Tesla P100 and GPU of type RTX 3060.
E.2 PARAMETERS
Communication rounds: 500 for both datasets in the section of client sampling. For the other sections, 80 and 300 communication rounds for MNIST and CIFAR-10, respectively.
Dataset partition: Clients' local datasets are evenly partitioned into balanced subsets. However, the distributions are non-lID since they follow Dirichlet distribution with concentration a.
We consider a constant learning rate in all cases, and the choices are tuned through grid search. Specifically, ") {0.0001, 0.001, 0.01, 0.1). ). B E (0.001, 0.01, 0.1, 1]. Although our theory indi- cates the algorithm not sensitive to mini-batch size, we set a large batch size n = 256 for both datasets.
Universal
/ Stochassi Sign SGD
FedAvg Local Epochs
Learning Rate 7
Mini-batch Size n
Hidden Units
B
MNIST CIFAR-10
0.01
256
64
0.01
0.01
256
200
Table 4: Hyperparameters
E.3 BYZANTINE BASELINE COMPARISONS
In this section, we reuse the network model and parameter settings in Table set local epoch be I for non-signed aggregation rules. We evaluate the algorithms on MNIST dataset and partition in a same manner as Appendix H.T We consider total of 100 clients under full- paltpparticitatoon with 20 Byzantine clients. The wwwpeaaiioonrul-speeeeeeee parameters are illustrated in the following part. All the experiment results are collected with 5 repetitions.
We compare our 3 stochastic sign compressor with Krum Blanchard al. (2017). geometric median Chen et al. (2017), 7) centered clipping Karimireddy et al. (2021) under three adversary models, in- cluding label flipping, inner product manipulation lation Xie et al. (2020), the "A little is enough" Baruch ctt al. (2019). Following Karimireddy et al.] (2021), T is set to be 10 in centered clipping since momentum is switched off. We first illustrate the adversary models below:
27

---

Under review as a conference paper at ICLR 2023
Label flipping:
Suppose original label is the adversary will replace it with 9 2;
Inner Product Manipulation: The adversaries send Li EieN (f(w), instead of honest messages, to mislead the parameter server, where is the strength of the adversary. Let 0.1.
A Little is Enough: The adversaries estimate the benign clients' mean JA and standard deviation ov. Then, they will construct new messages as μw + zaN and upload to the parameter server, where is the strength of the adversary. We choose according to Baruch et al. (2019):
M --8 M
max
((=)
where 2 12 + +1| [B())), and + is the cumulative distribution function of standard normal distribution. For us, = 0.5.
In Section 7 we present the performance of our compressor under flipping sign attacks. For sign-bit messages, this is the worst-case scenario as adversaries' messages cannot escape binary value. Otherwise, it will be detected by PS and filtered out.
We consider milder condition than the sign flipping attacks for fair of competition. We allow adversaries to manipulate the mini-batch stochastic gradient but assume an honest compressor that will send out the correctly compressed corrupted messages to PS.
Label Flipping
Inner Product Manipulation
A Little is Enough
100
Accuracy (8)
STO
1-STO
KRUM
Geo-Median
Centered Clipping
200 400
600
800
1000 D
200 400
600
800
1000
200
400
600
800
1000
Communication Rounds
Communication Rounds
Communication Rounds
Figure 4: Comparisons with baselines: Krum, Geometric Median, Centered Clipping under Label Flipping, Inner Product Manipulation, and the "A Little is Enough" Adversaries,
where 1-STO refers to our 3 stochastic sign compressor with 8 B = 0.01.
Throughout the experiments, it observed that our 3 stochastic sign compressor outperforms all other baseline algorithms when 3 = 0 or 3 = B. Notably, our compressor saves up to 31x commu- nications and differentially private when 3 >
28


Reviews:
[{"review_id": "oXhFH8-2mPK", "reviewer": "Reviewer_9qJV", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "This paper provides the first algorithm based on sign SGD, which achieves Byzantine resilience and differential privacy.", "summary_of_the_review": "I think this is a good paper and should get accepted. But, the writing should improve.\n", "strength_and_weaknesses": "1)Author motivates the subject from a theoretical and practical point of view. \n2)In the introduction, the author reviewed the previous works carefully. \n3)the author successfully addressed the issue and recommended the algorithms.\n4)The authors successfully provide simulation results for their algorithm.\n5)The proof is mathematically correct.\n\n", "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": {}}, {"review_id": "DqJ9-fdOpT-", "reviewer": "Reviewer_nUrq", "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": "In this paper, the authors propose a new communication compression method called $\\beta$-stochastic sign SGD, which is Byzantine-resilient and differentially private. The authors provide theoretical results about differential privacy and convergence. Besides, the proposed method is empirically compared with SignSGD and FedAvg.", "summary_of_the_review": "Although the proposed method is easy to implement, given the concerns about novelty, quality, and readability, this work is currently below the bar of ICLR.", "strength_and_weaknesses": "**Strength**: The main idea of randomly flipping the sign is easy to understand and makes sense. The proposed method is not hard to implement.\n\n---\n**Weaknesses**: \n1. The novelty of this work is limited since the proposed method seems to be a combination of stochastic sign SGD and random flipping.\n2. The $L_1$ norm of gradients can be directly bounded by $\\sum_{i\\in[d]}B_i$ according to Assumption 3. It seems that the constant terms in the right-hand side of (5) and (6) are very likely to be not smaller than the trivial upper bound $\\sum_{i\\in[d]}B_i$. Could the authors compare the results in Theorem 5 with this? \n3. The empirical results are not solid enough. The proposed method is only compared with SignSGD and FedAvg. Comparing $\\beta$-stochastic sign SGD with more Byzantine-resilient methods is required.\n4. This paper is not well-written.\n  - $\\beta$ is frequently used before being formally defined in the abstract and the introduction. Besides, $d$ appears in the statement of contributions (page 2) without any definition.\n  - It is ambiguous what the notation $\\nabla F_i(\\cdot)$ means. Does it mean the partial derivative w.r.t. the $i$-th variable (i.e., the $i$-coordinate in the gradient)? If so, it is highly suggested to use $\\nabla_i F(\\cdot)$ or $(\\nabla F(\\cdot))_i$ since the original notation is very likely to be confused with $\\nabla f_m(\\cdot)$, which denotes the gradient of function $f_m(\\cdot)$.\n  - It is highly suggested to explicitly clarify which norm the notation $||\\cdot||$ in Assumption 2 denotes.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": "DpyVIOfAgBn", "reviewer": "Reviewer_W1pz", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This paper analyzes an optimization algorithm $\\beta$-stochastic sign SGD. The authors proves that $\\beta$-stochastic sign SGD is differentially private in the case of $\\beta > 0$. The authors also show that $\\beta$-stochastic sign SGD achieves Byzantine resilience under some problem assumptions.", "summary_of_the_review": "This paper has a very interesting finding that $\\beta$-stochastic sign SGD achieves Byzantine resilience and differential privacy simultaneously. It will help the reviewer to understand the contributions of this paper better if there were more performance comparisons of $\\beta$-stochastic sign SGD with existing methods designed for DP or Byzantine resilience only, whether they are comparable theoretically or in experiments in each dimension, and maybe some more explanations on the significance of the presented results. ", "strength_and_weaknesses": "Strength: \n1. The paper shows that $\\beta$-stochastic sign SGD achieves communication efficiency, differential privacy, and Byzantine resilience simultaneously.\n2. The proposed algorithm is very practical, easy to implement, and have good performance in MNIST and CIFAR-10 datasets in experiments. \n\nWeakness:\n1. The technical contribution in proving differential privacy of $\\beta$-stochastic sign SGD is not that significant. \n2. The assumptions for bounded gradients and sub-Gaussian element-wise gradient noise are kind of strong for federated learning or requires more justification, and these two assumptions again make the technical contributions less significant. \n3. More discussions with existing works such as [1] are needed for comparing the final error bounds for Byzantine resilience.\n4. Basically, the reviewer gets the idea that $\\beta$-stochastic sign SGD achieves two-fold benefits, but wants to see some comparisons with existing works in each dimension, so that the paper is more persuasive in that $\\beta$-stochastic sign SGD achieves performances matching the state of the art of at least comparable, and the technical challenges therein is non-trivial given that the algorithm itself is not that novel. \n5. In the experiments, it seems that the authors tune the algorithm to find good parameters $B$, which makes the algorithm less practical since it means that this algorithm needs to be run several times to achieve good performance (this will contradict to the target benefits of the algorithm), so a good estimate of a favorable $B$ would be helpful. \n6. Can the authors add some experiments to compare the performance of $\\beta$-stochastic sign SGD with other existing algorithms either designed for DP or Byzantine resilience?\n\n\n[1] Karimireddy, S. P., He, L., & Jaggi, M. (2021, September). Byzantine-Robust Learning on Heterogeneous Datasets via Bucketing. In International Conference on Learning Representations.", "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": "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": "2C8rQ-w0ax", "reviewer": "Reviewer_YSJ7", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 gradient compression in federated/distributed learning with two additional requirements: robustness against Byzantine clients and differential privacy (DP). The paper proposes a sign-based gradient compression method, called $\\beta$-stochastic signSGD, which applies clipping and a stochastic sign operator to gradients (Definition 3) for compression. SignSGD, which simply applies a sign operator to gradients was proposed in [Bernstein et al., 2019], and its stochastic version was proposed in [Jin et al., 2020]. The method proposed in the paper reduces to that in [Jin et al., 2020] for $\\beta = 0$. The paper presents convergence result and DP guarantees, along with experimental results. ", "summary_of_the_review": "The proposed method of $\\beta$-stochastic signSGD and the analysis are interesting. However, there are several questions that need to be addressed before the paper becomes ready for publication. \n", "strength_and_weaknesses": "**Strengths:** \n\n1. The family of sign-based compressors is practically appealing, and the paper proposes an interesting variant of stochastic signSGD. \n\n**Weaknesses:**\n\n1. The paper does not cover all details and the technical presentation leaves open several questions. For instance, the paper does not discuss any upper bound on the number of Byzantine clients $\\tau(t)$ in an FL iteration. It is well-known in Byzantine robustness literature that, when the fraction of Byzantine clients is greater than 1/2, then it is not feasible to achieve robustness. Remark 1 discusses the case of sufficiently large $\\tau(t)$, which is quite confusing. (Other comments and suggestions are mentioned later). \n\n2. The paper does not give details on whether DP guarantees are for client-level or item-level privacy. There are also no empirical comparisons with DP-SGD and/or local-DP algorithms with the proposed method. \n\n3. The $\\epsilon$ of DP for the proposed method is $O(d)$, where $d$ is the number of parameters of ML model (i.e., the length of gradients). This is going to be significantly large for several ML models such as deep neural networks. Would such a high epsilon be practical in terms of DP?\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": {}}]

Author rebuttal:

Decision: Reject