FedREP: A Byzantine-Robust, Communication-Efficient and Privacy-Preserving Framework for Federated Learning
Authors: Yi-Rui Yang
Kun Wang
Wu-Jun Li
Venue: Submitted to ICLR 2023 (2023)
Keywords: federated learning
Byzantine robustness
communication efficiency
privacy preservation

Abstract: Federated learning (FL) has recently become a hot research topic, in which Byzantine robustness, communication efficiency and privacy preservation are three important aspects. However, the tension among these three aspects makes it hard to simultaneously take all of them into account. In view of this challenge, we theoretically analyze the conditions that a communication compression method should satisfy to be compatible with existing Byzantine-robust methods and privacy-preserving methods. Motivated by the analysis results, we propose a novel communication compression method called consensus sparsification (ConSpar). To the best of our knowledge, ConSpar is the first communication compression method that is designed to be compatible with both Byzantine-robust methods and privacy-preserving methods. Based on ConSpar, we further propose a novel FL framework called FedREP, which is Byzantine-robust, communication-efficient and privacy-preserving. We theoretically prove the Byzantine robustness and the convergence of FedREP. Empirical results show that FedREP can significantly outperform communication-efficient privacy-preserving baselines. Furthermore, compared with Byzantine-robust communication-efficient baselines, FedREP can achieve comparable accuracy with an extra advantage of privacy preservation.

Under review as a conference paper at ICLR 2023
FEDREP: A BYZANTINE-ROBUST, COMMUNICATION- EFFICIENT AND PRIVACY-PRESERVING FRAMEWORK FOR FEDERATED LEARNING
Anonymous authors Paper under double-blee blind review
ABSTRACT
Federated learning (FL) has recently become hot research topic, in which Byzan- tine robustness, communication efficiency and privacy preservation are three impor- tant aspects. However, the tension among these three aspects makes it hard to simul- taneously take all of them into account. In view of this challenge, we theoretically analyze the conditions that communication compression method should satisfy to be compatible with existing Byzantinerrobust methods and privacy-preserving methods. Motivated by the analysis results, we propose novel communication compression method called consensus sparsification (ConSpar). To the best of our knowledge, ConSpar is the first communication compression method that is designed to be compatible with both Byzantine- robust methods and privacy- preserving methods. Based on ConSpar, we further propose novel FL framework called FedREP, which is Byzantine-robuss preserving. We theoretically prove the Byzantine robustness and the convergence of FedREP. Empirical results show that FedREP can significantly outperform srivacy-preserve baselines. Furthermore, compared cummunication-efficee communicationn-effciinn baselines, FedREP can achieve with Byzantine- comparable accuracy with an extra advantage of privacy preservation.
communication-effieee
and privacy-
INTRODUCTION
Federated learning (FL), in which participants (also called clients) collaborate to train a learning
model while keeping data privately-owner has recently become hot research topic (Koneveny
et al. 2016: McMaaan & Ramage 2017). Compared to traditional data-center based distributed
learning (Haddadpour et al..|2019 Jaggi al. 2014 Lee et al. 2017: Lian et al.) 2017 Shamir et
2014 Sun et al. 2018 Yu et al. 2019a| Zhang & Kwok| 2014 Zhao et al. 2017 2018 8 Zhou et al.
2018 Zinkevich et al. 2010). service providers have less control over clients and the network is usually less stable with smaller bandwidth in FL applications. Furthermore, participants will also take methods are not used. Consequently, Byzantine robustness, communication efficiency and privacy preservation have become three important aspects of FL. methods (Kairouz et al. 2021) and have attracted much attention in recent years.
the risk of privacy lcakage in FL if privacy-preserve
Byzantine robustness. In FL applications, failure in clients network transmission may not get discovered and resolved in time (Kairouz et al.) (021). Moreover, some clients may get attacked by an adversarial party, sending incorrect even harmful information purposely. The clients in failure or under attack are also called Byzantine clients. To obtain robustness against Byzantine clients, there are mainly three different ways, which are known as redundant computation, server validation and robust aggregation, respectively. Redundant computation methods (Chen et al.) 2018 Konstantinidis Ramamoorthy) [002 Rajput al., 2019) require different clients to compute gradients for the same training instances. These methods are mostly for traditional data-center based distributed learning, but unavailable in FL due to the privacy principle. In server validation methods (Xie et al.) 2019b 2020b), server validates clients' updates based on public dataset. However, the performance of server validation methods depends on the quantity and quality training instances. In many scenarios, it is hard to obtain large-scale high-quality public dataset. The third way is to replace the mean aggregation on server with robust aggregation (Alistarh et al.) [2018) Bernstein et al. 2019
Blanchard et al. 2017 Chen et al. 2017
Ghosh al. 2020 Karimireddy et al. 2021
al.

---

Under review as a conference paper at ICLR 2023
Table 1: Comparison among different methods in terms of the three aspects of federated learning Byzt.-robut
Method
RCGD (Ghosh et al. 2021
Led-Learning (Wang et al. 2020
SHARE (Velichet et al., 2021
SparseSecAge (Ergun et al.
2021
FedREP (Ours)
2019 Sohn et al. 2020 Yin et al., 2018 2019).
Compared to redundant computation and server validation, robust aggregation usually has wider scope of application. Many Byzantine-robust FL methods (Wang et al. 2020 Xie et al. 2019a) take this way.
Communication efficiency. In many FL applications, server and clients are connected by wide area network (WAN), which is usually less stable and has smaller bandwidth than the network in traditional data-center based distributed machine learning. Therefore, communication cost should also be taken into consideration. Local updating technique (Konevený et al. 2016 McMahan et al. 2017: Yu al., 2019b; Zhao et al.) 2017 2018). where clients locally update models for several iterations before global aggregation, is widely used in FL methods. Communication cost can also be reduced by communication compression techniques, which mainly include quantization (Alistarh)
et al. 2017; Faghri et al., 2020, Gandikota et al.) 2021 Safaryan & Richtárik, 202 Seide et al.
2014 Wen et 2017), sparsification (Aji Heafield 2017] Chen et al. 2020 Stich et al., 201
Wangni et al. (0188) and sketching") (Rothchild al. 2020). Error compensation (also known error feedback) technique (Gorbunov et al. 2020 Wu et al. 2018 Xie et al. 2020c) is proposed to alleviate the accuracy decrease for communication compression methods. Moreover, different techniques can
be combined to further reduce communication cost (Basu et al. 2020 Lin et al. 2018).
Privacy preservation. Most of the existing FL methods send gradients model parameters during training process while keeping data decentralized due to the privacy principle. However, sending gradients model parameters may also cause privacy leakage problems (Kairouz al. 2021 Zhu
et al. 2019). Random noise is used to hide the true input values in some privacy-preserving techniques
such as differential privacy (DP) (Abadi et al. 2016 Jayaraman al. 2018 McMahan al. 2018
and sketching (Liu et al. 2019 Zhang& & Wang 2021). Secure aggregation (SecAgg) (Bonawitz et al.
2017. Choi al. (000)) is proposed to ensure the privacy of computation. Based on secure multiparty computation (MPC) and Shamir's f-out-of-n secret sharing (Shamir) 1979), SecAgg allows server to obtain only the average value for global model updating without knowing each client's local model parameters (or gradients). Since noises can be simply added to stochastic gradients in most of the exsiting FL methods to provide input privacy, we mainly focus on how to combine SecAgg with Byzantine-robust and communication-effiicee
methods in this work.
There are also some methods that consider two of the three aspects (Byzantine robustness, communica- tion efficiency and privacy preservation), including RCGD (Ghosh et al. 2021). Feed-Lerning (Wang) et al. 2020). SHARE (Velicheti et al. (021)) and SparseSecAgg (Ergun et al. 2021 which we sum- marize in Table I However, the tension among these three aspects makes hard to simultaneously take all of the three aspects into account. In view of this challenge, we theoretically analyze the
tension among Byzantine robustness, communication efficiency and privacy preservation, and propose a novel FL framework called FedREP. The main contributions are listed as follows:
We theoretically analyze the conditions that a communication compression method should satisfy to be compatible with Byzantine-robust methods and privacy-preservinn methods. Motivated by the analysis results, we propose a novel communication compression method called consensus sparsificattio (ConSpar). To the best of our knowledge, ConSpar is the first communication compression method that is designed to be compatible with both cecaanine-robuus methods and
methods.
Based on ConSpar, we further propose novel FL framework called FedREP, which is Byzantine-robust, caamunication-effiicc. and sriaacy-preservng.
Sketching technique can be used in different ways for reducing communication cost protecting privacy. Thus, sketching appears in both communication-effciee methods and crivacy-preservin methods.
2

---

Under review as a conference paper at ICLR 2023
We theoretically prove the Byzantine robustness and the convergence of FedREP.
We empirically show that FedREP can significantly outperform existing communication- efficient privacy-preservin baselines. Furthermore, compared with Byzantine- cnttuumiicaato-fffcciinn baselines, FedREP can achieve comparable accuracy with an extra advantage privacy preservation.
PRELIMINARY
In this work, we mainly focus on the conventional federated learning setup with m clients and single server (Kairouz et al.) 2021). which collaboratively to solve the finite-sum optimization problem:
m Σ (w))
min F(w)= weRd
s.t. Fl(W)
E fi(w), & 1,2, 1.2,...,m,. m, (1) SDDz
DR
where w is the model parameter and d is the dimension of parameter. f((w) is the empirical loss of parameter w on the i-th training instance. Dj: denotes the index set of instances stored on the k-th client and F& (w) is the local loss function of the k-th client. We assume that Dj. n D = 0 when k * K, and consider the instances on different clients with the same value as several distinct instances. Pa is the weight of the k-th client satisfying that P&: >> O and Σx= Pk- = 1. A common setting of is that
t [Dxl) ). For simplicity, we assume [Dx [Dw/ for all k, k E [m]] and thus |DaI/E k=1,
Pk 1/m. The analysis in this work can be extended general cases in similar way.
Most federated learning methods (Karimireddy et al. 2020; McMahan et al. 2017,2018 to solve problem ( are based distributed stochastic gradient descent and variants, where clients locally update model parameters according to its own training instances and then communicate with server for model aggregation each iteration. However, the size of many widely-used models (Devlin et al.) 2018 He et al. 2016) is very large, leading to heavy communication cost. Thus, techniques to reduce communication cost are required in FL. Moreover, FL methods should also be robust to potential Byzantine attack and privacy attack in real-world applications.
Byzantine attack. Let [m] = 2,.,.... m) denote the set of clients. G S [m]] denotes the set of good (non-Byzantine) clients, which will execute the algorithm faithfully. The rest clients [m] \ G are Byzantine, which may act maliciously and send arbitrary values. The server, which is usually under service provider's control, will faithfully execute the algorithm well. This Byzantine attack model consistent to that in many previous works (Karimireddy et al.] (021). Although there are some works (Burkhalter al. 2021) focusing on another types of attacks called backdoor attacks (Kairouz) et al. 2021), in this paper we mainly focus on Byzantine attacks. The purpose of Byzantine attacks to degrade the model performance. One typical technique defend against Byzantine attacks is robust aggregation (Kairouz et al. 2021). which guarantees bounded aggregation error even if Byzantine clients send incorrect values.
Privacy attack. In a typical FL method, server is responsible for using the average of clients' local updating values for global model updating. However, local updating information may be used to recover client's training instances (Zhu et al.) 2019)) which will increase the risk of privacy leakage. Thus, server is prohibited directly receive individual client's updating information by the requirement of privacy preservation (Kairouz et al. 2021). Secure aggregation (Bonawitz et al., 2017) is a typical value for global model updating.
method, which only allows server to have access to the average
There are mainly two different types FL settings, which are also called cross-silo FL and cross- device FL (Kairouz et al. 2021). We mainly focus the cross-silo FL setting in this paper, where the number clients m is usually not too large and all clients can participate in each training iteration. Meanwhile, in this paper mainly focus on synchronous FL methods.
METHODOLOGY
In this section, analyze the conditions that communication compression method should satisfy to be compatible with Byzantine-robus methods and propose novel communication compression method called consensus sparsification and novel
methods. Based on the analysis,
3

---

Under review as a conference paper at ICLR 2023
federated learning framework called FedREP that is Byzantine- communication- In FedREP, we adopt robust aggregation technique to obtain Byzantine robustness due to its wider scope of application than redundant computation and server validation. For privacy preservation, we mainly focus on secure aggregation, which is a widely used technique in FL to make server only have access the average of clients' local updating values.
and
3.1 MOTIVATION
We first analyze the compatibility of existing communication compression methods with secure aggregation (SecAgg) (Bonawitz al. 2017). SecAgg is usually adopted together with quantization since it requires to operate on fimite field to guarantee the privacy preservation. Traditional quantization methods that represent each coordinate in lower bits can compress gradients floating point number (32 bits) only up to 1/32 of the original size. Even with quantization, SecAgg still suffers from heavy communication cost. Thus, sparsification is required to further reduce the communication cost (Ergun et al., 2021). However if we simply combine traditional sparsification methods (e.g.. random-K K and top- K sparsification) with SecAgg, the random mask in SecAgg will damage the sparsity. Thus, non- BanaByyantine clients should agree the non-zero coordinates in order to keep the sparsity in SecAgg.
Then we analyze the compatibility of sparsification with robust aggregation. As previous works (Karimireddy et al. (222)) have shown, to obtain Byzantine robustness, it requires the distances between compressed updates from different clients (a.k.a. dissimilarity between clients) be small. Specifically, we present the definition of (6, c)-rbusst aggregator in Definition]
Definition ((ō, c)-robust aggregator (Karimireddy et al., 2021 2022 ). Assume constant 5 E [0, 2) and index set 9 C [m] satisfies |g] 2 [I 0)m. Suppose that we are given m random vectors Viy..., Vm E Rd such that Bllvv= V S p² for any fixed k,K' E G. Vi can be arbitrary value if k- E ml G. Aggregator Agg(.) is said to be (8, -r-busst if the aggregation error Agg [Vk k=
( ENEg Vs, satisfies that
E||e| S cōp².
(2)
As shown in previous works (Karimireddy et al. 2022). many widely-used aggregators, such as Krum (Blanchard et al., 2017), geoMed (Chen et al. 2017) and coordinate-wise median (Yin)
ct al. 2018), combined with averaging in buffers (please refer to Section 3.3), satisfy Definition] I Moreover, ((pp²) is the tightest order (Karimireddy et al. 2021). Thus, a compression method which compatible with robust aggregation should satisfy the condition that the expectation of dissimilarity between clients' updates is kept small after compression. Therefore, we theoretically analyze the expectation of dissimilarity after sparsification. For space saving, we only present the results here. Proof details can be found in Appendix B
Theorem 1. Let {ve]K= denote random vectors that satisfy El[vk v = (pH,))2 and = ||
(uu)) for any fixed k. k E G. More specifically, [[((v)); - )2 = Ev.'d (PK,N) and [[(v))3]= (k.(H where Ex,K' > O, pk.j > 0, Σjeld EK,K', = and ΣjE[a Sk.j = for any fixed k, K E G. Let C(-) denote any sparsification operator and N₂ denote the set of non-zero coordinates C(V+). For any fixed k, k E G. we have:
E
(p
Σ (ERN No (.wl)) SEld]
+ (1RR22
(SasPrli e E Naol) + (mRI)2 SE[4
Σ
Σ jEld]
(Gr.PPll E NNr \NN))
(3)
Please note that when dissimilarity between the k-th and the k'tth clients is not too large, (1²))² and (uz))² are usually much larger than "2 In Equation (3). terms (Hx)² and (ugr)² vanish if and only if Ni, W = NN A = 0 with probability 1, which is equivalent to that M₁. = -Ny with probability 1. Furthermore, in order to lower the dissimilarity bewteen any pair of non- non-Byzen noz-Biinntinn clients, all non-B non-Byzantine clients should agree on the non-zero coordinates of sparsified vectors. Motivated by the analysis results in these aspects, we propose the consensus sparsification.
4

---

Under review as a conference paper at ICLR 2023
3.2 CONSENSUS SPARSIFICATION
We introduce the consensus sparsification (ConSpar) method in this section. For simplicity, we assume the hyper-parameter K is multiple of client number m. We use uf to denote the local memory for error compensation (Stich et al. 2018) on client_k at the (-th iteration. Initially, u = O.
Let gi denote the updates vector to be sent from client_k at the t-th iteration. Client_k first generates K sparsification criterion. More specifically, Th contains the coordinates a coordinate set T by top- m
according to the largest absolute values in gi. Then, set T% is generated by randomly selecting K rx,) elements from Th. where random variable rf. follows the binomial distribution B Kk a) m
(0 S a S 1). Thus, IT K rí. Then, set R2 is generated by randomly selecting r elements from TT. Finally, client_k computes T = Th U and sends Tg to server. The main purpose of the operations above is to obfuscate the top- m provide stronger privacy preservation on the coordinates, but may degrade the model accuracy, we will empirically show in Section 5 The sent coordinates are totally random when a =.
m
K dimension for privacy preservation. Larger could
When server has received (Ix mm from all clients, it decides the coordinate set of sparsified gradients I' = - and broadcasts I' to all clients. Finally, each client receives I', and computes the sparsified E according to it More specifically, (gi), = (gi,; if j E I' and (gi)) = 0 otherwise, where (g denotes the value in the j-th coordinate of g Since [ k we have = I k= I S >i= | K. Please note that clients only need to send (g. Jz to the server since clients and the server have reached an agreement on the non-zero coordinates I' of sparsified gradients. More specifically, (g))z = ((K))j...., (zk) where j. E I' (s 1, 1,..., (T') are
in ascending order. When server has received ((g)) Ize mm k==1 uses robust aggregation to obtain (G')z = ( }==,). Please note that (G')z )z2 is still a sparsified vector. Moreover, server is only required to broadcast (G')z+ since I' has already been sent to clients before. Thus, ConSpar is naturally& a two-way sparsification method without the need adopt DoubleSqueeze technique (Tang
et al., 2019). Then we analyze the dissimilarity between clients after consensus sparsification. Please note that we do not assume the behaviour of Byzantine clients, which may send arbitrary I-
Proposition 1. Let {g J denote the consensus sparsification results of vectors {gl, J and then we have E g 1 E 1 for any fixed k. ke E g.
Proposition indicates that ConSpar will not enlarge the dissimilarity between clients, which is consistent with Theorem I Meanwhile, SecAgg can be used in the second communication round and random masks are needed to add on the consensus non-zero coordinates only. Then we analyze the privacy preservation of the mechanism that we use to generate I in ConSpar. To begin with, we
present the definition of e-differential privacy (c-DP) in Definition 2
Definition 2. Let > 0 be real number. A random mechanism M is said to provide e-diffrrnntial privacy if for any two adjacent input datasets Ti and Tz and for any subset of possible outputs S:
Pr Pr(M(Ti) E S) S exp(e) Pr((M(T2 E).
In the mechanism that we use to generate I in ConSpar, Ti and To are the top- m Definition 2 leaves the definition of adjacent datasets open. In this work, coordinate sets Ti and Ta that satisfy T1 To C [d] and IT |2l K are defined to be adjacent if Ti and Ty differ only on one element. Liu et al. (2020) provides DP guarantee for sparsification methods with only one selected coordinate. Our definition is more general and includes the one coordinate special case where 'Ti = [T2l 1. Now we show that the coordinate generation mechanism provides c-DP.
K coordinate sets.
Theorem 2. For any (0, 1), the mechanism in consensus sparsification that takes the set of top coordinates Th as an input and outputs Ił provides (In (1+a) K (d +1) )) -disferential privacy.
2a
Finally, we analyze the communication complexity of ConSpar. Clients need to send candidate coordinate set Zi. receive I', send local gradient in the form of (gi)zz, , and then receive (G') Iz in each iteration. Thus, each client needs to communicate no more than K + K) integers and 2K floating point numbers in each iteration. When each integer floating point number is represented We use tilde denote sparse vectors in this paper for easy distinguishment.
5

---

Under review as a conference paper at ICLR 2023
by 32 bits (4 bytes), the total communication load of each client is no more than (96 32 K bits in each iteration. The communication load is not larger than that of vanilla top-K K sparsification, in which 4 32K 128K bits are transmitted in each iteration. Meanwhile, although ConSpar requires two communication rounds, the extra communication round is acceptable. For one reason, there is little computation between the two rounds, which will not significantly increase the risk of client disconnection during the aggregation process. For another reason, the cost of the extra communication round is negligible when combined with SecAgg since SecAgg already requires multiple communication rounds and can deal with offline clients.
m
3.3 FEDREP
As we have shown, ConSpar compatible with each of robust aggregation and SecAgg. However, robust aggregation and SecAgg can not be simply applied together since SecAgg is originally designed for linear aggregation (such as summation and averaging) while robust aggregation is usually non- linear. This is also known as the tension between robustness and privacy (Kairouz et al.) 2021).
Buffers on server are widely studied in gezzantine-rouse machine learning (Karimireddy et al. 2022
Velicheti et al.) 2021; Wang et al. 20200] Yang & Li [2021), which can be used to make such a trf between robustness and privacy. We also introduce buffers in FedREP. The details of FedREP are illustrated in Algorithm [ and Algorithm 2 in Appendix [A]
Let integer s denote the buffer size. For simplicity, we assume client number m is a multiple of buffer size and hence there m buffers on server. At the beginning of the t-th global iteration, each a
client & locally trains model using optimization algorithm A and training instances Dd based on w and obtain model parameter w = A(ww;; Dx)) The update to be sent is gi: = un + (w' - w - where uf is the local memory for error compensation with _ = O. Then client k generates coordinate set I by consensus sparsification (please see Section 3.2). and sends Ij to the server.
When server receives all clients' suggested coordinate sets, it broadcasts I' = I which is the set of coordinates to be transmitted in the current iteration, to all clients. In addition, server will randomly assign a buffer for each client. More specifically, server randomly picks a permutation of [m]] and assign buffer b; clients {I(ls k)}i= 1 (1 = 0,1...., m 1). Then for each buffer, b, = Σi= (8(((t))))) ) is obtained by secure aggregation and global update (G*)z =
Agg( (bb (m))) is obtained by robust aggregation among buffers. During this time, clients could update the local memory for error compensation by computing u. = gk - Finally, (G') zz is broadcast to clients for global updating by w4+1_ = w G
We have noticed that the consensus sparsification is similar to the cyclic local top- sparsifica- tion (CLT-K) (Chen et al./ 2020), where all clients' non-zero coordinates are decided by one client in each communication round. However, there are significant differences between these two sparsifica- tion methods. CLT-K is designed to be compatible with all-reduce while consensus sparsification is designed to be compatible with robust aggregation and SecAgg in FL. In addition, when there Byzantine clients, CLT-K does not satisfy the d' ""cootraction property since Byzantine clients may purposely send wrong non-zero coordinates. Meanwhile, some works (Karimireddy et al.) (022) show that averaging in groups before robust aggregation (as adopted in FedREP) can help to enhance the robustness of learning methods on heterogeneous datasets. We will further explore this aspect in future work since it is beyond the scope of this paper.
Finally, we would like discuss more about privacy. In the ideal case, server would learning nothing more than the aggregated result. However, obtaining the ideal privacy-preserviy property itself would be challenging, and even more so when we attempt to simultaneously guarantee Byzantine robustness and communication efficiency (Kairouz et al. 2021). In FedREP, server has access to the partially aggregated mean by and the coordinate set Z. However, as far as we know, the risk of privacy leakage increased by the two kinds of information is limited. Server does not know the momentum sent from each single client, and only has access to the coordinate set Zí without knowing the corresponding values even the signs. Although it requires further work to study how much information can be obtained from the coordinates, to the best of our knowledge, there are almost no exsiting methods that can recover the training data only based the coordinates.
RRnndmm quantization can he simply adopted hefore secure aggregation to make the values finite field for more privacy preservation. However for simplicity, we do not include it in the description here.

---

Under review as a conference paper at ICLR 2023
4 CONVERGENCE
In this section, we theoretically prove the convergence of FedREP. Due to limited space. proof details in Appendix B Firstly, present the definition of d' conttrracttoon operator (Stich et al. 2018).
Definition (d'=contraction).
C TRd + RRd is called d' -contraction operator (0 < S d) if
E x C(x)1l S (1 - d' /d) |x]], VX E
(4)
The d' ccontraction property of consensus sparsification is shown in Proposition
2
Proposition 2. the fraction of Byzantine clients is not larger than d (0 S fication is dloons-conn -ootr-contaattion operator, where d'amss d(1 <K((1-))m-)
2) consensus sparsi-
K
881m-1]
m
Therefore, the existing convergence results of d'-contraction operator (Stich et al. 2018) can be directly applied consensus sparsification when there is no Byzantine attack. Then we theoretically analyze the convergence of FedREP. For simplicity in the analysis, we consider the secure aggre- gation and the robust aggregation on server as unit secure robust aggregator, which is denoted by SRAgg(-). Therefore, G SRAgg( ( (=)) The assumptions are listed below.
Assumption (Byzantine setting). The fraction of Byzantine clients is not larger than 8 [0<8<})) and the secure robust aggregator SR.Agg(.) is (6, c)robust with constant 2 0. Assumption (Lower bound). F(w) bounded below: 3F* E R. F(w) 2 PP,YW E TRdd.
Assumption 3 (L-smoothness). Global loss function F(w) is differentiable and L-smooth: |[V((w) VF(w")l S L|[w w'l,, Vw, w' E RR. Assumption (Bounded bias). vk G, we have E[V (w)) = V (ww)) and there exists B 0 such that F (w) - VF(w)]] S B, Vw E Rdd Assumption 5 (Bounded gradient). Vk E G, stochastic gradient V fig (w) has bounded expectation: 3D E Rt, such that [w)] S D, Vw E Rd
Assumption is common in Byzantine previous works (Karimireddy et al. 2022). The rest assumptions are common in distributed stochastic optimization. Assumption il widely used the analysis of gradient compression methods with emor compensation. We first analyze the convergence for a special case of FedREP where the training algorithm .A is local SGD with learning rate and interval 1. Specifically, w w+++ is computed by the
distributed machine learning, which is consistent with
following process: (i) w ++1.0 ww; (ii) w ++1,j+1 = w 1.j -n-- V f,a. (w( ww(111),, j = 0, 0,1,
(ii) w w 1+1,1 where d is uniformly sampled from Dr. Assumption i made for this case.
Assumption 6 (Bounded variance). Stochastic grudient V Vsgg (w) is unbiased with bounded variance:
f (w) Fe(w) and Bo Succ that fxg (w) V [w) < 0², Vw Rd. Vk E g.
According to Assumption and the second order moment of stochastic gradient V (w) is bounded by (D2 + oz). Let u
Ekeg ut and let et = SRAgg (((Agg((())m
क Σkeg gi
denote the aggregation error. We first show that E.
| 1l2 and 1E| are both bounded above.
Lemma 1. Under Assumption 7
and 6 let constant H d/d'cone and take learning rate n? Vk G.
? = 77 > 0, we have E||ui, 11
Lemma 2. Under the same conditions Lemma 1 we have El e' 112 S Scd +x
Based on Lemma D and Lemma 2 we have the following theorem.
Theorem 3. For FedREP, under the same conditions' in Lemma 7 and Lemma
we have:
T
2[F(w0) F*
B|VF(w)))
+ +m + 177222 A,
(5)
T
nIT
where
71 2IL (2(1 - + D2 + o (D² 0²) + 8c5 + +z)]
22 82 ( +
and
A 2BD + 4 +
7

---

Under review as a conference paper at ICLR 2023
When taking 7 (1//VT), Theorem guarantees that FedREP has convergence rate of O(1/VT) with an extra error 4, which consists of two terms. The first term 2BD comes from the bias of stochastic gradients, which reflects the degree of heterogeneity between clients. The term vanishes in i.i.d. cases where B 0. The second term 4 //2c aggregation error. The term vanishes when there is no Byzantine client (6 = 0). Namely, the extra error A vanishes in i.i.d. cases without Byzantine clients. Then we analyze the convergence of FedREP with general local training algorithms that satisfy Assumption 7 which illustrates two important properties of a training algorithm.
( o²iD comes from the
Assumption 7. Let w' = A(w; D. There exist constants nA > 0, A 2 0 and A2 > 0 such that local training algorithm satisfies | (w: D&]] FFF(W)] I A1 and E (a(:;; D I (A2)², where Gw( Da.) = (w- w')/TA, Ak E [m]]
In Assumption 7 Gw( Dis) can be deemed as an estimation of gradient (w) by algorithm A with bounded bias/ A and bounded second order moment (A2)². The expectation appears due to the randomness in algorithm A. Many widely used algorithms satisfy Assumption 7 For vanilla SGD, let 77,4 be the learning rate and (w: Dx) is exactly the stochastic gradient. Thus, we have A
and (A2)² = D2 + o² under Assumption and 6 Morcover, previous works (Allen-Zh) et al. 2020 El-Mhamdi et al., 2020; Karimireddy et al. 2021 have shown that using history information such as
momentum is necessary in Byzantine robust machine learning. We show that local momentum SGD
also satisfies Assumption 7 in Proposition in Appendix [B]
Theorem 4. Let constant H = a/d'ons. For FedREP, under Assumption 7
2
3
and
we have:
EE B| < 2[F(w")-
F NAT
MATAI + (nA))
7A,2 + AA
(6)
T
where
N4.1 I + AHA2DT, 16c (1 1)
7A. 8H (A2)
and A 22, + 2BD + 4 200 D).2D.
Compared to the error A in Theorem 3 there is an extra term 2A, D in A which is caused by the bias of gradient estimation in algorithm A. Meanwhile, would like to point out that Theorem 4 provides convergence guarantee for general algorithms. For some specific algorithm, tighter upper bounds may be obtained by adopting particular analysis technique. We will leave it for future work since we mainly focus on a general framework in this paper.
EXPERIMENT
In this section, we evaluate the performance of FedREP and baselines on image classification task. Each method is evaluated on CIFAR- dataset (Krizhevsky et al., 2009) with a widely used deep learning model ResNet-20 (He et al. 2016). Training instances are equally and uniformly distributed to each client. All experiments in this work are conducted by PyTorch on a distributed platform with dockers. More specifically, we set 32 dockers as clients, among which clients are Byzantine. One extra docker is set to be the server. Each docker is bound to an NVIDIA Tesla K80 GPU. Unless otherwise stated, we set local training algorithm AA to be local momentum SGD with momentum hyper-paramenn / = 0.9 (see Equation (82) in Appendix B for FedREP. We run each method in the same environment for 120 epochs. Initial learning rate is chosen from 10.1. 0.2, 0.5, 1.0, 2.0, 5.0}. At the 80-th epoch, learning rate will be multiplied by 0.1 as suggested in (He et al. 2016). The best top-1 accuracy w.r.t. epoch is used as final metrics. We test each method under bit bit-flipping attack, 'A Little is Enough' (ALIE) attack (Baruch et al. 2019) and 'Fall of Empires' (FoE) attack (Xie et al., 2020a).. The updates sent by Byzantine clients with bit bit-flipping attack are in the opposite direction. ALIE and FoE are two omniscient attacks, where attackers are assumed to know the updates on all clients and use them for attack. We set attack magnitude hyper- pprramear to be 0.5 for FoE attack. For FedREP, we test the performance when the robust aggregator is geometric median (geoMed) (Chen et al. (017), coordinate-wist trimmed-mean (TMean) (Yin et al.) 2018) and centered- clippping (CClip) (arimireddy et al., 2021). respectively. More specifically, we adopt Weiszfeld's algorithm (Pillutla al. 2019)) with iteration number set to be 5 for computing geoMed. The trimming fraction in TMean is set to 7/16. For CClip, we set clipping radius to be 0.5 and iteration number to be 5. Batch size is set to be 25.
8

---

Under review as a conference paper at ICLR 2023
80
20
Top: Accurer
Top- fetimey
WM
40
pue mm17
2.99 (13
20
60
100 120
20
40
60
92
100
120
40
60
80
100
120
Fpzch
Ppoch
Fpoca
Figure 1: Top-1 1 accuracy w.r.t. epochs of FedREP with CClip when there are 7 Byzantine clients under bit-flipping attack (left), ALIE attack (middle) and FoE attack (right),
Too Acouncy
Top Accustty
Top- Accunty
E0-
A..30-FF 13:5
SC-CRC 12
FcoREE at TMaan SnL 15
--FcREE At TTTMann FS3
Cc 15
w/ccos
20
60
100
120
Epoch
Figure 2: Top-1 I accuracy w.r.t epochs of FedREP and RCGD-EF when there are 7 Byzantine clients under bit-flipping attack (left), ALIE attack (middle) and FoE attack (right).
We first empirically evaluate the effect of on the performance of FedREP We set 1, and K = 0.05d. We compare the performance of FedREP when a = 0, 0.2, 0.5, 0.8, 0.95, 0.99 and 1. As illustrated Figure [], the performance of FedREP with CClip changes little when a ranges from 0 to 0.95. Final accuracy will decrease rapidly when a continues to increase. A possible reason is that some coordinates could grow very large in local error compensation memory when & near 1, More results of FedREP with geoMed and TMean are presented in Appendix [C1]] Since the effect of a is small when 0 < a < 0.95, we set a = 0 in the following experiments. In addition, as the empirical results in Appendix C.2 show, Byzantine attacks on coordinates have little effect on the performance FedREP. Thus, we assume no attacks on the coordinates in the following experiments.
Then compare FedREP with a Byzantine-robust Compressed Gradient Descent with Error Feedback (RCGD-EF) (Ghosh et al., 202I). For fairness, set the compression operator Q(-) in RCGD-EF to be top-K sparsification, and set I = 0.05, which is the ratio of transmitted dimension number to total dimension number, for both FedREP and RCGD-EF. Local updating interval 7 is set to 5 for each method. As illustrated in Figure 2 FedREP has comparable performance to RCGD-EF under bit-flipping and FoE attack, but outperforms RCGD- EF under ALIE attack. Meanwhile, FedREP is naturally two-way sparsification method while RCGD-EF is not. Moreover, FedREP provides extra privacy preservation compared to RCGD-EF,
cew.uuuiicaiioeffffiieeeee baseline called Robust
Due to limited space, more empirical results are presented in the appendices. Empirical results in Appendix C.3 show the effect of momentum hyper-parameter 3. Empirical results in Appendix C.44 show that FedREP can significantly outperform the coamunniatiooneffccien baseline SparseSecAgg (Ergun et al., (021). Empirical results in Appendix C.5 show that compared with the Byzantine- robust comparable convergence rate and accuracy with much smaller communication cost.
privacy-preserving
baseline SHARE (Velicheti et al. (202T). FedREP has
CONCLUSION
In this paper, we theoretically analyze the tension among Byzantine robustness, communication efficiency and privacy preservation in FL. Motivated by the analysis results, we propose novel Byzantine-robust, communication-efficeee and privacy-preserving FL framework called FedREP. Theoretical guarantees for the Byzantine robustness and the convergence of FedREP are provided. Empirical results show that FedREP significantly outperform communication-effin preserving baselines. Furthermore, compared with Byzantine- rozuuttin-robuust communication -effiiiinnnnnnnnntt base- lines, FedREP can achieve comparable accuracy with extra advantage of privacy preservation.
privacy-

---

Under review as a conference paper at ICLR 2023
Reproducibility Statement. In this work, we empirically test the performance of FedREP and the baselines on the public dataset CIFAR-10 KKrizhvsky et al. 2009) with the widely used deep learning model ResNet-20 (He et al. 2016). Common settings for all the experiments in this work
are presented at the beginning of Section 5 More settings for each single experiment are presented
provide the core part of our code in the suppiementary material. All the proof details for the theoretical results in this work
along with the empirical results in Section 5 and Appendix [ In addition,
can be found in Appendix B
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, Brendan McMahan, Ilya 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 308-318, 318, 2016.
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, pp. 440 445, 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Communication- efficient SGD via gradient quantization and encoding. In Advances in Neural Information Process- ing Systems, pp. 770-17720, 2017.
Dan Alistarh, Zeyuan Allen-Zhu, and Jerry Li. Byzantine stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 4613-4623, 2018.
Zeyuan Allen-Zhu, Faeze Ebrahimian, Jerry Li, and Dan Alistarh. Byzantine-resilient non-convex stochastic gradient descent. arXiv preprint arXiv:2012. 14368, 2020.
Gilad Baruch, Moran Baruch, and Yoav Goldberg. A little is enough: Circumventing defenses for distributed learning. In Advances in Neural Information Processing Systems, pp. 8635-8645 2019.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N Diggavi. Osparse-local-SGP Distributed SGD with quantization, sparsification, and local computations. IEEE Journal on Selected Areas in Information Theory, 1(1):217-226, 2020.
Jeremy Bernstein, Jiawei Zhao, Kamyar Azizzadenesheli, and Anima Anandkumar. signSGD with majority vote is communication efficient and fault tolerant. In Proceedings of the International Conference on Learning Representations, 2019.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzantine tolerant gradient descent. In Advances in Neural Information Processing Systems, pp. 119-129, 2017.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175 1191, 2017.
Lukas Burkhalter, Hidde Lycklama, Alexander Viand, Nicolas Kücchler, and Anwar Hithnawi. RoFL: Attestable robustness for secure federated learning. arXiv preprint arXiv:2107.03311, 2021.
Chia-Yo Yu Chen, Jiamin Ni, Songtao Lu, Xiaodong Cui, Pin-Yu Chen, Xiao Sun, Naigang Wang, Swagath Venkataramani, Vijayalakshmi Viji Srinivasan, Wei Zhang, et al. Scalecom: Scalable sparsified gradient compression for communication-eftiiiee distributed training. In Advances in Neural Information Processing Systems, pp. 13551-13563, 2020.
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos. Draco: Byzantine- resilient distributed training via redundant gradients. In Proceedings of the 35th International Conference Machine Learning, pp. 903-912, 2018.
Yudong Chen, Lili Su, and Jiaming Xu. Distributed statistical machine learning in adversarial settings: Byzantine gradient descent. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1 2017.
10

---

Under review as a conference paper at ICLR 2023
Beongjun Choi, Jy-yong Sohn, Dong-Jun Han, and Jackyun Moon. Conmuniccation-compuiiii efficient secure aggregation for federated learning. arXiv preprint arXiv:2012.05433, 2020.
Jacob Devlin, Ming-Wor Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep
bidirectional transformers for language understanding. arXiv preprint arXiv://100048805 2018.
El-Mahdi El-Mhamdi, Rachid Guerraoui, and Sébastien Rouault. Distributed momentum for Byrannine-resilien learning. arXiv preprint arXiv:2003.000/0, 2020.
Irem Ergun, Hasin Us Sami, and Basak Guler. Sparsified secure aggregation for federated learning. arXiv preprint arXiv:2112.12872 2021.
Fartash Faghri, Iman Tabrizian, Ilia Markov, Dan Alistarh, Daniel M Roy, and Ali Ramezani-Kebrya. Adaptive gradient quantization for data-paaralae sgd. In Advances in Neural Information Processing Systems, pp- 3174 1185- 2020.
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vqsgd: Vector quantized stochastic gradient descent. In International Conference Artificial Intelligence and Statistics, pp. 2197-2205, 2021.
Avishek Ghosh, Raj Kumar Maity, and Arya Mazumdar. Distributed Newton can communicate less and resist byzantine workers. In Advances in Neural Information Processing Systems, pp. 18028-18038, 2020.
Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramchandran. Communication-effiiia. and byzantine-robust distributed learning with error feedback. IEEE Journal on Selected Areas in Information Theory, 2(3):942-9535 2021.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Linearly converging erтor compensated sgd. In Advances in Neural Information Processing Systems, pp. 20889-20900. 2020.
Farzin Haddadpour, Mohammad Mahdi Kamani, Mehrdad Mahdavi, and Viveck Cadambe. Trading redundancy for communication: Speeding up distributed SGD for non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 2545-2554, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Martin Jaggi, Virginia Smith, Martin Takác, Jonathan Terhorst, Sanjay Krishnan, Thomas Hofmann, and Michael Jordan. Communication-efficcae distributed dual coordinate ascent. In Advances in Neural Information Processing Systems, pp. 3068-00677 2014.
Bargav Jayaraman, Lingxiao Wang, David Evans, and Quanquan Gu. Distributed learning without distress: Privacy-preeerving empirical risk minimization. In Advances in Neural Information Processing Systems, pp. 6346-6357, 2018.
Peter Kairouz, 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, (6(1-2):12110 2021.
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, 2020.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Learning from history for Byzantine robust optimization. In Proceedings of the International Conference on Machine Learning, pp. 5311-5319, 2021.
Sai Praneeth Karimireddy, Lie He, and Martin Jaggi. Syzantine-robus learning on heterogeneous datasets via bucketing. In Proceedings of the International Conference on Learning Representa- fions, 2022.
11

---

Under review as a conference paper at ICLR 2023
Jakub Konevený, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv:1610.05492, 2016.
Konstantinos Konstantinidis and Aditya Ramamoorthy, Byzshield: An efficient and robust system for distributed training. Proceedings of Machine Learning and Systems, 3:812-828, 2021.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. Technical report, 2009.
Jason D Lee, Qihang Lin, Tengyu Ma, and Tianbao Yang. Distributed stochastic variance reduced gradient methods by sampling extra data with replacement. The Journal of Machine Learning Research, 18()):40044446, 2017.
Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling, RSA: Byzantinerrobust stochastic aggregation methods for distributed learning from heterogencous datasets. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 1544 1551, 2019.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 5330-5340, 2017.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proceedings of the International Conference on Learning Representations, 2018.
Ruixuan Liu, Yang Cao, Masatoshi Yoshikawa, and Hong Chen. Fedsel: Federated sgd under local differential privacy with top-k dimension selection. In International Conference on Database Systems for Advanced Applications. pp. 485-501, 2020.
Zaoxing Liu, Tian Li, Virginia Smith, and Vyas Sekar. Enhancing the privacy of federated learning with sketching. arXiv preprint 1910v:/911.011122 2019.
Brendan McMahan and Daniel Ramage. Federated learning: Collaborative machine learning without centralized training data. Google Research Blog, 3, 2017.
Brendan McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficeent learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282, 2017.
H. Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. In Proceedings of the International Conference on Learning Representations, 2018
Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui. Robust aggregation for federated learning. arXiv preprint 191.v: 2019.
Shashank Rajput, Hongyi Wang. Zachary Charles, and Dimitris Papailiopoulos. Detox: A redundancy- based framework for faster and more robust gradient aggregation. In Advances in Neural Informa- fion Processing Systems, pp. 10320-10330, 2019.
Daniel Rothchild, Ashwinee Panda, Enayat Ullah, Nikita Ivkin, Ion Stoica, Vladimir Braverman, Joseph Gonzalez, and Raman Arora. Fetchsgd: Communication-effciennn federated learning with sketching. In Proceedings of the International Conference on Machine Leurning, pp. 8253-8265, 2020.
Mher Safaryan and Peter Richtárik. Stochastic sign descent methods: New algorithms and better theory. In Proceedings of the International Conference on Machine Learning, pp. 9224-922999 9234,, 2021.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data- aatallarallel distributed training of speech dnns. In Annual Conference of the International Speech Communication Association, 2014.
12

---

Under review as a conference paper at ICLR 2023
Adi Shamir. How to share secret. Communications of the ACM, 22(11):612 613, 1979.
Ohad Shamir, Nati Srebro, and Tong Zhang. Communication-effiienn distributed optimization using an approximate newton-type method. In Proceedings of the International Conference on Machine Learning, pp. 1000-1008, 2014.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jackyun Moon. Election coding for distributed learning: Protecting signsgd against Byzantine attacks. In Advances in Neural Information Processing Systems, pp. 06615-14625, 2020.
Sebastian U Stich, Jean- Baptistt Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018.
Shizhao Sun, Wei Chen, Jiang Bian, Xiaoguang Liu, and Tie- Yan Liu. Slim-dp: mulli--genn system for communication-effcienn distributed deep learning. In Proceedings of the 17th International Conference on Autonomous Agents and gunt Systems, pp. 721-729, 2018
Hanlin Tang, Chen Yu, Xiangru Lian, Tong Zhang, and Ji Liu. Doublesqueeze: Parallel stochas- tic gradient descent with double-pas error-compesn compensated compression. In Proceedings of the International Conference on Machine Learning, pp. 6155-6166 6165, 2019.
Raj Kiriti Velicheti, Derek Xia, and Oluwasanmi Koyejo. Secure Byzantine-robust distributed learning via clustering. arXiv preprini arXiv:21100002940) 2021.
Lun Wang, Qi Pang, Shuai Wang, and Dawn Song. Towards bidirectional protection in federated learning. arXiv preprint arXiv:2010.01175: 2020.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems, pp- 1299-1309, 2018.
Wei Wen, Cong Xu, Feng Yan. Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Tergradd Ternary gradients to reduce communication in distributed deep learning. Advances Neural Information Processing Systems, pp. 1509-1519, 2017.
Jiaxiang Wu, Weidong Huang, Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In Proceedings of the International Conference Machine Learning, pp. 5325-5333, 2018.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. SLSGD: Secure and efficient distributed on-device machine learning. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 213-228. 2019a
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with iuspicion-based fault-tolerance In Proceedings of the International Conference on Machine Learning, pp. 6893-6901, 2019b.
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking Byzantine-tolerant sgd by inner product manipulation. In Proceedings of the Conference on Uncertainty in Artificial Intelligence, pp. 261-270, 2020a.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous SGD. In Proceedings of the International Conference on Machine Learning, pp. 10495-10503, 2020b.
Cong Xie. Shuai Zheng, Oluwasanmi O Koyejo. Indranil Gupta, Mu Li, and Haibin Lin. CSER: commuuicaaiooncfficceeee sgd with error reset. In Advances in Neural Information Processing Systems, pp- 12593-1 12603, 2020c.
Gupta.
Yi-Rui Yang and Wu-Jun Li. BASGD: Buffered asynchronous SGD for Byzantine learning. In Proceedings of the International Conference Machine Learning, pp. 11751-11761, 2021.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robus distributed learning: Towards optimal statistical rates. In Proceedings of the International Conference on Machine Learning, pp. 5650-5659, 2018.
13

---

Under review as a conference paper at ICLR 2023
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Defending against saddle point attack in Byzantine-robuss distributed learning. In Proceedings of the International Conference on Machine Learning, pp. 7074-7084, 2019.
Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient momentum SGD for distributed non-convex optimization. In Proceedings of the International Conference on Machine Learning, pp. 7184-7193, 2019a.
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, pp. 5693-5700, 2019b.
Mengjiao Zhang and Shusen Wang. Matrix sketching for secure collaborative machine learning. In International Conference Machine Learning, pp- 1 12599, 2021.
Ruiliang Zhang and James Kwok. Asynchronous distributed admm for consensus optimization. In Proceedings of the International Conference on Machine Learning, pp. 1701-1709, 2014.
Shen-Yi Zhao, Ru Xiang, Ying-Hao Shi, Peng Gao, and Wu-Jun Li. SCOPE: scalable composite optimization for learning on spark. In Proceedings of the AAAI Conference on Artificial Intelligence, pp. 202-22222222 2934, 2017.
Shen- Yi Zhao, Gong-Dur Duo Zhang, Ming-Wei Wei Li, and Wu-Jun Li. Proximal SCOPE for distributed sparse learning. In Advances in Neural Information Processing Systems, pp. 6551-6560, 2018.
Yi Zhou, Yingbin Liang, Yaoliang Yu, Wei Dai, and Eric P Xing, Distributed proximal gradient algorithm for partially asynchronous computer clusters. The Journal of Machine Learning Research, 19(1):733-764, 2018.
Ligeng Zhu, Zhijian Liu, and Song Han. Deep leakage from gradients. In Advances in Neural Information Processing Systems, pp. 14747-14756, 2019.
Martin Zinkevich, Markus Weimer, Lihong Li, and Alex Smola. Parallelized stochastic gradient descent. In Advances in Neural Information Processing Systems, pp. 2595-2603, 2010.
14

---

Under review as a conference paper at ICLR 2023
A DETAILS OF FEDREP
The detailed algorithms of FedREP on server and clients are illustrated in Algorithm and Algo- rithm 2 respectively.
Algorithm 1 FedREP (Server)
Input: client number m, iteration number T, buffer size s, robust aggregator Agg(-);
for t to T do
Receive { mm Broadcast 7' k= from all clients and compute I -uk Ae
all clients;
Pick a random permutation of [m]; Assign buffer by to clients (T( + k)]a=1 for I = 0, 1,..., 1; for 1 0 to
do
Obtain b Σx=1 [ (z) via SecAgg protocol;
end for
Compute: (G') ) Agg (
Broadcast (G') 2r to all clients;
end for
Algorithm 2 FedREP (Client)
Input: client number m, iteration number T, local optimization algorithm A and sparsification size K; Initialization: model parameter w and local memory uß = 0;
for = 0 to T T - do
/ Locally train learning model and update error compensation #/ Locally train learning model and obtain parameter w [+1 Compute gi
A(w"; Ds);
u + (w' w!+1);;
/ Two-stage aggregation with sparsification */
Generate coordinate set Z by consensus sparsification (see Section 3.2 in the main text);
Send I the server;
Receive coordinate set I' and assigned buffer number from the server, Compute (g() z. and send it to the assigned buffer b, via SecAgg protocol;
Update memory: u gf g
Receive (G')z Iz from the server and recover &o according to It:
1s Update model parameters*/
Update parameters: w 1+1 w G
end for
Output model parameter w":;
15

---

Under review as a conference paper at ICLR 2023
B PROOF DETAILS
In this section, we present the proof details of the theoretical results the paper.
B.1 PROOF OF THEOREM
Proof. For any fixed k, k [m]]
[l(((vv)) C(vx))12
=E
Σ
[(vx); (vwr))]
+E Σ
(vR)}
+E E
(ve))
JENLTUN
JENEWWE
LiEVerivee
E
+E Σ
(kO(HE)²
+E JEN
(8)
JENLNNN
JENIWN
SN,M S EIJENNNNN
jE(d
+
Σ Snn(HN) Prli NG \N+++
Σ
( Prlj No \Nal
(9)
jE(d]
jEId]
=(pR,)))
Σ
(LR E No NN
sE(d]
+ (1x)2.
Σ
(A. e No Worl) + (mxr)2.) SEld]
Σ
(Sr E No \al).. (10)
jEId]
B.2 PROOF OF PROPOSITION 1
Proof. Let I denote the set of non-zero coordinates after consensus sparsification. In general cases, for any fixed k, k [m]] have:
E E
B
12
Σ
E((g))
(Bi:)
(11)
JEI
< B((g));
(g
(12)
sE[d]
Ellg gt 112
(13)
B.3 PROOF OF THEOREM 2
Proof. Let M be the the mechanism in consensus sparsification that takes the set of top coordinates T as an input and outputs a random coordinate set. Tı To S [d] are two arbitrary adjacent input coordinate sets that satisfy [T| IT&| = and is any subset of possible outputs of M. When is empty, Pr() E S Pr M S] = 0. Thus, for any > 0, we have:
Pr( S] exp(e) Pr(M(T2) E S) =0
(14)
Without loss of generality, we suppose that S is non-empty. For any I E S, let [Ti n I U₁ and TT 0 Z| Uz. Tj and Tz only differ on one element since they are adjacent. Thus, we have U2 U, 1, U, or U, 1. Set T, is generated by randomly selecting (K - rı) elements from Ti, where 71 follows the binomial distribution Pr( K a... Thus, Vi 0, 1,... K/m,
[//m) a' a a) K/m-i
Pr(ri = 1]= =
(15)
16

---

Under review as a conference paper at ICLR 2023
To obtain I as the final output, only the elements in TI n I can be selected. Thus, 11 should equal
or be larger than [ I = K U1. Furthermore, for 71 2 K U1, the probability that all K/m elements are selected from Ti ni is (x/m-n))/ (K/ ( (n U1 -0,) ( (K//m)) Finally, the
(k/
r1 elements in I T1 should be selected from [d] Tı, of which the probability is 1/("-R/mmm) k//+rr) since |[d]] \ Ti| d (K/m- m1) = d - K/m + r1. Thus, have:
(T] = 4
K/m
Pr(ri =]]x x (i-(k/m (i// U.
Σ
(16)
(k!m)
(d- (d-K/mittt)
K1m-U1
K/m
(K/m)
(K-(k/m- (k/mn)
Us
Σ
cx((1 - -a) am)mmmi x
x (d-kimatt)
(17)
i
i= U1
K/m
(1
U1 (K((mm - (-
bi))
Σ
a2(1-a)k/mm-
(a-kimtnn)
(18)
K/m U1
K/m-it(1 (1 -a)²
U1 -i)
U1 ))
(k/m--))
d-b
1
(19)
U1
(U1) x
= =a K/m
(20)
(d-k/mm)
i=0
Thus, PT(M = -] is monotonically increasing with respect to U1. Similarly,
Up
Pr[M((2) = 1 = a K/m
Σ
U2
(21)
K/m
which is monotonically increasing with respect to U2. Thus, (T = when U1 = U2 + 1. Therefore,
takes the maximum value
Mr
K/m U2+1
Li=
I-a a
(1++1) x
Pr[M = Pr[M = =
K/m
(22)
a k/mm
Σ// U/ 10=0
(1-a) (1) x (a-k/m)
Σ ===
Uz+1
1-a
1
(1)+1)
d K/m
(23)
U1 Σ
L-0
x (42)
kk/m)
Up+1
1-a
1
x (22+2)
(d-R/m)
Li=l
|=1
(24)
U2
x (U0)
+
1=
K/ml
K/mJ
1 1-a
U2+1
(1-a) 1-1
k/m)
(U2+1)
Pi=1
k)m)
(25)
1 I-a
>
0/2
(La
k/m)
x (U:)
a
Let
Sola) = Σ
U2
a
i-1
K-K/m
d
X
U2
(26)
d-i
i=1
α
dmK/m
and
(i(a) = Σ
Up+1
(1-a)
1 a
i-1
d k\mm
x
U1 + 11)
i 1)
(27)
d=i
a
- k/ml
17

---

Under review as a conference paper at ICLR 2023
We have
(T(M -
1+ 1- 1+ Si())
(28)
Pr(M =I
1+ 1- So(a)
1- (Si(a)-So(a))
=1+ 1+ 1-8 (s(a)
(29)
a
1-e (S) (a))
<1+
(30)
1-a Sa(a)
Si(a)
(31)
So(a)
Since Us = U2 + 1 S K/m, we have U2 S K/ m - 1. Thus,
U/2 1
1_
i-1
d- K/KKm// (U2+t)
(1())
(32)
i=1
k//mm
U1
8-1 1
(12+1) 1
U2+1
(1a))=²
(1a) f-1
d- 1KKKmll (U2t1)
d- K/ml
(33)
d-i
d-
kmmmm
1=2
dd K/mll
1-1
(12+1)
U2
L=a
(1z+1)
d- K/mm 1
a
J-KKm//
i+1
(34)
d-i
d-i-1
d-K/ml
x=1
d- K/mm
1-1
(1))
Up+1
U1
Lma)
L-a 1-1
d
U2) Up+1
d- K/ml
U2+1-1
k-K/m
s+1
(35)
d-i
d-i K/m-i
d-K/m
d-K/ml
d-i
U2
I-a i-1 |
U2
Up+1
U2
1-a
1-a )11
U2)
Uz+1
d- K/m
U2+1-03 12
4-K/m
I+I
(d d-K/m
d-1
1m1
ddKKmml
d-i
K K/m U2
d-Uz
(36)
1-a U2+1
Up
i-1
d d- d=i d-K/mo
U2
(U2 + 1)
(37)
K/ K/m U1
a
U-Uz
1-a
K/m-1+1
(K 11+1) + Kjm K/m-1
2
So(a)
(38)
d-K d-K/m+l
K
(1 aa
K +1)
+
So(()
(39)
m
2a
K (d-
K
K (1 a)
K + +1)
+ +1) +
So(aa)
(40)
77
m
2a
(1 + a):
(d
+1)
m
(a)
(41)
20x
Therefore,
Pr(M(Ti) =
(1
(1 +
K (d
K
+ 1)
m
(42)
(r[ = I
50(a)
2ax
Consequently,
(1 + a))
K (d
K
+ 11 1)
Mr(M II 2 exp In
m
PriLM(Ta== = =I],
(43)
20
(1+a)
K (d- K +1)
which shows that M provides In
-DP.
2cc
18

---

Under review as a conference paper at ICLR 2023
Then we provide stronger result for the case where is close to 1. Specifically, when 1 s a S 1,
Pr(M(Ti) = 1 I-a (Si(a)-S((a) 1 1-a PT(M II S 1+ La So(a))
(Si((a) So(a)). (44)
a
Since U1 = U2+11 +1+1 S K/m, we have U2 S K/m - 1. Thus,
Uz+1 (1-2)
(Va++1)
U2
1ma
d-K/m) (7))
Σ
d-K/m
=
(45)
d-K/m)
1=1
d-K/m
1-a
d
(1++1)
(12)
(اا) U2
k/m
d- kjmm
a
+
(46)
d=i
d-
d-K/m
d-K/m/
(1-a) 1-1
U2)
(1-a) U2
A-K/ml
1--1)
(-KK/m)
(47)
d=1
d U2-1
i=1
k/mm
d- k/mm)
d K/m
1/2
a
x-1
U2
(2aa
U/
+
(48)
d U2
K/m
α
i i-1
d U2-
k/mm
d K/ml
U22
U2
1-a
Up
d- K/ml
+
(49)
U2
i
d U2-11
K/m
1=0
d k/mm
U/2
L_a)
Us
d k\mm
a
d- k\mml
(50)
U2
a
d U2-1)
K/ml
d-K/m
(2)
U2
(1-a)
U/2
d- K/m
(k/mm))
(51)
(d-U2-1 (1))
d- 12-11
d- k/mm)
K-Kmm
U2
d k/m) 2
d k\mml
(52)
(d-U--1)
1)
dd-K km/m)
d k\/m)
= (2% +1).
(--K/m)
(53)
(-U
kmmmm
d
S k2 + +1).
(54)
K//m
s (2k/m/ + 1) k//m
(55)
Consequently,
In 1+ (1((1+
- a
(2k/m+1) 1) .)...... dlkm)) Pr(M(Ta) = Z].
Pr[M((T) = =I] S exp
(56)
a
It shows that when 1
S
1. M provides eM-DP, where eM
In (1+ 1- (2K/m + 1)- dk/m) Specially, when a 1, eM = In(1 + 0) 0. It is consistent to that the coordinate set is totally random when a = 1.
a
B.4 PROOF OF PROPOSITION 2
Proof. Vk E G. vA S tt< < T. we have:
[Lu
IU
T TーU [m[m]] kgEg
Ir
(57)
MEDI(()
19

---

Under review as a conference paper at ICLR 2023
Therefore,
B
1 = E
Σ
Ix
(58)
JEZ
= E
Σ
(g)))
I
+ E
Σ
(gk }
I
(59)
JETN
(TD
= Σ
(B + EF
Σ
(gf) I
(60)
JEIZ
JE (I
= Σ
{B +
Σ
(gk)
Pr [j E T
(61)
JEI
For any j & Iz.
Pr P
Pr
jE
U
I
(62)
MEDV(K)
Pr
jE
U
(FUUR)))
T
I
(63)
(ESV(K)
Pr
jE
U
U
U
RS
Ix
(64)
WEgM(k)
WEDVEK
Pr
j
E
U
T
It
+
Pr
jE
U
Ri.
(
F
(65)
WESVIA
For simplicity, let
v jE
U
Th
I
E 10,
(66)
(ED
and we have:
Pr Pr[jeI''Zz
1
= (1 v1- v)- Pr
jE
U R2.
&
U Th
(67)
WEOV(R)
MEDVER)
=U+ v)
1 Pr
j E
U RS.
Ieej &
U
T
(68)
WES)((K
(ESV(()
4h+ (1-
1
II Meg\(N)
Pr
j E Ri
Ihij& $
U TB
(69)
WEOWIN
K/m
Σ Pr(ri =il (1 (1- K/m +
4A (1 -))
II (EGV(M)
(70)
d
1=0
K/m
Σ Prtric =i] (1- 2) }}
1 44 (1-
II
(71)
(Eg
1=0
20

---

Under review as a conference paper at ICLR 2023
K/m
K/m
Pr (r
= =F+ (1 [1-
II (M)
Σ
Pr(r = =1]
Σ
(72)
d
141 (1 (1-
E El(fj]]
II
(73)
ak
4 (1 (1-1)
II
(74)
md
ak 161-11
= (1
(75)
md
aK
(1-6)m-17
1 (1 v)
1
(76)
md
(1))
1- (1
ak
(1-8)m-11
1 - (1-
ak
(1-8)m-1
+ (1 v)-
(77)
md
md
(1-6)m-1
aK
(78)
md
where (i) holds because when r = i, the probability that element j is among the i randomly selected elements from [d] \. Th is 2-K/m+F since [[d] \ Til d - K/m + i. Incquality (ii) holds because
i < K/m. Equation (iii) holds because rt. follows the binomial distribution B K m a). Incquality
(iv) holds because 1 - (1- B(rA)) (1 (1-8)m-1 1.
Since 0 < S and 0
K < d, we have 0 S
ak md
< 1. Thus,
akl0 61m-1
(1- a<K
(1-6)m-1
(
ak
md
x - mmm- md
<
(79)
md|
md
Therefore,
Pr [j E I I' 2 1 - c-
a11(-J)m-1 mn
(80)
Substituting it into (61. it is obtained that
E |
(g)) [1
Σ (gF)
(81)
jEZī
Jez
Σ
{gt)} + 1 21((--6m-1)
|ggk
(gg)
(82)
TEZ
JEZ
-k(1-60m- mid
||g 1|2 +
mi
Σ
(g
(83)
JEZz
Take total expectation and we have:
1 = E (1 (1-e"
LKk1 61m mm
||g 1|2 +
=8 5m ml
E
(g))
JEZ
(84)
Also,
E
Σ g 1
jezg
21

---

Under review as a conference paper at ICLR 2023
E
(gk
1
ri
+
Σ JER
ri
(85)
J
rk
E
Σ
(g r/
E
Σ
gg 3
(86)
d K m
r
JET
JieT
r
E
(gk) (1
1
I
Σ
(a5h ) ri
(87)
K/ K/m- rk
LET
DETT
r
K/m
|18/| 1 + d - K/m + +r
EE Σ
(g()
r
(88)
d
K/ m + r
LiETH
+
d - K/m
K/m - rk.
118% 11 + d K/m+ + +rk
E
Σ
(st))
r/
(89)
d
K/m + rk
K/m
LIET
rk d K/m + rk
d - K/m
K/m r/.
K/m.
|18 11 +
(90)
d K/m + rk
K/m
d
r
d - K/m
K/m r/
12
||
(91)
d K/m + r
d /mmm= + rk
d
dri + (d K (K/m)(K// //m -rr)
|g
(92)
O(d - K/m + r()
(K/m) . (d - K/m + r1))
(93)
d(d - K/m + ri)
K md g....
(94)
Thus.
E
Σ
E
E
Σ
(Bt))
> E
K md
gg 1
K
11.
(95)
md
JEZZ
JEZZ
Substituting 995
into
84
we have:
E
1
fmm---)m- mnd
K
K - 6mm-1 mil
|1sk
(96)
md
(d
K
( 60m-1] wed
11% 12.
(97)
d
Since g is the consensus sparsification result of g we have:
Blgg
gill = E
(st)
(98)
E
(g)) )3
Σ (g
(99)
jEGG
JEI
||g/
E g 1?2
(100)
(d
K )
2
(101)
d
d(1
K1 6mm11
K
KT(1 81m-1l
m
|12
(102)
d
22

---

Under review as a conference paper at ICLR 2023
By definition, consensus sparsification is d'cons contraction operator, where
Loons d (1 [1-e" AA -
11
K
+ e
m
B.5 PROOF OF LEMMA 1
Proof. When training algorithm A is T-iteration local SGD with learning rate y), we have w 1+00 w', W ++1++1
Wx 1. 7) Vf.g (w ( (j 0..,..., I 1) and w w/ where t
uniformly sampled from Dr. Therefore, we have the following inequality for all l: e
E| 12 = Elgg
1
(103)
doms d
1
E gi ||
(104)
deoms
[8] Iuj + (w" wh 211
(105)
1 d' d'coms
domna
2d
(1
+ (1 +
E w
++1.0
w
w
(106)
d
2d
d' d'cons
(ii)
1
d'con
E
+
2d
E||
w ++10 k
1+111 ||2 k
(107)
2d
d'
conss
1
d'cons
E
1
+
2ld
E W
H1, 1+1
(108)
2d
d'anns
d' d'oon
21d
1
E
1 1
+
Elime Vfgaa 11
(109)
2d
d'
d'ans j=0
(iv)
d'com
21d
E
+
(mp ? + +
(110)
2d
doons
where (i) is derived based on Proposition
2 (ii) is derived based on that ||x + y1 < (1
0)
2
(1+0-1) y+)y1) for any constant 0 > 0. (iii) is derived based on that (1 d' L'gnn
2d
2d
and (1
d' Legge)
2d
2d (iv) is derived based on Assumption and Assumption 6
When 1/-- VFF
where constant b > 0 and X
4d d
the second term on the RHS
212d
21d
b²
(n (122
DD² + 0z2)=
(111)
d'cons
d'
t+ A
822 (D2 + +o2)
1
Loons
(112)
(d'oons) )
t t+1 X
4d
d2
(d'ons)) }2 (D² +00)
1
d'ans
d' daans
(113)
t
2d
4d
d22
1
d'
deans
1
(d'onn)) )2 (D2 -
(114)
[+
2d
dz'
d' d'ans
(dl )2 (D2 + +00)
(115)
t+ X
2d
t ++
= 812
d'ana
(t + ++ -1
(dl )2 (D² +00)
2d
(116)
(t+ A) + x x
812
(dl 12 (D2 2D2++)))
1
(1
d'ans
2d
(117)
(d'ons))
[+
1+
23

---

Under review as a conference paper at ICLR 2023
Combining (110) and 117).
we have
E
12 -
d' deons 2d
( (D (
(1+2=1 (1
Loaps
2d
d''
(dcons))
t+}
(118)
Therefore,
(d'ons) ( < <(1- (1-
812 D2 +02) 02)
Leons
EBlu, 12 8 0²)
B 11
2d
(dcons (2 +
(119)
Recursively using (119), we have
812 + +02) (dcone ( + A)
<(1 ) (ElluQQ1 812 (D2 + t02)
d' deons
E 1ull
< 0.
2d
(dions) 1
(120)
Thus,
312
6²
= 812 +
E J 1 ك
(m1))
(121)
(deons) )
t ++
(d'oms)) )2
Finally,
E
E1
1
u
11
S
Σ
El
Ellui 12
8 + 02)
(mn))
(122)
9
|9|
d'coms) )2
REG
REG
When 7/ 11, by (100,, we have
E E
1
1
d'
cons
j 1| +
21dd
T222 +
(123)
2d
d'ans
d %ooms
412
E El 12
n (D² + 0z2)
1
1
E 1
y2 1D22 +
+00)
(d'cons) )
2d
(d' (d'cons)
(124)
Recursively using
124 we have
El
dd (d'cons)
(D2
+ +0?)
3111 deans
1-
[B|luR]1
(d'cons) RD2 +112
2
< 0.
2d
(125)
Thus,
41262 + .1p2
El <
E
(126)
(d'cons) )2
Finally,
4T2 +02) (d/oma))
E
||u'112= = Ell
Σ 11 <
Σ
El
.1²
(127)
|
|9|
REG
KEG
B.6 PROOF OF LEMMA 2
Proof. Based Assumption and Assumption
have that Vk E G.
E g 2
Elgg 2 [E + (w" w 1)1
(128)
<2E || 1 112 + 2F || wt
w w uf 112 21 (m (D2 + o²).
(129)
<2E
(130)
By Lemma i if
VIT where constant b > 0 and À = 4d
we have
Jann'
E E
s 2T + 1) +02) (n)), Wk EG
(131)
24

---

Under review as a conference paper at ICLR 2023
gir 11
s 2E 2E |
+ 2B
8f + +DD + (nx)
(132)
Therefore, by Definition
and 132
m B||e*11 1 =E SRAgg 18
[k=1
9
(133)
kEG
< cb BN [|g] g [|]]
(134)
< 8có (8112 + +1) + 0²) (11:)2
(135)
Similarly, rf 11 0, we have
+ 1)(D2 E B v 2112
. ,/², Veeg.
(136)
and
|| e|e' و scol + 1)((2 + +02) n/2
(137)
B.7 PROOF OF THEOREM 3
Proof. Let u' |9] Ekeg nr be the averaging memory of non- con-Byzantine clients. w is defined as
w w u'. The iteration rule for is derived as follows:
w++1 -w'+1 u ++1
(138)
- -(w'- (w' SRAggg( ((
uu + (w" - w B%
(139)
9
kEG
1
= -S-Agg (B
u +
(w' w(t1)
Sk
(140)
|9
REG
KEO
1
(w' -n²)
(w w
(SRAgg( (B()
gk
(141)
9
KES
kES
w w²
w
++1
e',
(142)
G
KES
where e¹ = -SRAgg (18
Ekeg of is the estimation error of 1
Σ Ekeg Bi.
T
Let G = (w' - To
Eker
Then we have
G¹
Σ
V ff (')),,,, t= 0,0,,.... --1,,
(143)
[|g
kEG 1=U
and
w w++ - W ni G -e' t= t= 0, --1.
(144)
The equation can be interpreted as that w is obtained by performing an SGD step on w' with learning rate 1/,, gradient approximation G and error e'. Based on Assumption 3 and the inequality that ||x + yll < 2|| 2
F(w++)) +1 =F(w" II G' -ee)
(145)
SF(W') - VF(W)) G¹ +e") - f G¹ ee112
(146)
SF(W") - 1 VF - VF(W "f +
(147)
=F(w") - 171 VF
-VF(W!)T +
(148)
25

---

Under review as a conference paper at ICLR 2023
=F(w)) - nI /VF("') VF(W)) - VF(W") VFF(")Te M
(149)
Taking expectation on both sides, we have
B[F(W w', u'] v F(w') n |[F((*)] - n/ E VF ( I VF(W")) w ul]
CIVF(w*)"cc u'] + 1
B|| /w', u'] +
L. BB||c'
I u').
(150)
Based on Assumption and that |x11? - 211y11 + ||x - yl1? we have:
IVF |12 = [/VF(w*) VVF(W' VF(W2)]11
(151)
S 2 |VE((W + [[ - VF(w")]
(152)
IVF( + (VF --) VF(w')12
(153)
< IVF(( 21( + 2 11'1
(154)
In addition, using Assumption 3 Assumption
Assumption 5and Equation 143) we have:
E VF(W') G VF(W*)] w', u²) (PP(W)/w'uu u'] < IIVF(W")] || - E|G' VF(W") u'il
- E|G' VF(W") /
(155)
DD.
E VF(W") 1
Σ Fig (w (11)
w', u'
(156)
[
kEO j=0
$ DD
1
VF(w' u²) - VFcc( (1.) w m1
(157)
1
KEC ==0
D
I-1 ΣΣ
VF - VF( (1.0 -
E
1|9
+ [|
D
ΣΣ
E
7F(WttLO) -F w',u"
(158)
kEG 3=0
< [|91
L E
++00 u² --
w", w''u' + B)
(159)
NEG j=0
DL
<
[Iu'll
W/
++10 w
w/' /' + BD
(160)
T|G KEG 1=
DL
1 ('..u' + DL -| BD.
E
w
(161)
[||
j=0
#'=00
With Assumption we have:
E
+1,'
++1 +1
w', ur]
= E
Vi ( +
w u²]
S nD.
(162)
Therefore,
E ('' w [u]
-
26

---

Under review as a conference paper at ICLR 2023
DL
nD) + DL ||l'l + BD
(163)
[|91
REG j=0
5'=0
4T2
1-1
ΣΣ
(nnD) + DL. ||' + BD
(164)
[|
KEG j=0
4L
111 1)
|9|
11D DL ||u`l|| + BD
(165)
2
2(1 1)mDL2 + DL ||l0|| || BB.
(166)
Note that E X
S
X 2 Using Assumption and Lemma we have:
EVF((('' u'] B[IVF((*']I ||ee ||l u²]
(167)
([[[I u²] 18 el 12 w u²]
(168)
S (A + -2)) n7
(169)
nI ( +]
(170)
According to Assumption 5 and
1
B|||G"||| u') = E
(w
wt 11c
(171)
[[]]
kED 1=0
1-1
$ 1|9
E
(w
++1
2
w', u²
(172)
kEG 1=0
1
ΣΣ
(D² +
(173)
[
kEG
D2 + +02
(174)
Substituting (177).
154).
(66). (77
and 174 into 150), we have:
E E[F(W(+1) ww u'l s F(w') nI.
/ w ||( np E
w u²]
c/ u'1 1 || u'1 + L BBlle
12 P/ww' u2]
(175)
<((W') T
2 VF(w")) |22 + + 1
+ n/l [2( 1)nDL² + DD BD
+ 1/ +
+ +,2 + + L [ + 1)(D2 +02).00 17.
(176)
Note that E||u'| = / E ut' ||3 < u'122 Taking total expectation on both sides and using that
El < 411212 + 0²) 7
we have:
B|F(w+1)]] < B[F(W')]
7 +
+ +o?) .72
2
+ - DL -4+ - DBBD
172
+ +1108800(U[++(0++++++))
+ P + + +0²).
(177)
27

---

Under review as a conference paper at ICLR 2023
Namely,
B[F(W [[[(W")]
+ 11- o2 (D² 0²) + Sc0 + 1)(D2 + +
+ (n1)) (D + (n1) BD + /8c5 + 1)( 02)D
(178)
By taking summation from t= to T 1, we have:
[[F(WT)] E[F(w*)] T
E VF(w')1
2
t=
T(nT)2 2(1 1-1 DL ) 2HD D2 0z + (D2 +00) + +1)DD2 + oo)
+ +T(n)) 11122 + +2)| +
BD (
(179)
Note that w w and F(WT)= Ft Thus,
B||FF(W (1 2[
F*]
nIT
1=0
+ 211 2(1 - 1 DL 2 D2 +2 (D² + 0d) 8cd(4112 +))(D2 + +00
+ 18121111121000 + +
2 BD (888 D) +
(180)
In summary,
1 T-1
E [[/F(('') 2(F(ww) Fd)
+ + 1/ + A.
(181)
T
nIT
1=0
where 71 = -IIL [2(1 - 1 2HD 0² (D2 + 0²) 805 1) + +f)]
12- = ( + +2)
and A = =2BD + 1))(
B.8 ANALYSIS FOR LOCAL MOMENTUM SGD
We present the following proposition, which illustrates that Aasumption[]inn hollds when A is set to be local momentum SGD.
Proposition 3. Under Assumption 3 local momentum SGD satisfies Assumption 7 Moreover for local momentum SGD with learning rate 1) > 0, update interval I E N and momentum hyper-
parameter 3 E 1), we have 1A = n,,, A = ((1-8')
7(188) D +
2 + + + (221 + 11-882
(11--"
((-D)) LVD2 + o and (A²)² = 2 + +
Proof. When is set be local momentum SGD with learning rate 7,, update interval and momentum hyper-parameter 9, let m 0 be the initial momentum and w w+1 (t 0, 1,..., T 1) is computed by the following process:
m ++10 m
W ++10 = =w:
m ++15t1 = B- mmm ++1 + +(1 3)
Vf (w (11)).
j j= 0, 1, ..... I --
(182)
w 1+1h+1 w (+, m
141,+1
j == 0. 1 I...,
w w 1111
28

---

Under review as a conference paper at ICLR 2023
Let 77A nI, we have
I-1
1-1
Ga(w':Da) = (w' - w =
W
W/
m k
+45+
(183)
1=0
/=0
In addition,
m
(+15+1
=3 =3.mp mg + (1 - B) V (W (+1..)
1+1,5
(184)
= (3 m
(+1,j-1 (1 B) VSgs ( (+) + (1 () ( (1))
(185)
= = m
H+1-1 B(1 B) Vi +11-111 + (1 3) VS (w (w)
(186)
j
1+1,0 = m
+ (1- 3) Σ 3o-5 ( +115"
(187)
10=0
Now we prove that El|m 4. 1| < D2 + 0² (j= 0, ,,..,.., by deduction on
Step 1. When we have E. m 0.1 1| 05 D2 o².
Step 2 (deduction). Suppose E | 12 < D2 + 0², we have E Bllm 1- = E B| 1.1
< D2 + +
and E|/V (w 1+ )1(2 S D + 0 Since
33+1
g5+1 + (1- - B) Σ 9i-و g0++1 + (1 3)
1 1,
(188)
1'=0
(+1,++1 m
1+1,0 can be deemed as weighted averaging of m and (Vfar (+1 312 Thus,
m
++1,++ 1 S D2 +0²
j= 1.2,....,
(189)
By mathematical deduction, 1I = 0,1,..., T. we have
E [lmm t. < D + +0² j 0,1,2.....
(190)
Therefore,
1-1
E G (
E
Σ
m
++1
S SD2
(191)
5=
Substituting (187 into 183
we have:
Ga(w';Da)
m
1+1.0
+
+(1- 11-88 3)
Σ
3 3
1. (w [11)
(192)
1=0
3'=0
8(1 - 8)
1- 1-1
m
++1.
3
1,00 (w (111
(193)
7(1 - 3)
B(1 - 81)
m
++,0
1- 8
Σ
Σ
VS
(w(+1)) (111
(194)
I(1 3)
!=
B(1 81)
1- 8 I-1
BJ-
m
++1.
v V. (w (411
(195)
7(1 3)
1
0'=0
=1 1 1-
1
B(1 3*)
m
(+1,0
+
I-1 Σ
(1
3¹ 3
V f (1
(196)
=
29

---

Under review as a conference paper at ICLR 2023
Therefore,
3(1 - (8))
E[Gu(w')D,) VFF((w)]]
.E/m, 1+1,0 [Fx()')]
1 - 8
|-1
+
Σ (1
18 V for (wh vEW(w"))
(197)
j'=0
Since Bl|mm 11,0 - VFk(W)) 5 VD + oz
D and that
E V La (w ) (Fa(w")l
$ B VJ 4a5 (w/+
+1))) VV + EIVFF(W(+))) - VF&(w')]
(198)
s DV D2 + 0² + + -l|w
[/ wwll
(199)
1'11
$ D2 D2 0² +
mlmm
||
+11
(200)
1"=
$ SVD2 o2 + D2 D2
(201)
we have
[EGGu(w Dx)) (w')l
3(1 - -B))
I-1
$ I
IV + 0² +D
Σ
(1-B1a 31--)-3). D2 0² + jLLv DDVDD= D2 + o
(202)
1 B
j'=0
1
3(1 BB)
D+IVD2++ L D Φ²
1-1
(j' - (
(203)
- B
j'=0
1
B(1 BB") 1 B
(1(1-1)
+ 8 P[1-Bt (
3(1 - 1)
D D D2 + 0².
LV
2
(1- B)2
1- B
(204)
3(1- 31) ((1-31)
D + D2 + + +
111
81 -1-1)
B(1 -(1-1))
) .LV D2 + 02.
(205)
T(1 - (3
2
T(1
8)²
T(1
B.9 PROOF OF THEOREM 4
Proof. Similar to Lemma I and Lemma 2 we have the following inequalities to bound the local memory and the aggregation error, respectively, for general training algorithm A that satisfies
Assumption 7
Elgi
gk 1
(206)
d'
d'onss d
E Elggi 1|
(207)
d'ons
E Ellluj + (w' - -
(208)
d
IA
d'
d'ons
d' conss BBllu' 112 + (1 +
2d
1
Ell Ga(w": Di)Il
(209)
d
2d
d' d'onns
(m1)
d'ons
2d
E
1|
(na)² .E :
(210)
2d
d'
coms
(iv)
d' d'ons
2d
E
(1A))(A2))
(211)
2d
d'
d'oos
30

---

Under review as a conference paper at ICLR 2023
where (i) is derived based on Proposition (ii) is derived based on that (1y0=))ly||?
||x
+
y1 (1 + 0
2 for any constant 0 > 0. (iii) is derived based on that (1
d'
<
d
2d
2d
and (1 Leom (1
+
d'anne
d'
2d
d'aom"
(iv) is derived based on Assumption
Therefore,
Elluk 11 4d
d'enss 2d
4d (d'cons) )2 (11))
(nra) (A2)2
-
E
(d'ons)) )
(212)
Recursively using
(112) we have
4d2 (A2)² (1z))
d' d'ons"
4d
E
(d'ons)) (na)²
1
(12))
< 0.
2d
(d'oms)
(213)
Thus,
4d (A2)2
E Bl <
(dl )2 (111)2
(214)
Let H = /d. Finally, it is obtained that
4c{(A2)
B 1|2 2
E
uf || =
Σ
(na)) = (A2)
(215)
G
(d'coms) )2
kEg
kEG
Based on Assumption
7
we have that Ak E g.
E E
11
Elgg 1
=Bllui + (w' 111
(216)
uf <2B|uuf1
<
+ 2B 2B/lI//' w-
- 1
(217)
<2B||ug + 2(11) (A22)
(218)
<2(4/1 +1)(A2) (na)².
(219)
Thus,
Egyss [|le]
gl ||
< 2 1
21 < 8(411
1)( (na)).
(220)
Therefore, by Definition
and (220).
El|e*1 122 =E
ER (at
gk
(221)
9
kEg
$ cō Buys [lg] gk
12]
(222)
s 2 + 1)( (na)²
(223)
Let w 1 [o] Ekeg w w+1 Combining with Equation 142) we have:
w w (w' w(+ e'.
(224)
The equation can be interpreted as that w is obtained by adding small term -(w'- (W'--!++ w(+1) on w' with error e'. Therefore,
F(W(+1) = =F(W* (w" - w(+1) e¹)
(225)
<F(W") - VF(W"?(WW (w' - w(t +c+)+ + - | w + ee
(226)
2
<F(W") VF(W") -wth)- VF(W") + 12 - 11 Lile 1|2
(227)
=F(W") 9 KED
VF(W -w'-
2
-VF(W)T w¹
1
Σ w
+ L||e'112
(228)
9
KEG
31

---

Under review as a conference paper at ICLR 2023
- -
V VF(W") [w -w nA VF(W')
KEG
I
-VF(W*TT
Σ
||
|w'
w + 1|
(229)
191
KEO
=F(W9)- - 2AIIVF(W"))]
VF(WW) [MA Ga(w';Da) nA VF(w")
KEG
VF
L
Σ
1l Ga(W': +T|ee11
(230)
|9]
keg
Taking expectation on both sides, we have
B[F(w*+))|wv u']
< F(WW) - A VF VA g
D2) (
kEg
-VVF /' uf] [']]
(nA)²
L
E
: w ur)
+ L B. w
9
ked
(231)
By using Assumption
3
Assumption
Assumption
we have:
- E
(' D&) - [ } w', u²)
= VF((")"
[[G Dw)l u²] - [F((t)] [ D))l u'] VF(W''/
(232)
[F((")I
(233)
[[F((*)]
[ D&) w", w') Fw''(l
+I[VF((w")) VF VV / -V/(0)I]
(234)
<D. (A1 + B T.lww' w\l)
(235)
=A + BD + DT|[
(236)
Note that E[Xy] S V E| J. Based on Assumption
Assumption and 223). we have:
VE e'' e'/w", u'] < E[IVF[(W)]]
||ee |||w", u']
(237)
S [=]] u'] [B[le" 12 w u²]
(238)
I - +)))))))++((4)))()))))
(239)
= n v 1
(240)
According to Assumption
7
B|||G
; w u²| $ (Az)²
(241)
Substituting
154
223
236
240
and
241
into 231
we have:
E
F(( w u'
z F(w*)
nA
VF((*)
1|2 n 11
2
+ π
A, + BD + DL
u + 7A V 8c5(4H2 + 1)A2D
+ (Λλ) 2 + |8c6 + 1)(A2)² (TA)a].
(242)
Note that B||u'1|
E | <
E 1 and that E| 4H2 (A2)
Taking total
expectation on both sides, we have:
[]
1 (A))
2
32

---

Under review as a conference paper at ICLR 2023
+ nu (A + 8888(4H2 + 1)A2D
+ (na))((A2) +
L. +
(80((HH + (n1)²).
(243)
Namely,
E[F(W - [[P[(W)]
74 E1 + +
+
+ ((A)) + +HH +
+ 8c0 + ()2) 2].
(244)
By taking summation from t = to T 1, we have:
T-1
[[F(W")] S [[F
TA
E B + BD + +
+ 1)
2
t=
+ (A
(A2)
(A(
(245)
Note that w w and F(WT) 2 Thus,
2[F(W F*] BI
[2A, 2BD 44520 + 1]A2D]
nAT
+ 188) +na (2(A2) + 4HH)DL+
+ 11co5
16c6(144
(246)
In summary,
T T
2[F(w F
E
VF )1
-ATAA + (TA) + AA.
(247)
NAT
1=0
where Y,,1 2 L + 4HH + 1))A2))LL 7A.2 (A,' and A 2A, 2BD 200
2c0 4H² 1)A2D.
33

---

Under review as a conference paper at ICLR 2023
C MORE EXPERIMENTAL RESULTS
In this section, present empirical results, which consistent to the ones in the main text of this paper and further support our conclusions.
C.I MORE EXPERIMENTS ABOUT THE EFFECT OF ALPHA
We present more empirical results about FedREP with aggregators geoMed and TMean in this section. The experimental settings are the same as those in the main text. As illustrated in Figure] 3 the empirical results are consistent with that in the main text. In addition, we have also noticed that the performance of FedREP with TMean is not stable enough under ALIE attack. possible reason is that the aggregator TMean is not robust enough against ALIE attack since FedREP with each of the other two aggregators (geoMed and CClip) has a relatively stable empirical results. We will further study this phenomenon in future works.
Top-1 Accurae)
60
Top-1 Accuracy
60
Top-1 Accuracy
60
40
40
(1 244045
20 (THC
(04222
(T-4090074
13
70
(40001
55
(TH6,000600
048124
(T-00048728
(T....0TTHHH0 648128
20
40
60
100
120
40
60
100
120
20
60
80
100
120
Epoch
Epoch
(a) geaMed, flt-fiipping attack
(b) geoMed, ALIE attack
(c) geoMed, FoE attack
80
80
8D
Top-1 Accuncy
Top Accuntty
60
Top Accuncy
6o
40
+0.00 11:0 541515
500
1H 224330
0.00 943355
048214
043925
0.30
848235
20
20
20
863973
+0.00 (140 048713
E.00 (-10 045712
-.000
(140 548713
0
0
60 Epoch
120
0
20
80 100
20
40
100
120
Epoch
Epoch
(d) TMean, bit- flt-piipiin attack
(c) TMean, ALIE attack
(f) TMean, FoE attack
Figure 3: Top-1 accuracy w.r.t. epochs of FedREP with geoMed (top row) and TMean (bottom row) under bit-flipiig attack (left column), ALIE attack (middle column) and FoE attack (right column).
C.2 EXPERIMENTS ABOUT BYZANTINE ATTACKS ON COORDINATES
In each iteration of FedREP, clients will send the coordinate set I to server. However, Byzantine clients may send arbitrary coordinates. Although the theoretical analysis in the main text has included this case, we also provide empirical results about Byzantine behaviour on sending coordinates. We set a for non-Byzantine clients and consider four different Byzantine settings, where Byzantine clients send the correct coordinates (noAtk), send the coordinates of K smallest absolute values (minAtk), send random coordinates (randAtk) and send coordinates that is the same as a non-Byzantine client Atk), respectively. We set K 0.065d while the other settings are the same as those in Section in the main text. As illustrated in Figure 4l although the Byzantine attack on coordinates slightly changes the communication cost, it has little effect on the convergence rate K coordinates of each non- Beza--yyannee client and final top-1 accuracy. The main reason that the top- m can always be sent server in FedREP, matter what sent from Byzantine clients.
34

---

Under review as a conference paper at ICLR 2023
90
80
80
80
Accunnyy
Top- Accuncty
Top 1 Accuraty
50
030816
minAk 048616
-0
minAk [--3 050301
andkA (T-0.0500443
Bardank 045738
randAAk 050124
sammald (1r0 (1:0 30036
032432
9 033.333
40
40
60
120
20
80
100
Epoch
Figure 4: Top-1 accuracy w.r.t epochs of FedREP with different Byzantine behaviour on sending coordinates when there are 7 Byzantine clients with bit-flipping attack (left), ALIE attack (middle) and FoE attack (right), respectively.
Accurcc)
Top Accurcc)
60
Top 1 Accuracy
600
80
80
20
20
RCGD EF 05)
20
RCGO 11-5.051
20
-RCGD-EF 11-00FF
-.- FasREP gusMiel (w0 r-o (47456)
FauitE T.Nun (000) T-0 043500
---eSHEP wiCCipt ((00) 056545)
+ FRSREP ei gosMacl (-0 T-0.040973
FedtLE P w/ T'Naa (0-0 1-0 0463006640
+ FeSREP wiCCipt (,-0., 1-6.5483591
20
40
60
80
100
120
20
40
60
90
100
120
20
40
60
80
100
120
E Epoch
Epoch
Epoch
Figure 5: T accuracy w.r.t. epochs when there are 7 Byzantine clients with ALIE attack. B is the hyper-parameter of local momentum. Local momentum not used when = The robust aggregator in FedREP is set to be geoMed (left), TMean (middle) and CClip (right), respectively.
C.3 EXPERIMENTS ABOUT LOCAL MOMENTUM
Previous works (Karimireddy et al. 2021 ) have shown that using momentum can help to reduce the variance of stochastic gradients and obtain stronger Byzantine robustness. We also provide empirical results about the momentum in this section. The experimental settings keep the same as in Section in the main text. As illustrated in Figure using local momentum can make FedREP more robust to Byzantine attack ALIE, which is consistent with previous works (Karimireddy al. 2021).
C.4 COMPARISON WITH SPARSESECAGG
We first empirically compare the performance of FedREP with the communication-efficeent privacy- preserving FL. baseline SparseSecAgg (Ergun et al.) 2021) when there no attack. We test the performance of FedREP with buffer size s for SparseSecAgg in the two experiments, respectively. Correspondingly, we set K = 0.05d and K 0.1d in the two experiments for FedREP since the transmitted dimension number in FedREP is uncertain but not larger than K. Thus, we have r < K/d for FedREP. The top-1 accuracy w.r.t. epochs is illustrated in Figure/o The results show that FedREP can significantly outperform the existing communication-efffciee privacy-preserving baseline SparseSecAgg when there is no Byzantine attack.
and 16. respectively. We set I 0.05 and 0.1
In addition, we have tried different learning rates for SparseSecAgg and it has the best perfor- mance when learning rate equals 5. As illustrated in Figure 7 FedREP significantly outperforms SparseSecAgg on top-1 accuracy when communication cost is similar. The communication cost of SparseSecAgg is much more than FedREP when the performance on top-1 accuracy is comparable. For one reason, FedREP is based top- K sparsification while SparseSecAgg is based random- K sparsification. For another reason, FedREP adopts compesatmennnnion technique while SparseSecAgg does not.
35

---

Under review as a conference paper at ICLR 2023
80
80
80
Accuncyy
60
Top Accuncyy
60
Top Accuraty
60
15
enA.g
Sparses (T-00.00 000
Sparse5 I1-0 00)
parseSeckgp 11=0
lecit EP (s
eeR EP (5
-.RREE Ps.0.. edRLi 1s-06, (:20.05)
eolht (und, (1:0
edit LP (umt) 1:c0
0
0
60 Epoch
120
20
80
100
Epoch
Figure 6: Top-1 accuracy w.r.t. epochs of FedREP and SparseSecAgg when there is no attack. The buffer size for FedREP is set to be 4 (left), 8 (middle) and 16 (right), respectively.
80
80
80
Accuacy
60
Top1 Accuncy
60
Tep Accuncy
60
Sparren uo
Sparnes wo (h-0.1, (-m))
o (m)2)
40
sd4gp 11
Sparse
Sporses (1-6
Sporses
paases ackgo (1-0.25 (m)00)
parses ucAgo (h-0. 1-100)
Sparses scAgo [1-0.2 F-400)
20
parses ac [1.0.15, (mx00)
20
passes uc4gp (1-d. 1. 10000
20
Sparess acAgp [1-0.2 1-200
Fectt ni mean (snd, 1-c0
FedRie mimen jond,
Feef wimeen (snd, 1-c0 13
1:00
(:0.00)
(:00.00)
0
0
60 Epoch
120
80
Epoch
Epoch
Figure 7: Top-1 accuracy w.r.t. epochs of FedREP and SparseSecAgg when there no attack. I' for SparseSecAgg is set to 0.05 (left), 0.1 (middle) and 0.2 (right), respectively. The learning rate (Ir) for FedREP is set to 0.5.
C.5 COMPARISON WITH SHARE
We empirically compare the performance of FedREP and SHARE (Velicheti et al. 2021 in this section. Both FedREP and SHARE are FL frameworks that can work with various local training algorithms on clients. Compared to SHARE, the main advantage of FedREP is the consensus sparsification. Moreover, FedREP degenerates to SHARE when consensus sparsification hyper- parameter K = md. Therefore, we compare SHARE and FedREP with different I when keeping other conditions the same. Specifically, we set buffer size (a.k.a. cluster size in SHARE) to be 4 and local training algorithms to be vanilla SGD for each method. The other settings are the same as those in Section the main text of this paper. Since the actually transmitted dimension number is uncertain in each communication round for FedREP, we count the average transmitted dimension number of all communication rounds and use as a measurement of communication cost. The experimental results of FedREP and SHARE when there are no Byzantine clients are illustrated in Figure [8 The experimental results of FedREP and SHARE when there are 3 Byzantine clients under bit-flipping attack, ALIE attack and FoE attack are illustrated in Figure 9 Figure 10 and Figure [1] respectively. As we can see from the empirical results, compared to SHARE, there is almost no loss on the convergence rate and final accuracy when I' is about 0.079 for FedREP. In addition, there is only a little loss on final accuracy when I' is as low as about 0.017.
Interestingly, when under ALIE attack, empirical results show that FedREP has even higher final accuracy compared to SHARE. We conduct an extra experiment to compare the performance of FedREP and SHARE when there are 7 Byzantine clients with ALIE attack. We set local training algorithm to be momentum SGD with 3 = 0.9 and buffer size
in the extra experiment. The other settings the same. As illustrated in Figure 12 FedREP can still outperform SHARE in this setting. A possible reason is that the consensus sparsification in FedREP can lower the dissimilarity between the updates of different clients and thus lower the aggregation error (please see Definition in the main text for more details). However, it requires more effort to further explore this aspect and we leave it for future work. In summary, FedREP has a comparable performance to SHARE on convergence rate and final accuracy, but has much less communication cost than SHARE.
36

---

Under review as a conference paper at ICLR 2023
90
80
80
80
Accuracy
Top Accuncty
Top Accuraty
70
70
50
50
SHARE (1:000174533
50
EORE groMed F-0 042067
groMed
50
TeCREP
POREP TMean (1:00 0436.0
-TedRE WcCCCp (1-00 042002
FedRER KCCCClp (1:00 012426
groMed 100.0 0/93L
POREP IMean 07-50.55052
FdRRE WCCC (1-0 05000
40
40
40
120
100
poch
poch
Figure 8: Top-1 accuracy w.r.t. epochs of FedREP and SHARE when there are Byzantine clients.
80
Accurayy
Top Accurayy
Top Acturay
70
-0
60
50
60
SHARE gooMest [1=)
SHARE NY TMeaM [E
SHARE WI CCIP((-)
EdRIP mt groMed 1-0.01 017637
Fed INeen (37-0.01
16
FediE CC- 01-3001355
mt geoMed 1- 667667
(1101041535
FedRiE (C-CClp11-000 (1-0:04::4 04:0041:440
W/ ocoMest
FodREP (000:p:0-000000
60
80
100
120
20
60
80
100
120
20
40
80
100 120
Epoch
E Epoch
Epoch
Figure 9: Top-1 accuracy w.r.t. epochs when there are 3 Byzantine clients with bit-flipping attack.
90
90
90
80
Top Accurayy
Top Accuncy
Top Accuraty
50
50
-SHAARE groltedd [m]
SHARE THean
SHARE wi (CH)
50
-+-FedREP P w/ geofted I- 040748
F-odREP P w/ gootted (T 017196
50
--FeeREF P THean (2-0 01-00441224
FocR THean 011000
+- FedREP CCC 0-2477
FedREP CCCC (1-0011002
- edREP P wl grofted (-0.077441
- edR P TWean (7-0.677123
FedREP w/ :-00::pp-00000000000
60
80
100
120
20
80
100
120
20
40
80
100
120
Epach
Figure 10: Top-1 accuracy w.r.t epochs when there are 3 Byzantine clients with ALIE attack.
90
80
80
80
Accuacy
Top11 Accuncy
Top-1 Accuacy
70
20
20
80
60
SHARE gww.est [T=]]
THiean IT=3)
SHARE WI CCIP
gooMedd
50
36
W/CCClp: 0173377
078841
FodREP TMean 075464
FedREP (-00077953)
40
40
40
Epoch
Eoch
Epoch
Figure Top-1 accuracy w.r.t. epochs when there are Byzantine clients with FoE attack.
90
80
80
Top Accurasy
Top Accumcy
Top' Accura)
60
60
30
SHARL geotes [=1
SHARE HY IMean [Ts]
SHARL wi (CC
FodREP el acoleed (1 (1 0000455555
FeoR w/ TNean (1-00 014886
FodREP w/Ccle (00 C16484
30
FodREP e/ gcolked 035150
30
FedR w/ TMean (1400 C34046
30
FodREP CCCC 1-0 037341
mt geoked p-6.080076
12-0.258367
20
40
60
30
100
120
0
20
40
60
80
100
120
20
40
60
80
100
120
Epoch
Epoch
Epoch
Figure 12: Top-1 accuracy w.r.t. epochs when there are 7 Byzantine clients with ALIE attack.
37


Reviews:
[{"review_id": "qj_eiy91f9", "reviewer": "Reviewer_VCzw", "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": "This paper considers the problems of communication efficiency, Byzantine robustness, and privacy in federated learning (FL). The paper focuses on sparsification for compression (in order to achieve communication efficiency), and analyzes what are conditions on sparsification to ensure that the expected pairwise l2-distance between client updates after sparsification remains bounded. Next, the paper proposes a sparsification technique -- consensus sparsification, which is a two-phase scheme that ensures that all clients agree on the same set of coordinates. The paper then combines it with a hierarchical scheme to enhance privacy, wherein sparsified updates from a subset of clients are first aggregated using secure aggregation, and then a robust aggregation is applied on top for Byzantine robustness. The paper analyzes the convergence rate for the proposed scheme.", "summary_of_the_review": "My main concerns are mentioned in the section on Weaknesses. Due to these issues along with a limited novelty, it seems to me that the paper is not yet ready for publication. \n\nAdditional suggestions and questions to improve the quality of the presentation are give below:\n\n1. In Theorem 1, it is not clear why the conditions $\\sum_{j\\in[d]} \\xi_{k,k’,j} =1$ and $\\sum_{j\\in[d]} \\zeta_{k,j} =1$ will be satisfied. Is it assumed that update vectors are normalized? \n\n2. Footnote 3 mentions that random quantization can be adopted for “more privacy preservation”. What do the authors mean by “more privacy preservation”? Why would random quantization increase the level of privacy?\n\n3. On page 2, it is mentioned that there are two ways to achieve privacy: differential privacy and secure aggregation. This is a bit misleading. Secure aggregation does not guarantee the privacy of training data, but only ensures the privacy of computation (i.e., aggregation operation). In other words, SecAgg ensures that the clients (and the server) observe only the aggregate model and cannot learn individual model updates. DP would be necessary to ensure input privacy. (For instance, in case of only 2 clients, even when secure aggregation is used, each client can compute the model update of the other client from the average.) It will be helpful to discuss this.\n\n4. Before stating the main contributions, the paper claims that: “we theoretically analyze the tension among Byzantine robustness, communication efficiency and privacy preservation, and propose a novel FL framework called FedREP”. The paper analyzes the tension between sparsification and the condition required by $(\\delta, c)$-robust aggregator. In other words, the tension between communication efficiency and Byzantine robustness. It is not cleat where the tension between the privacy and the other objectives is analyzed. It would be good to give a bit more details.\n", "strength_and_weaknesses": "**Strengths:**\n1. The paper considers a practically important and intellectually challenging problem of simultaneously achieving communication efficiency, Byzantine robustness, and privacy.\n\n2. The analysis of sparsification schemes to ensure assumptions in Def. 1 ($(\\delta, c)$-robust aggregator) is interesting. \n\n**Weaknesses:**\n1. For privacy, the paper proposes a hierarchical approach where clients are randomly partitioned and then an aggregate update is computed for each partition using secure aggregation. This is essentially the bucketing approach from [Karimireddy et al. ICLR 2022] with additional secure aggregation. From the perspective of novelty, this is fairly limited. More importantly, this method would only enhance privacy, but there is no analysis about how much is the enhancement. (In fact, the authors acknowledge at the end of Sec. 3 that further study would require to quantify the privacy leakage.) On the other hand, the paper claims in the Abstract and Introduction (Table 1) that their method is privacy-preserving. This seems like a bit of over claiming. \n\n2. The analysis in Theorem 1 is to ensure the assumptions in Def. 1 ($(\\delta, c)$-robust aggregator). The assumption of bounded pairwise distances is sufficient, but it is not discussed if it is necessary. Can there be another definition for a robust aggregator that does not need to assume bounded pairwise distances? There may be empirical robust aggregators that perform decently even without the assumption of bounded pairwise distances. It would be important to discuss this point. \n\n3. The $\\epsilon$ parameter of DP in Theorem 2 seems to be quite large. In particular, it is of the order $O\\left(\\frac{\\frac{K}{m}(d - \\frac{K}{m})}{\\alpha}\\right)$, which seems to be at least $O(d)$. Since deep neural networks have large $d$, the value of $\\epsilon$ may be too high for practice. It would be important to discuss this further.\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": "k2ffpWO8bj", "reviewer": "Reviewer_LcWV", "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 paper propose the first federated learning system which supports privacy, communication efficiency and byzantine-robustness. Specifically, it designs a consensus sparsification protocol to compress the update and also keeps compatible with secure aggregation and robust aggregation.", "summary_of_the_review": "The paper is a borderline one. I slightly tend towards acceptance but I am okay either way.\n\nThe biggest problem is that the authors do not discuss the influence of potential malicious attacks during the sparsification step. This makes the privacy guarantee questionable.\n\n----------------------------------------------------------\nThank you for the rebuttal. I decide to keep the score after reading it.", "strength_and_weaknesses": "Strength:\n1. Reconciling byzantine robustness, communication efficiency and privacy is an important topic in federated learning system design.\n2. The evaluational results show reasonable trade-off between the three dimensions.\n\n\nWeakness:\n1. The authors did not discuss the potential malicious behavior during the consensus sparsification. What if some malicious client always upload misleading $I^t_k$? Will that affect the robustness or the privacy of the protocol?", "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": "Omrmireqt3-", "reviewer": "Reviewer_UUqC", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 authors study the conditions that a communication compression method should satisfy to be compatible with existing Byzantine-robust methods and privacy-preserving methods. The core of their proposed method is consensus sparsification, which is a variant of top-$K$ sparsification with additional memory and a random selection component aiming at obscuring exact coordinates for sparsification. Their idea is that as long as the clients agree on non-zero coordinates, the dissimilarity among clients reduces, which is intuitive while they achieve communication saving through sparisification and preserve privacy by applying SecAgg off the shelf. ", "summary_of_the_review": "The key idea of this paper is consensus sparsification, which is a variant of top-$K$ sparsification with additional memory and a random selection component to improve privacy. ConSpar along with SecAgg is an interesting algorithm in terms of addressing communication costs and privacy risks. The main weakness is w.r.t. robustness. The attacks considered are very simple and not designed for ConSpar. I think the smaller dissimilarity in Proposition 1 does not imply improved robustness. ", "strength_and_weaknesses": "I think the paper is well-written. There are interesting algorithmic elements including the introduction of random variable $r_k^t$ with binomial distribution to improve privacy. The related work are sufficiently studied. I think ConSpar along with SecAgg is an interesting algorithm in terms of addressing communication costs and privacy risks. However, I am not sure it is much interesting in terms of  robustness. \n\n1- The main weakness of this paper is that the considered attacks are very simple and not designed for ConSpar, which will be elaborated in the following: \n\n- The type of attacks considered are mainly attacks effective against Krum and comed. What if an adversary constructs ${\\cal I}_k^t$'s that target the **most informative coordinates of average update of honest clients** and make them zero. In that case, even if the server  perfectly detects all Byzantines, the server can only figure out the average of least informative coordinates of  good client, which does not help the server to learn an effective model. In particular, an attack, which tries to remove the most informative coordinates from the aggregate of good updates should be considered. I also checked the results in Appendix C.2. However, those experiments do not consider this attack. \n\n2- Regarding FoE attack. I am not sure why  the hyperparameter is set to 0.5. Xie et al., 2020a proposed to apply a number of $\\epsilon$'s including 0.1 and 10 so I am curious why the authors selected 0.5? \n\n3- The idea is that sparsification makes the clients updates closer to each other. The smaller dissimilarity in Proposition 1 implies that it is easier fo find $\\frac{1}{|{\\cal G}|}\\sum_{k=1}^{|{\\cal G}|} \\tilde g_k$. However, it does not guarantee anything about the quantity of interest $\\frac{1}{|{\\cal G}|}\\sum_{k=1}^{|{\\cal G}|} g_k$. Note that $\\frac{1}{|{\\cal G}|}\\sum_{k=1}^{|{\\cal G}|} \\tilde g_k$ may be arbitrarily different from $\\frac{1}{|{\\cal G}|}\\sum_{k=1}^{|{\\cal G}|} g_k$. \n\n4- Definition 1: The upper bound $\\rho$ for (Karimireddy et al., 2021) holds only for those good clients but Definition 1 includes a bound on all $m$ clients.\n\n5- \"As shown in previous works (Karimireddy et al., 2021), many widely-used aggregators, such as Krum (Blanchard et al., 2017), geoMed (Chen et al., 2017) and coordinate-wise median (Yin et al., 2018), satisfy Definition 1.\" \n\n- Could you specify where this is shown in (Karimireddy et al., 2021)? It is shown that Krum and coordinate-wise median are vulnerable to simple attacks (Fang et al., 2020; Xie et al., 2020). I am not sure how much Definition 1 is meaningful in terms of robustness in practical settings. \n\nMinghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. Local model poisoning attacks to byzantine-robust federated learning. In Proc. USENIX Security Symposium, 2020.\n\nCong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking byzantinetolerant SGD by inner product manipulation. In Proc. Uncertainty in Artificial Intelligence Conference, 2020.\n\n6- Assumption 5 does not hold even for a quadratic loss function. Can the author clarify why Assumptions 3 and 4 are not sufficient to establish convergence guarantees?  \n\n7- \"Even with quantization, ... suffers from heavy communication cost.\"\n\n- One advantage of unbiased quantization schemes is that the same test accuracy as the uncompressed baseline is achievable while achieving communication efficiency. It is unclear how much test accuracy is lost under same hyperparameters tuned for uncompressed baseline if someones uses consensus spartifications under no attack scenario?\n\n\n\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": "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": "6KKmKB9JX90", "reviewer": "Reviewer_jrY6", "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": "This submission introduces a local sparsification scheme in the federated learning setting to reduce the data transmission burden. The scheme starts with sampling certain ratio of coordinates with largest magnitude, before adding in some randomly selected coordinates to meet the pre-designated sampling budget.\n\nThe authors intend to prove that the suggest sparsification scheme has differential-privacy property, and also shows the convergence of the resulted federated learning algorithm.", "summary_of_the_review": "The optimization proof did not include the buffer steps, which are stated in the main algorithm.\n\nThe writing of the paper needs major overhaul. The description of technical details should be direct to the point, specific and explicit, and the statement of theorems must be rigorous and detailed.\n\nI recommend rejection.", "strength_and_weaknesses": "Strength:\n\n--> the structure of this submission is clear.\n\n--> Proposition 2 about the contraction property of the proposed ConSpar algorithm is useful for the general community.\n\nWeakness:\n\n--> Some proof steps are problematic.\n\n--> The writing should be overhauled.", "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": "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": {}}]

Author rebuttal:

Decision: Reject