Federated Learning via Plurality Vote
Authors: Kai Yue
Richeng Jin
Chau-Wai Wong
Huaiyu Dai
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning via Plurality Vote

Abstract: Federated learning allows collaborative workers to solve a machine learning problem while preserving data privacy. Recent studies have tackled various challenges in federated learning, but the joint optimization of communication overhead, learning reliability, and deployment efficiency is still an open problem. To this end, we propose a new scheme named federated learning via plurality vote (FedVote). In each communication round of FedVote, workers transmit binary or ternary weights to the server with low communication overhead. The model parameters are aggregated via weighted voting to enhance the resilience against Byzantine attacks. When deployed for inference, the model with binary or ternary weights is resource-friendly to edge devices. We show that our proposed method can reduce quantization error and converges faster compared with the methods directly quantizing the model updates.

Under review as a conference paper at ICLR 2022
FEDERATED LEARNING VIA PLURALITY VOTE
Anonymous authors
Paper under double-blind review
ABSTRACT
Federated learning allows collaborative workers to solve machine learning prob- lem while preserving data privacy. Recent studies have tackled various chal- lenges in federated learning, but the joint optimization of communication over- head, learning reliability, and deployment efficiency is still an open problem. To this end, we propose a new scheme named federated learning via plurality vote (FedVote). In each communication round of FedVote, workers transmit bi- nary or ternary weights to the server with low communication overhead. The model parameters aggregated via weighted voting enhance the resilience against Byzantine attacks. When deployed for inference, the model with binary or ternary weights is resource- resource-friendly to edge devices. We show that our pro- posed method can reduce quantization error and converges faster compared to the methods directly quantizing the model updates.
INTRODUCTION
Federated learning enables multiple workers to solve machine learning problem under the coor- dination of central server (Kairouz al. 202T). Throughout the training stage, client data will be kept locally and only model weights or model updates will be shared with the server. Fed- crated averaging (FedAvg) (McMahan et al. 2017) was proposed as generic federated learning solution. Although FedAvg takes advantage of distributed client data while maintaining their pri- vacy, it leaves the following two challenges unsolved. First, transmitting nigh-dimensional messages between a client and the server for multiple rounds can incur significant communication overhead. Quantization has been incorporated into federated learning in recent studies (Reisizadeh et al., 2020) Haddadpour et al. 2021). However, directly quantizing the gradient vector may not provide the op- timal trade-off between communication efficiency and model accuracy Second, the aggregation rule in FedAvg is vulnerable to Byzantine attacks (Blanchard et al. (017)) Prior works tackled this issue by using robust statistics such as coordinate- median and geometric median in the aggre- gation step (Blanchard et al., 2017 Yin al. 2018). Another strategy is to detect and reject updates from malicious attackers algorithm is enhanced at the cost of additional computation and increased complexity of algorithms.
et al. 2019; Sattler et al. 2020). The robustness of the
In this paper, we propose a new method called federated learning via plurality vote (Fed We train a neural network at each worker with a range normalization function applied to model param- eters. After local updating, binary/ternary weight vectors are obtained via stochastic rounding and sent to the server. The global model is updated by voting procedure, and the voting results are sent back to each worker for further optimization in the next round. The contributions of the paper are summarized as follows.
1. We present VedVote as a novel federated learning solution to jointly optimize the commu- nication overhead, learning reliability, and deployment efficiency.
2. We theoretically and experimentally verify the effectiveness of our FedVote design. In bandwidth-limited scenarios, FedVote is particularly advantageous in simultaneously achieving high compression ratio and good test accuracy. Given a fixed communica- tion cost, Vote improves model accuracy on the CIFAR-10 dataset by 5-10%, 15-20%,
Prredictive coding in video and image compression Li al that directly quantizing the raw signal we intend to transmit does not provide the best trade-off between the coding efficiency and the utility/hitrate.
Gonzalez & Woods 2014 is an example 2015

---

Under review as a conference paper at ICLR 2022
and 25 30% compared with FedPAQ (Reisizadeh et al. 2020 signSGD Bernstein et al. 2018 and FedAvg, respectively.
3. We extend FedVote to incorporate reputation-based voting. The proposed method, DyzaatinneFFedoode exhibits much better resilience to Byzantine attacks in the presence close to half attackers without incurring excessive computation compared with existing algorithms.
RELATED WORK
Communication-EFFi Effficeent Federated Learning. In the prior study of federated learning, various strategies have been proposed to reduce communication cost. One research direction is to reduce the size of messages in each round. For example, [Brnsttii et al. (20T8) showed that sign-based gradient descent schemes can converge well the homogeneous data distribution scenario, while CCen et al.) (2020); Jin al. (2020); Safaryan & Richtarik (2021) extended it to the heterogeneous data distri- bution setting. In parallei, FedAvg adopts periodic averaging scheme and targets at reducing the number of communication rounds (McMahan al. 2017). Hybrid methods consider simultaneous local updates and accumulative gradient compression (Reisizadeh et al. [2020] [Haddadpour et al.) 2021]. In this work, we improve communication efficiency by employing binary/ternary weights in the neural network.
Quantized Neural Networks. Quantized neural networks aim to approximate the full null-precision networks using quantized weights while keeping their generalizability. As a special case, binary neural networks (BNNs) are gaining popularity recent years. By restricting model weight values to (11,+1+ ). BNNs can reduce computational cost, memory requirement, and energy consumption. Hubara et al. 2016) introduced real-valued latent weights and used the sign operator for binarization. In contrast, Shayer et al. (2018) let the neural network learn the distribution of the binary ternary weights. [ong et al.] (2019) added a soft quantization function to the real-valued weights, thus avoiding the gradient mismatch between the forward and the backward passes. A more thorough survey on BNN optimization can be found in Qin et al. (2020a).
Distributed Optimization of Quantized Neural Networks. A few recent works have explored BNN optimization in a distributed setting, which is more relevant to our work. Lin et al. (2020) conducted the case study of 1-bit quantized local models aggregated via ensemble distillation. The aggregation becomes complicated due to the separate optimization stage of knowledge distillation. especially when the distillation algorithm does not converge well in practice. In addition, their
BNN optimization is not tailored to the federated learning setting. Hou et al. (2019) theoretically analyzed the convergence distributed quantized neural networks, which was later implemented in the application of intrusion detection (Qin et al., (0206). In comparison. FedVote is presented as a new algorithm by leveraging client local updates to accelerate the training. Different from Hou et al. (2019), we do not assume convex and twice differentiable objective function and bounded gradients. Therefore, the analyses in Hou et al. 2019) cannot be directly applied to our study.
Byzantine Resilience in Federated Learning. An attack is Byzantine if arbitrary outputs are produced due to the adversary (Kairouz et al. 2021). Blanchard et al. (2017) showed that FedAvg cannot tolerate a single Byzantine attacker. They proposed an aggregation--ule-basee remedy using the similarity of local updates. Similarly, Yin et al. (2018) took the advantage coordinatewise median and trimmed-mean to robustify the aggregation. Munoz-González et al. (2019) and Sattler ct al. (2020) detected the adversaries and filtered out their model updates. In this paper, we propose reputation based voting strategy for FedVote that is shown to have good convergence performance in the Byzantine setting.
3 PRELIMINARIES
Symbol conventions are as follows. Bold lower cases of letters such as um denote column vectors, and i é used to denote its ith entry. For a scalar function, it applies elementwise operation when vector input is given. [1....,] 1]T denotes vector with all entries equal 1.
2

---

Under review as a conference paper at ICLR 2022
3.1 FEDERATED LEARNING
The goal of federated learning is to build a machine learning model based on the training data distributed among multiple workers. To facilitate the learning procedure, server will coordinate the training without seeing the raw data (Kairouz et al. [02T]. In supervised learning scenario, let
Dm ((Xm...X ([Xmm.--mm))]. Jm fm denote the training dataset on the mith worker, with the input Xm, R
and the label Ym.j E IRd in each training pair. The local objective function fm with model weight vector A E IRd is given by
fm (0) A fm (0:
e(0; (Xm.ji Mm.)),
Tlya
where E is loss function quantifying the error of model 0 predicting the label ym.j for an input Xm.j. A global objective function may be formulated as
1
min f(0) ARRd
Σ (0).
M
3.2 QUANTIZED NEURAL NETWORKS
Consider neural network with the weight vector 0 E Rd. A forward pass for an input x E RR and a prediction y E & can be written as y g(0,x) x). In quantized neural networks, the real- valued 0 is replaced by E Dr where D, is a discrete set with a number n of quantization levels. For example, we may have [B2 = {-1, 1} for a binary neural network. For a given training set {(x). 1ー and the loss function the goal is to find optimal w" such that the averaged loss is minimized over a search space of quantized weight vectors:
N
w argmin WED.
((: (x). 2=1
(3)
Prior studies tried to solve 3 by optimizing real-valued latent weight vector h Rd (Hubara et al. 2016, Shayer al. 2018 Gong et al., 2019). The interpretations of the latent weight vary when viewed from different perspectives. Hubara et al. (2016) used the sign operation to quantize the latent weight into levels during the forward pass. The binary weights can be viewed an ap- proximation of their latent real-valued counterparts. [Shayer et al. (018) trained a stochastic binary neural network, and the normalized latent parameters interpreted as the Bernoulli distribution parameter d;;
2 P(w; 1) S(h,), wy (0, 1),
(4)
where S R + (0, 1) is the sigmoid function. In the forward pass, instead of using the binary vector w, its expected value,
W Wsto-ban
A E[w] = 1 - + 5x = 2h) 1,
(5)
will participate the actual convolution or matrix multiplication operations. other words, the neural network function becomes y o( sto-bun: x). Likewise, Gong et al. (2019) normalized the latent weight but interpreted it from different viewpoint. They approximated the staircase quantization function with a differentiable soft quantization (DSQ) function, i.e..
Wasq tanh(ah),
(6)
where (anh R + (-1,1) is the hyperbolic tangent function, and controls the shape of the function. The neural network function thus becomes y = g( x..
We now summarize the latent- siient-weight-baseee BNN training methods and depict an example of single-layer network in Figure [ First, a real-valued vector restricted using differentiable and invertible normalization function ; IR + (-1, The forward pass is then calculated with the normalized weight vector w. The procedure is described as:
gd is introduced and its range is
y g W, x), W p(h).
(7)
Second, the back propagation, the latent weight vector is updated with its gradient, i.e.. h (++1) = (t) v, Finally, the normalized weight vector w are mapped to the discrete space approximate w" via thresholding stochastic rounding.
3

---

Under review as a conference paper at ICLR 2022
input
x W
server calculates the valtng statistics
a nonlinear activatiio
normalized weight
W
sends quarlizzdd weight w (f.))
the resalts
nommalization
(P))
W
latent weight
h
local updaties
that yields Win
worker
Figure 1: Example of single-layer quantized neural network with latent weight vector R. h is normalized to generate w E ()1, and the output is y o o( x). binary weight Wa can be obtained by thresholding or rounding w to the discrete space D.
One round of FedVote is composed of four steps. Each worker first updates the local model and then sends the quantized weight wm." to the server. Later, the server calculates the vot- ing statistics and sends back the soft voting results p (k+1l) to each worker.
Figure 2:
(k.r)
PROPOSED FEDVOTE ALGORITHM
In this section, present proposed method with emphasis uplink communication effi- ciency and enhanced Byzantine resilience. We follow the widely adopted analysis framework in wireless communication investigate only the worker uplink overhead, assuming that the downlink bandwidth is much larger and the server will have enough transmission power (Tran et al.) 2019). To reduce the message size per round, train quantized neural network under the federated learning framework. The goal is to find a quantized weight vector w that minimizes the global objective function f formulated in i.e.
W argmin f(w).
(8)
wED4
For the simplicity of presentation, we mainly focus on the BNN case with Dy = (-1,1}. We illustrate the procedure in Figure and provide the pseudo code in Appendix B Below, explain each step in more detail.
4.1 LOCAL MODEL TRAINING AND TRANSMISSION
We optimize neural network with learnable latent weight vector h. In the kth communication round, we assume all workers are identically initialized by the server, namely, V m E (1,..., M.,, (k:D) (*)_ To reduce the total number of communication rounds, first let each worker conduct local updates to learn the binary weights. For each local iteration step, the local latent weight vector h (k,++1 is updated by the gradient descent:
h h (k,++1) = (k:,)) WnJm (v(hh(h-)) (k.0))
</hit)) )(
EE (0. .O. 1}.
where <lh.0) mini-batch randomly drawn from Dm at the ith iteration of round k. After updating for т steps, we obtain h (k,7) and the corresponding normalized weight vector wm (kkr) defined as follows:
E (-1, 1)d
m (k,r) A (hh (kir)).
(10)
To reduce the message size, we use the stochastic rounding to draw randomly quantized version (k.7) using with namely. wm
+1, with probability of (A:.)) 1 (A.77 m.s
(k.7) w m,
W
+
(11)
1, with probability 1 1 π Tm.i
(k.7)
It can be shown that the stochastic rounding is an unbiased procedure, i.c., Ej B(ww Wm
(k.7)
(hir)
W After quantization, the local worker will send the binary weights wh to the server for the global model aggregation.
(k.T)

---

Under review as a conference paper at ICLR 2022
4.2 GLOBAL MODEL AGGREGATION AND BROADCAST
Once the server gathers the binary weights from all workers, it will perform the aggregation via tie in vote will be broken randomly. In the following lemma, we show that the probability of error reduces exponentially as the number of workers increases. The proof can be found in Appendix [D.I
plurality vote, i.e., w(++1) sign (EM= w
wm
Lemma 1 (One-Shot FedVote) Let w" TDr be the optimal solution defined in S For the mith worker, Em,, - PP (k.7) m. * wx) denotes the ervor probability of the voting result of the ith coordi-
nate. Suppose the error events (k.)) * " M are mutually independent, and the mean error
probability 81 = 37 Em== Em, smaller than z. For the voted weight w(--1), we have
PP (w (1+1) # (w]) < [28, exp(1 - -28;)]
(12)
In practice, the number of available workers may be limited in each round, and the local data distri- bution is often heterogenous or even time-variant. Therefore, it is almost always desirable to execute FedVote in a multiple-round fashion. In this case, we first use the soft voting build an empirical distribution of global weight w, i.e.,
P(m(+t)) (++1)) =1) ((
1 M
Σ
1
(w mmm.
1 =1),
(13)
where (-) E {0, 1} is the indicator function. Let Pz [p] (k+1) Pd. (++1)TT The global latent parameters can constructed by following (10)
(k+1) F( = 1) and p(++1)
h (++1) - (22())))) 1),
(14)
where 8-- (-1,1) + R is the inverse of the normalization function sp We further apply clip- ping to restrict the range of the probability, namely, clip(p,*+1)) max(pmin min (piax, Pa ( where Pmin: Pmmx E (0, 1) are predefined thresholds. To keep the notation consistent, we denote ((++1) & (k+1)) as the global normalized weight. After broadcasting the soft voting results (l++1, all workers are synchronized with the same latent weight h (*++) and normalized weight ((++)) The learning procedure will repeat until termination condition is satisfied. We relate FedVote to FedAvg in the following lemma. The detailed proof can be found in Appendix D.2
Lemma 2 (Relationship with FedAvg) For the normalized weights, FedVote recovers FedAvg in
expectation: E [W(+
Σ ~ w(kkr) (k:T)) where (k+1) = (p(h (k+2)) and wilk.)) (h(((:)))
4.3 REPUTATION -AASD SIRZANTINE-FEVOOT
Lemma 2 shows that Ved is related to FedAvg in expectation. As we have reviewed in Section
2. FedAvg cannot tolerate single Byzantine attacker. indicates that Vote will exhibit similar
poor performance in the presence of multiple adversaries (see Appendix C.2 We improve the design of FedVote based on a reputation voting mechanism, which in essence is a variant of the weighted soft voting method.
Reputation- based voting was presented in failure-robust large scale grids (Bendahmane et al. 2014).
= =1), where (1ke) is proportional to credibility score. In Byzantine-resilien Fed (Byzantine-FedVVott) we assume that least 50% of the workers behave normally and treat the plurality vote result as the correct decision. The credibility score of the mith worker is calculated by counting the number of correct
In our design, we modify (13 ((( (k+1) 1) -MM- M ((h) 1
(u.(k.7) (k.kk)
votes makes: (k++11 = E (wih,?7
(k,7) w. (((++))). Through multiple rounds, we track
in
the credibility of local worker by taking an exponential moving average over the communication rounds, namely, vn (k+1) = 33 vm + (1 - B) CR (R++1) where 3 E (0, 1) is a predefined coefficient.
The weight ( is designed X (k) Σ D Um
M (k)
5

---

Under review as a conference paper at ICLR 2022
Even though the presentation in this section focuses the binary weights, the scheme can be nat- urally extended to quantized neural networks of more discrete levels. We will briefly discuss the implementation for ternary weights in Section 6
5 ANALYSIS OF ALGORITHM
In this section, we present the theoretical analysis VedVote when local data are independent and identically distributed (i.i.d.). The empirical results in the non-i.idd setting will be discussed in Section 6 and the corresponding analyses are left for future work. We use the gradient norm expectation an indicator of convergence, which is commonly adopted in nonconvex optimization 2021). To simplify the notation, we first literature (Reisizadeh et al. 2020 Haddadpour et al.
denote the stochastic local gradient by g(h.1) Wn ((p (E.2)
Sm <lhit)). The local true gradient and (nf(((h(()) respectively. In addition, let (/h) A w(k.r) w(lh.)) denote the error introduced by stochastic rounding. According (S
global true gradient will be denoted by gm
(k.c) A Eg 9 m
(k.r) g
to the unbiased property of stochastic rounding, we have T [[()]
O. With the aforementioned
notations, we state five assumptions for the convergence analysis.
5.1 ASSUMPTIONS
Assumption (Lower bound) V E Rd, w E (-1,1)4, the objective function is lower bounded by a constant f", i.e., [(W) > l" minneR" (()())
Assumption 2 (L-smoothness) A WI, W2 E (-1,1)) m E negative L such that fm (W1)
there exists some non-
We)lla < L [| W2 12
Assumptions to 2 are common for necessary analyses (Wang & Joshi 2018). We limit the range of the normalized weight w while in a typical setting there is no restriction to the model weight. Assumption 3 The normalization function y IR + (-1, is strictly increasing. In particular, (k.C)
assume its first derivative is bounded for all m,s Le., an (h.))) [c1, where 0i, 02 positive parameters independent of k. t, m, and
Assumption 3 is not difficult to satisfy in practice. For example, let (ph) = ranh(ah), we have (h) = a tanh² tanh" with c2 = a. Note that & quickly saturates with a large h in the local updating. On the other hand, the empirical Beroulli parameter p. will be clipped for stability, which indicates that (8.0)) will be upper bounded by certain hg- In this sense, we have e =
m,
[1 - tanh" The next two assumptions bound the variance of the stochastic gradient and quantization noise.
Assumption The stochastic gradient has bounded variance, iee, EE g g g & o? where of is fixe variance independent of k. t and m.
(k.4)
Assumption 5 The quantization error c(k) has bounded variance, i.e. El ( 1|2 < of where of is a fixed variance independent m..
Note that quantization error is affected by the quantizer type and the corresponding input. For example, if the normalization function &p approximates the sign function very well, the stochastic quantization error will be close to zero. Formally, the upper bound of can be viewed as a function of input dimension d, which formulate in the following lemma. The proof is in Appendix D.3 Lemma 3 Suppose we have an input a (-1,1)d for the quantizer Que defined f). then the quantization error satisfies EE [1)))(a) a
d ||al12
For existing algorithms quantizing the model update 5(h) ((4) (k.rr the quantizer has the property E [[(((x) x x||21x < g g||x||2= With a fixed quantization step, q increases when the input
dimension d increases (Basu et al. 2020 We state the result for widely-used quantizer, QSGD Alistarh et al. 2017), which has been adopted in FedPAQ, in the following lemma.
Lemma 4 Suppose we have an imput E Rd for the QSGD quantizer Q. In the coarse quantization
scenario, the quantization error satisfies E [1((x) - x12 = =0 =0(d |xx|2

---

(k.7) follow the symmetric Under review as a conference paper at ICLR 2022
5.2 CONVERGENCE ANALYSIS
We state the convergence results in the following theorem. The proof can be found in Appendix D.5
Theorem 1 For FedVote under Assumptions I too after K rounds of communication, we have
let the learning rate ll O
then
LtvK
1 K-1
2 [ \/
f(w))]
1 M
2 LI - 1)
Σ c
+ +2gL1
0
K k=0
L K-1
2(c -c
K-1
ok
R(K)
(15)
MTKM
TMK
where R(hh)
Σ E (V V
and (k.0) A {ir 1g
(k) (k.()
9 gm, 0}
Remark When there is no normalization function and quantization, iee, so(x) = x with c1 =
22 = o = Theorem recovers the result obtained in Wang Joshi 2018
To discuss the impact of quantization error, con- sider the distribution of different inputs. For the model update _(h) we expect the central limit theorem to render its distribution shape, where each entry g(h)) follows the Gaussian distribu- m,²
(a)
(b)
tion. For the Bernoulli probability Ti (k.T), we ex- pect the Beta distribution the conjugate prior to render its distribution shape, where each entry (A,r) follows the symmetric Beta distribution. Tm.
Figure 3: Histograms of (a) model updates (
and (b) binary weight probabilities (k.r) We trained a LeNet on MNIST for a single commu- nication round.
See F for the empirical results.
Remark 2 Following the analysis framework in Theorem 7 the order-wise convergence rate is R EKOO LE [ (w(t)))l = + where E(d) is the error introduced by the quantiza- tion. For FedVote with the normalized weight w Wm (k.r) as the input, when x m.
Beta distribution, it can be shown that E| ( =0 (d) based on Lemma For algorithms such as FedPAQ with the model update ((k) as the imput, when ('t)) 's follow the Gaussian distribution, it can be shown that TE (((()((()))) 5 m d is sufficiently large, FedVote converges faster.
O (d/22 based on Lemma When the weight dimension
The value of the positive scalar error term (k) in (15) depends the gradient dissim- ilarity. If the angle between the local gradient V fm ( (k.t)) and the global gradient ((((k)) is not large, (M) can be treated as a bounded variable.
Remark 3
Remark 4 The choice of nonlinear function Rd + (-1,1)² will affect the convergence. If sp behaves more like the sign(.) function, e.g., when a increases in tanh(ax), the quantization error will be reduced. In other words, we expect smaller of according to Lemma 3 which leads to tighter bound in 75). Meanwhile, a larger 02 will negatively influence the convergence.
6 EXPERIMENTAL. RESULTS RESULLS
Data and Models. We choose image classification datasets Fashion-MNIST (Xiao et al., 2017)
and CIFAR-I0 (Krizhevsky) 2009). Both of them have a total C 10 classes. We consider two data partition strategies: (i) i.i.d. setting where the whole dataset is randomly shuffled and assigned to each worker without overlap; (ii) non-i.i.d. setting where we follow Hsu et al. (2019) and use the Dirichlet distribution simulate the heterogeneity. In particular, for the mith worker we draw
dom vector 4m. ~ Dir(a), where 4,, = [qm.,, ... 4m,c] c belongs to the standard (C - 11) -i-mimplex. We then assign data samples from different classes to the mith worker following the distribution of
7

---

Under review as a conference paper at ICLR 2022
0.7
Falles
Fedii
FuPA0
FwPMM)
6.7
4g550D
40050
Todlrg
40
04
(a)
(h)
(C)
Figure 4: Learning curves of different methods on CIFAR-10 with (a) the i.i.d. setting and (b) the Dirichlet non-i.id. setting. Compared with the gradient quantization methods such as signSGD [Bernstein et al. 2018) and the model update quantization methods such as FedPAQ (Reisizadeh) al.) 2020), Fed Vote achieves higher accuracy given the same number of communication rounds. (c) Test accuracy versus accumulative uplink communication cost on the i.i.d. CIFAR dataset. Fed- Vote achieves the best accuracy given the transmitted data size.
Table 1: Test Accuracy in the Byzantine Setting
Table 2: Effect of the Normalization Function
Distri-
sign- SGD
Co- Med
Pro- posed
Fashion- MNIST
a
Dataset
bution
0.5
1.5
2.5
10
Fashion- i.i.d.
61.5%
77.7%
91.4%
float binary
90.7%
90.6%
90.0%
88.2%
i..d.
MNIST non-i.id
61.0%
73.4%
89.4%
88.7%
90.1%
89.9%
88.2%
CIFAR- i.idd. 13.5%
29.3%
76.6%
non-
float
87.3%
86.9%
85.7%
85.0%
non-ii.d 11.0%
28.7%
72.0%
i.i.d.
binary
83.3%
85.5%
85.2%
84.6%
mm We set 0.5 unless noted otherwise. We use LeNet-5 architecture for Fashion-MNIST and a VGG-7 architecture for CIFAR-10. Results are obtained over three repetitions.
Implementation Details. We provide implementation details in the proposed Ved design. First, following prior works (Shayer al. 2018 Gong et al., 2019). we keep the weights of the BNN final layer as dooting-pooit values for the sake of the model performance. The weights of the final layer are randomly initialized with a shared seed and will be fixed during the training process. Second, we notice that for quantized neural networks, the batch normalization (BN) (loffe & Szegedy, (2055) after the convolutional layer necessary to scale the activation. We use the static BN without learnable parameters and local statistics (Diao et al., (021) ensure the voting aggregation of binary weights. For the normalization function, we choose (rxx) = tanh(3x/2 unless noted otherwise. More details of the experimental setup can be found Appendix C.T
Communication Efficiency and Convergence Rate. In this experiment, we consider M = 31
workers with full participation and compare FedVote different methods within N munication rounds. The results of partial participation can be found in Appendix C.3 The com- munication cost is calculated as the accumulative uplink message size from all workers. Figure reveals that FedVote outperforms the siafienntquantizattio stein al. 2018) that quantizes gradients bit signs, and FedPAQ (Reisizadeh et al. 2020) that quantizes the updates to 2 bits integers. Compared with FedPAQ, signSGD, and FedAvg, Vet improves the test accuracy by 5-10%, 15-20%, and 25-30%, respectively, given the fixed commu- nication costs of 1.5-4.7 GB.
100 com-
methods such as signSGD (Ber-
Byzantine Resilience.
This experiment validates the effectiveness of Byzantine-FedVel We consider omniscient attackers who can access the datasets of normal workers and send the opposite of the aggregated results to the server. The number of attackers 15, and the remaining 16 clients are normal workers. We compare the proposed method with coordinate- wise median based (CoMed) gradient descent (Yin et al., 2018) and signSGD (Bernstein et al., 2018), and report the testing accuracy after 100 communication rounds. We do not compare with FedAvg and FedPAQ, they are fragile to Byzantine failure. The results are shown in Table can be observed that Byzantine- VedVote exhibits much better resilience Byzantine attacks with close to half adversaries.
8

---

Under review as a conference paper at ICLR 2022
Table 3: Test Accuracy of TNN and BNN
Table Forward Pass Efficiency
Distri- bution
BNN
TNN
Neural
Weight Type
Adds
Muls
Energy (mJ)
Dataset
Net
Fashion- i.i.d.
91.1%
91.9%
float
1.7x10
1.8 x 10
8.1 1.5
LeNet-5
MNIST
non-iidd
88.3%
89.4%
binary
1.7x10
1.0x 10
CIFAR- i.i.d.
80.5%
82.5%
float 4.8x10t0
10'x
242.9
VGG-7
10
non-i.i.
74.6%
77.6%
binary
4.8
20 43.3
Normalization Function. From Remark we know that the normalization function influence the model convergence. We empirically examine the impact in this experiment. For normalization function (ar) = tanh we choose from (0.5, 1.5, 2.5, 10). We test the model accuracy after 20 communication rounds on Fashion-MNIST. The results are shown in Table [ As a increases, the linear region of the normalization function shrinks, and the algorithm converges slower due to larger c2. On the other hand, the gap between the model with normalized weight w and the one with binary weight w also decreases due smaller quantization errors. A good choice of the normalization function should take this trade-off into consideration.
Ternary Neural Network Extension. In the previous sections, we focus on the BNNs. We ex- tend Ved to ternary neural networks (TNNs) and empirically verify its performance. Training and transmitting the categorical distribution parameters of the ternary weight may bring additional communication and computation cost to edge devices, we therefore simplify the procedure as fol-
(k.t)) lows. For each ternary weight w Wm, we still keep latent parameter h (k.4) to optimize. After
(()(()))) and obtain quantized weight wm (k.,T) At the aggregation stage on the server, instead of calculating the vote dis- tribution, we directly compute the global normalized weight as W (k+1)
local steps, we use the stochastic rounding to the normalized weight Wm (k,7) phh
J >==1 (k.T)) More As TNNs can fur- ther reduce the quantization error, their performance is better than the BNNs at the cost of additional 1 bit/dimension communication overhead.
details can be found in Appendix C.4 The training results are shown in Table 3
Deployment Efficiency. We highlight the advantages of BNNs during deployment edge de- vices. In Vedeo we intend to deploy lightweight quantized neural networks on the workers after the training procedure. BNNs require 32 smaller memory size, which can save storage and en- ergy consumption for memory access (Hubara et al. 2016). As we do not quantize the activations, the advantage of BNNs inference mainly lies in the replacement of multiplications by summations. Consider the matrix multiplication in a neural network with an input x E IR and output y E Rda;
= WT x. For a floating-point weight matrix W E Rdixds, the number of multiplications di d2. whereas for a binary matrix Wi, E DDdixda all multiplication operations can be replaced by additions. We investigate the number of real multiplications and additions in the forward pass of different mod- els and present the results in Table We use the CIFAR- --0 dataset and set the batch size to 100. As to the energy consumption calculation, use 3.7 pJ and 0.9 pJ in Hubara al. 2016 for each floating-pon point multiplication and addition, respectively.
7 CONCLUSION
In this work, we have proposed FedVote to jointly optimize communication overhead, learning re- liability, and deployment efficiency. In FedVote, the server aggregates neural networks with bi- nary/ternary weights via voting. We have verified that FedVote can achieve good model accuracy even coarse quantization settings. Compared with gradient quantization, model quantization is a more effective design that achieves better trade-off's between communication efficiency and model accuracy. With the voting-bases based aggregation mechanism, FedVote enjoys the flexibility to incorpo- rate various voting protocols to increase the resilience against Byzantine attacks. We have demon- strated that Byzantine- Fedeee-Feoooor Vote exhibits much better Byzantine resilience in the presence of close to half attackers compared to the existing algorithms.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie.
QSGD:
Communication-ellccient SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems, pp. 1709-1720, 2017.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N Diggavi. Qsparse-local-sgd: Distributed sgd with quantization, sparsification, and local computations. IEEE Journal on Selected Areas in Information Theory, 1(1):217-226, 2020.
Ahmed Bendahmane, Mohamed Essaaidi, Ahmed El Moussaoui, and Ali Younes. The effectiveness of reputation baaed voting for collusion tolerance in large-scale grids. IEEE Transactions on Dependable and Secure Computing, 12(6):665-674, 2014.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. signSGD: Compressed optimisation for non-convex problems. In International Conference on Machine Learning. 2018.
Peva Blanchard, Rachid Guerraoui, Julien Stainer, et al. Machine learning with adversaries: Byzan- tine tolerant gradient descent. In Advances in Neural Information Processing Systems, 2017.
Xiangyi Chen, Tiancong Chen, Haoran Sun, Steven Z. Wu, and Mingyi Hong. Distributed training with heterogeneous data: Bridging median- and mean-based algorithms. In Neural Information Processing Systems, 2020.
Enmao Diao, Jie Ding, and Vahid Tarokh. Heterofl: Computation and communication efficient
federated learning for heterogeneous clients. In International Conference Learning Represen- tutions, 2021.
Ruihao Gong, Xianglong Liu, Shenghu Jiang, Tianxiang Li, Peng Hu, Jiazhen Lin, Fengwei Yu, and Junjie Yan. Differentiable soft quantization: Bridging full-precision and low-bit neural networks. In International Conference on Computer Vision, 2019.
Rafael C. Gonzalez and Richard E. Woods. Digital Image Processing 3rd Edition. 2014.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Feder- ated learning with compression: Unified analysis and sharp guarantees. In International Confer- ence on Artificial Intelligence and Statistics, 2021.
Lu Hou, Ruiliang Zhang, and James Kwok. Analysis of quantized models. In International Conference on Learning Representations, 2019.
Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint urXiv:1909.06333 2019.
Itay Hubara, Matthiuu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:1502.03167, 2015.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for feder- ated learning with theoretical guarantees. arXiv preprint 2xXxx:0002.10940 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning. Foundations and Trends in Machine Learning, 14(1), 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Master thesis, Dept. of Comput. Sci., Univ. of Toronto, Toronto, Canada, 2009.
Shuai Li, Ce Zhu, Yanbo Gao, Yimin Zhou, Frédéric Dufaux, and Ming- Ting Sun. Lagrangian multi- plier adaptation for iate-distortoon optimization with inter-frami dependency. IEEE Transactions Circuits and Systems for Video Technology, 26(1):117-122) 2015.
10

---

Under review as a conference paper at ICLR 2022
Tao Lin, Lingjing Kong, Sebastian U Stich, and Martin Jaggi. Ensemble distillation for robust model fusion in federated learning. Advances in Neural Information Processing Systems, 2020.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communicaionn-fficien learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, pp. 1273-1282, 2017.
Luis Munoz-GGnzálee Kenneth T Co, and Emil C Lupu. Byzantine-robust federated machine learn- 2019.
ing through adaptive model averaging. arXiv preprint
Haotong Qin, Ruihao Gong, Xianglong Liu, Xiao Bai, Jingkuan Song, and Nicu Sebe. Binary neural networks: A survey. Pattern Recognition, pp. 107281, 2020a.
Qiaofeng Qin, Konstantinos Poularakis, Kin K Leung, and Leandros Tassiulas. Line-speed and seal- able intrusion detection at the network edge via federated learning. In International Federation for Information Processing Networking Conference, 2020b.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication-effiienn federated learning method with periodic averaging and quan- tization. International Conference on Artificial Intelligence and Statistics, 2020.
Mher Safaryan and Peter Richtarik. Stochastic sign descent methods: New algorithms and better theory. In International Conference on Machine Learning, 2021.
Felix Sattler, Klaus-Robert Müller, Thomas Wiegand, and Wojeiech Samek. On the byzantine bustness of clustered federated learning. In International Conference on Acoustics, Speech and Signal Processing, 2020.
Oran Shayer, Dan Levi, and Ethan Fetaya. Learning discrete weights using the local reparameteri- zation trick. In International Conference Learning Representations, 2018.
Nguyen H Tran, Wei Bao, Albert Zomaya, Minh NH Nguyen, and Choong Seon Hong. Feder- ated learning over wireless networks: Optimization model design and analysis. In International Conference Computer Communications, 2019.
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-fffiiee SGD algorithms. arXiv preprint 10XX::1800007766 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv: 1708.07747 2017.
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-rou robust distributed learning: Towards optimal statistical rates. In International Conference Machine Learning, 2018.
Zhi-Hun Hua Zhou. Ensemble methods: foundations and algorithms. Chapman and Hal//CRC, 2019.

---

Under review as a conference paper at ICLR 2022
A VOTING METHODS
We review the definitions of several voting methods (Zhou 2019). Suppose we have set of M individual voters and candidate output labels {vi,,... WC J. For the mith voter, it will output result Um = [1m,11, ...,!!!!! Here, the ith entry Um, E {0, }. which takes the value one if the voter chooses the candidate a) and zero otherwise.
Majority vote requires the winner to receive more than half of the votes; if none of the candidates receives more than half of the votes, rejection option will be given. The majority vote result can be written
M
C M
V majority
if
Um,
2
Um.ji
(16)
m==1
j=1 m==1
rejection, otherwise.
Plurality vote takes the class label that receives the largest number of votes as the final winner, i.e.,
U plurality
V argmax > AM
(17)
In the binary case with C. 2, plurality vote resembles majority vote except that it does not have a rejection option. If more than two candidates receive the same number of votes, randomly select one of them as the final results. Weighted vote assigns different weights for voters and the result can be written
v weighted v Vargmaxx Im- Am P
(18)
where Am is the weight assigned to the math voter. In contrast to the aforementioned vote methods, soft vote produces the probability output. The probability that the ith candidate wins is calculated as
P(V soft = thx)= =
1 M
Σ
Um
(19)
B FEDVOTE ALGORITHM
We summarize the proposed FedV method and its Byzantine-resilien variant in Algorithm When there no attackers involved, Option I. When we require the resilience against Byzantine failure, we choose Option II.
I
C SETUP AND ADDITIONAL EXPERIMENTS
C.I HYPERPARAMETERS
For the clipping thresholds, we set Pmin 0.001 and Pmax 11- Pmin- The thresholds are introduced for numerical stability and have little impact on performance. We use 3 = 0.5 in Byzantine- Fed The choice of the smoothing factor has little impact on the final test accuracy, as the credibility score decays exponentially for adversaries over multiple communication rounds. We use the Adam optimizer and search using the learning rate 77 over the set (10-1, 3 10-1, 10-3 3 10-3 10-2 3x 10 10-2, 1,1011,1 3 x 10-1]. We set the number of local iterations 7 to 40 and the local batch size to 100.
C.2 COMPARISON OF VANILLA VET AND BYZANTINE-PEEDVOTE
Lemma 2 shows that FedVote is related to FedAvg in expectation. Adversaries sending the opposite results will negatively affect the estimation of the weight distribution and impede the convergence in multiple rounds. We compare the test accuracy of Byzantine-FedVort Vanilla FedVote, and signSGD on the non-i.i.d CIFAR-10 dataset (a = 0.5) with various numbers omniscient attack- 6 reveals that the test accuracy of Vanilla FedVote drops severely when the number of adversaries Increases, which is consistent with our analysis. In contrast, the drop of accuracy in Byzantine-Fed Vote is negligible, confirming its resilience omniscient attackers.
ers. Figure
12

---

Under review as a conference paper at ICLR 2022
Algorithm 1: Hinary-Weight Ved with/without Byzantine Tolerance
initialize (0) and broadcast
for 1, .. do
on m worker: receive (A) from the server
initialize latent weight h (k.D)
(2p((k) 1)
for = 0: do
9 (k.d) = (n (h:))))) Sm )
h hm (k.141) (8.10 (k gm (k.t)
-(.TT) ((h (1.7))
Wm (k,T) = sloudiin Wm (k.tt)
10
D Eq.
(k,r) to server
11
send Wm
12
on server:
(w(1) p ( vote( ro (K5F) 1
13
/m=1)
broadcast p ((++1) to workers
function vote( Wm mmmi)
(k,7) M
15
16
for i 1: d do 1)++) sign
M (k:T)
17
Wi
Σ Wmmi
M
P.
(++1)
M Σ
(1(k))) mii
=1)
Option
18
M
19
P;
1k+
Σ
Am
(k,r)
Option II
m==1
return [w(h+1) ()+ to the server
0.7
0.6
0.70
Tex: Accurayr
Text Accuraty
0.5
0.65
0.4
0.60
FedAvg
0.3
FedVode
0.55
RyzeriiceFaadooe
0.2
FedPAQ
Vanilla FedVots
FigrSGD
sigrSGD
0.1
0.45
20
40
60
80
100
Commmncation Round
Number Ryzzerine Workess
Figure 5: Test accuracy versus communication round of different methods on the non-i.i.d. CI- FAR dataset (a = 0.5). We use 100 workers and sample 20 of them in each round.
Figure 6: Test accuracy versus the number of Byzantine workers. As the number of adver- saries increases, the test accuracy of Fed drops rapidly.
C.3 CONVERGENCE FEDVOTE WITH PARTIAL PARTICIPATION
We increase the number of workers to 100 and sample 20 of them in each communication round.
We compare FedVote with FedAvg McMahan et al. (017). FedPAQ (Reisizadeh et al. 2020). and signSGD (Bernstein al. 2018) in Figure the non-i.id. CIFAR- 10 dataset (a 0.5) without changing other experimental setups. The observation is consistent with the results Figure
FedVote outperforms gradient quantization methods such FedPAQ and signSGD.
13

---

Under review as a conference paper at ICLR 2022
C.4
EXTENSION TO TERNARY NEURAL NETWORKS
The stochastic rounding used in the ternary neural networks, W; = Qar ()) (i) an extension of 11
+1, with probability м1 = ú; [(W; > 0),
01
with probability 22 -i [ < 0),
(20)
0,
with probability 1 1 (#1 + #2).
One can modify the normalization function to optimize neural networks with multiple quantization levels. For example, consider quaternary weight Wy E {-2, -1, 1, 1,2,, the normalization function (p(x) can be modified to (xx) tanh(az).
C.5 BATCH NORMALIZATION IN FEDVOTE
Below review the commonly-adopted BN function for convenience of presentation. For dimensional input x(5) from the current batch B (x()),...,x('))) the output of BN layer is formulated as
(m))),,
x11) 11
y a BNN.6Zz0)) =9 v +
+ b,
(21)
where 7, are learnable affine transformation parameters, and μ4, o² are the mean and variance calculated over the batch samples. Note that the normal BN layer will introduce the real-valued pa- rameters and track the statistics of the input, all of which may cause problems when being binarized VedVote. Therefore, we choose to set parameter-free static BN, i.e.
EB x (i))
y' BN(x(0)) r
(22)
Varg [r()]] +
D MISSING PROOFS
D.1 PROOF OF LEMMA I
Lemma 1 (One-Shot FedVote) Let w TVd be the optimal solution defined in 8 For the rath
worker, Em,i - PP( (k.7) + wu) denotes the ervor probability of the voting result of the ith coordi- m.
M nate. Suppose the error events m, + w 1m=1 are mutually independent, and the mean error
probability 8; = M4 EM=1 Em, smaller than 1/2. For the voted weight (k++), we have
IP w (k+1)
+ ww)) < [2s; exp(1 25;))
(23)
(Kir) - fw?) w following Bernoulli distribution with parameter Em,i- Let Proof. Let Xm. A (win
Yi- EM Xm.is have
m! (b+1) # ww²) = P V, 2
(24)
14

---

Under review as a conference paper at ICLR 2022
With independent vote results from workers, Y, follows Poisson binomial distribution with mean My; Em=1 6,, V a >> 0, the Chernoff bound be derived as
M
(25a)
P(c
2
(25b)
aM
exp
E
[
(25c)
2
a.
exp
m
em,t)
(25d)
2
M
a.M
exp
In (1 + Emi(e" 1))
(25c)
2
m=1
M
aM
exp
Em,(e" - 1))
(25f)
2
m=1
where ① is based on Markov's inequality. @ holds due to In(1 + x) & x for all x E (o),
By assumption we have j.y;
< 2
Let = In 2ny,
we have
M
exp Jyy;
M 2
IP
Y 3
(26a)
M
2uy;
2
2py;
exp
1
(26b)
M
M
Let 8;
PY; M
EmEn Em,i and substitute it into (6b)), the proof is complete.
M
D.2 PROOF OF LEMMA 2
Lemma 2 (Relationship with FedAvg) For the normalized weights. FedVote recovers FedAvg in
expectation: IE [ (k+1)]
Σ w(kir) (k,r) where ((+11) (p (1+1)) and with (k.7) (hhh)))))
Proof. From the inverse normalization in 14). we have (k+ = 2p - Recall the definition
of the empirical Bernoulli parameter (k+T)
given by 13 have the elementwise expectation
E
2P 2P (w = 1))
(27a)
M
(h
(27b)
M
m=1
where follows from stochastic rounding defined in Based on the definition of range normal-
ization in (10), for local normalized weight we have w m, 27bb we have
(h (k.T)) Substituting the result into
E w((++2)
1
(k.r) m=1
Σ
(28)
M
which completes the proof.
D.3 PROOF OF LEMMA 3
Lemma' 3 Suppose we have an input a E (-1,1)d for the quantizer Qor defined in
11 then the
quantization error satisfies E (a) - = d - ||a
15

---

Under review as a conference paper at ICLR 2022
Proof. Let â a Qac(a), we have
d
E [| 130)-a00 -al2iaa
=
Σ (a: a:)
(29a)
[ [ a] -7
(29b)
=1
Σ (1 at))
(29c)
d
|
(29d)
The proof is complete.
D.4 PROOF OF LEMMA 4
Lemma Suppose we have an input x E Rdd for the QSGD quantizer Q. In the coarse quantization
scenario, the quantization error satisfies E [|[((x) x1| = 0 d |
Proof. Consider a QSGD quantizer (Alistarh et al. 2017) with 1. For detailed results of other quantizers, we refer readers to Basu al. (202)).
In particular, we have
Qayga (xt) = ||x[|2 sgn (a:) (i(x, s),
(30)
where
0
with prob.
|xc
(x(x,)) 1 with prob.
x
(31)
|zc]_
1xx|="
The variance of quantization error is
[1((x)) - -x|13x]
Σ (#: - xz:)2 xx
(32a)
E
5 xx] -x²²)
(32b)
[0%]|
|x|
||x1
(32c)
x 2
||*||||||||
||
(32d)
(vd 1) 12
(32e)
which completes the proof.
D.5 PROOF OF THEOREM 1
We first introduce some notations for simplicity. Let (k) denote the difference between two suc- cessive global latent weights, i.e.,
(k+1)
(33)
(k,t) to denote the stochastic gradient noise, i.c.,
We use
(kitt) A (k,t)
g
(k.1)
(34)
Finally, we (f( denote the gradient with respect to w. The following five lemmas are pre- sented to facilitate the proof.
16

---

Under review as a conference paper at ICLR 2022
Lemma 5
The global normalized weight w()) can be reconstructed as the average of local binary weight, i.e,
((++1)
1 M
Σ
w
(35)
Proof. See Appendix D.6
Lemma 6 (Lipschitz continuity) Under Assumption 3 V Ti, 42 R. we have
1<p(11) (0(x22) < 02 02 rzl.
(36)
Proof. Without loss of generality, suppose 21 22 Based on the mean value theorem, there exists some (21, such that
(c(c)= (x(22) (2()))
(37)
32 I1
For the monotonically increasing function ip, we have
(x²) - ip (x1) ('(c) (x2 x1
(38a)
02 (22 x1)
(38b)
where ① holds due to Assumption 3 The similar result can be obtained by assuming 22
T1.
which completes the proof.
Lemma 7 (Bounded weight divergence) Under Assumption have
(k,r) m
T
Σ Elg
1 + 0²
(39)
Proof. See Appendix D.7
Lemma 8 Under Assumptions
we have
E
(V)W (0)
(
(40)
2
cîn
M
+
(2
E
1
(k:t)
11
4M
m= 1=1
(T
nlc2 dt)
0²
R
(41)
M
where Rilk)
Σ E (V and (k.0) 4 {i
g
(k) (k.0)
g
gm.s
of.
Proof. See Appendix D.8
Lemma (Bounded global weight difference) Under Assumptions 100
we have
B
B
(c27) T
M
M
g
m
(k.t)
1
(c2n)
M
0²
+
M
1
ok.
(42)
m=1
1=0
Proof. See Appendix D.9
17

---

Under review as a conference paper at ICLR 2022
Theorem 1 For FedVote under Assumptions to if the learning let the learning rate n
1
then after K rounds of communication, we have
LTVK)
K-1
- -
GLAl(T - 1)
Σ
+ 22L
+
oe
K 0=0
mTK
M
2
L
Σ o
2(c3 -c9)
K-1
R
(43)
KT
TMK
m=1
where Rih!
Σ
(V ) and Iin-.t)
/ 9
(K) (h.t)
9
Im.
0).
Proof. Consider the difference vector A (k) defined in 33 expand it as
A (k) w (h)
w
(1+11
(44a)
((h)
Σ w
(k.7)
(44b)
M
M
M
(k)
(k.r)
1
(tr)
(44c)
M
M
m=1
m=1
where @ follows from (35 and @ holds by substituting the definition of quantization error.
From Assumption
we have
[(Wlk+2)) - s(w(k)) < - (V)(((())) A A(t)) + 2 1
L
(45a)
Let (Ln))((F-1)
+ Lag < ./.
take the expectation on both sides, and use Lemmas
2
E
[(w((+2))
[(w(()))] < 6-2 2
R V
[
(1)) 1|2
(0102)p11
(2
-T - 1) - 2.yr
M
4M
m=1 1=0
(L
2
+
CGLn(TT 1 0² +
n1 ci)
M
R2())
+
L
(46a)
4
M
M
2M
m=1
ciPT
(02m) LT
(
2
L - -1) o²
E
+
M
(c3
of)
M
R(K)
o
(46b)
M
2M
where ① follows from the restrictions on learning rate. We rewrite the restriction
+
L2T +
21-
7
17
12
(47a)
1+ v 1
20
of
(47b)
L(r 1)
(47c)
L(T 1)22
where in ① we use 7(T - 1) < 7,, and @ holds due to the Bernoull inequality (1 + 2)
1+ fr, V e (-), Based on 47c we set the learning rate O ((@)
Summing
LTVK
18

---

Under review as a conference paper at ICLR 2022
up K communication rounds yields
K-1 Σ
<
2
1
&
GIn((T 1)
+
+
K k=0
mTK
M
L
K-1 1
2(c3 c7)
K-1 M
ok
(k)
(48a)
T
M
TMK
k=0
k=0 m=1
D.6 PROOF OF LEMMA 5
Proof. From the reconstruction rule (4). we have
w (k+1) (k+11
(49)
The ith entry of (k) is defined in as:
M
Σ
I
(K,T)
=1)
(50)
M
m=1
Substituting (50) into (49 yields
wi
(k+1)
1)
1
Σ
21
(kir)
=1) -1 1]
(51)
M
Note that
(k,7) +1,
(k.r)
=1) 1
+1, Wm
21
Wm,s
(k,7) 11,
(52)
1, Wm
we have
M
(k+1) W
(k)
w
(53)
M
which completes the proof.
D.7 PROOF OF LEMMA 7
Proof. With the local initialization and update method described in Algorithm ! we have
(K.T) m
B
(1
(k:)))
- 40 (h
(k.0) || h (k.0) 2
(54a)
(k.T)
(54b)
m
o3
9 ()
(54c)
(E
(k,tt
+
(k.tt)
(54d)
m
1=0
= =c22)²
Σ ())
+E
(k.()
(54e)
m
1=
0
< 3
E
11
(k.0)
+ of
(54l
where @ comes from the Lipschitz condition in Lemma 6
19

---

Under review as a conference paper at ICLR 2022
D.8 PROOF OF LEMMA
Proof. We have
V
(V(((())
M
M
E
(())
W m
(
(R)
(55a)
M
M
m
m=1
m=1
M
B
(()
(k,r)
(55b)
M
m=1
=
V
1
Σ
c(h (ki)
(h (1-)))
(55c)
M
Based the mean value theorem, for h ((6))) E R, there
where ① follows from Assumption
exists some (k)
m,
H H such that
(p((1))) (K:T))
(K)
(56)
1
(KiTT)
where H() an open interval with endpoints h1 and (hiT))
H+r) {
(1) (im
(B:7)) if i (K)
(1.))) (K.T)
(57)
(h (k.r)) (10) otherwise.
Let Clt) diag (c((c.)))) 1, ..... of ((((()))) (c) we have
(k) - ((((tt))) = ((() (h ((e))))) = ((R)
Σ
ghh
(k.t) + el(.t)
(58)
Substituting (58 into 55c
yields
M Σ
(K)
E
()((W))),
c. g (k.e)
(59)
M m=1
t=
(k.t)
According to the chain rule, gm
can be written as
glh (k.t)
Vnfm(pp(h (k.t) = ((k.t) V fm (W((k.)))
(60)
where (( diag
de
de To simplify the notations, let (k,4)
((k) (k.1)
Note that (kk.)) is still a diagonal matrix, where the ith diagonal element & (k:0) is
m,,
(k.t) A (B(k.)) = dep dip m,i
(61)
de dh (k.4)
Substituting (60) into (59) we have
M
E VV (k)
7
E
()(((()) B(k.)) V V. (am (wll))))
(62)
M
m=1
1=0
We first focus on the following inner product:
(V)(W())), Blk!)) V Fm((w(ii)
(w(k))))
Σ (V)(W x (k.11
(Vfma (w(t:))))s
(63)
20

---

Under review as a conference paper at ICLR 2022
where (Vf), denotes the ith entry of the gradient vector. Consider index set (((..) defined
I(kat) a E (1.....,d)) d} (VI( ()) (wlh:))); > 0].
(64)
Since the sign of written as
(k) (k.t) the index set I((::) can also be (w(W is equal to gj
Ikk00) ft.... df g: Im. > 20.
(k) (k.))
(65)
The result in (63) can be bounded as
V Blktt V fm wilh-1))
(66a)
(V]( ()) (v fm (
+ 0
Σ
(V ( (m((!h-))))
(g
(66b)
= c (V/(W(()), V. (m + -c3-c0 -t)
Σ E (V]((()))) V V. f5 (w!!
(66c)
where follows from Assumption gradient divergence, namely,
To simplify the notation, let R!l denote the accumulative
R
Σ
E
(67)
The expected inner product in 62 can be bounded as
E V
(K)),
A 1R0)
M
(W(ha))) 17(22 - of) M
M Σ
(8)),
((K)
(68a)
M
m=1
?
2M
nc3 - cf)
- E
V (f(
R(k)
(68b)
M
2 1Ip
M
[ (1)
ΣΣ
(k.t))
11
2M
m=1
(2Bl/W(t.0) - 11))
of)
M
(())
(68c)
M
m=
where ① follows from aaa b) ||al12 + ||b|1 2
||a
bll and @ holds due to Assumption
From Lemmal) 7 we can show that
(k.1) m
(t
Σ L (k,
|| + +02
(69)
21

---

Under review as a conference paper at ICLR 2022
where t 1, ..... 1. Substituting 669 in 68cc) yields
E
V / (K)), A 166))
Gi
M
E
V s(
(1)
11
w
1 ||
2
2M
m- 0=0
11
Σ
Σ
(T(T 1)
n(n 1)) B
9m (k 11
4M
(T
1)
nlc3 c
R
(70a)
M
m=1
Gn
M
B V/
112
W
(k.1)
11
2
2M
m
M Σ
(902)))77((-
1
B E
(k.0)
4M
m
m= 1=0
(1 1)
n[c3 ot
R(b)
(70b)
M
GU B.
| (8)
11
(2
Σ
Σ
Bllg
R
11
4M
m=1
1=0
(1022L)2)"T(T
n - c
M
4 0.
Σ
(())
(70c)
M
Y72
where follows from T(T - 1) - nnn + 1) & T(T - 1), and holds due to the chain rule in (60) and Assumption 3
D.9 PROOF OF LEMMA 9
Proof. We have
M
A (1) 11 E (A))
(k)
(k,7)
+
1
(k)
(71a)
M
m
M
m
m==
m==1
M
M
E
( (k))
(ho (k.rr)
+
1
(k)
(71b)
M m=l
M
m
M
M
= E
Σ
+
(1)
M
M
m==1
m=
1 M
M
2E
(K:T) ) (1e s0 (fo((tt)))
(t)
(71c)
M
M
m
m=1
M
M
E
(h)
5 (1s (RIT))
+ E
(k)
(71d)
M
M
112
m=
22

---

Under review as a conference paper at ICLR 2022
where @ comes from Assumption
5
For the first term in (7ld we have
M
E
1
(p(1) - (0 (A.T))
M
m=1
110(1(())
(p (K6TT) mm
2
(72a)
M
(1)
10 11
(72b)
M
m=1
(c21)
M
9m
(k,tt)
(72c)
M
(c21)
M
(h.
(k.)0)
(72d)
M
(
T
M
(o2n) 2T
(k.e) m
0.
(72c)
M
M
m=1
where due to Lemma and @ comes from
For the second term in (7dd) we have
M
E
k
(73)
2
Combing the results of 72e and 73
completes the proof.
23


Reviews:
[{"review_id": "nLbLycWa_Yf", "reviewer": "Reviewer_Cpmm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Pros**:\n- The paper is well-written and related works are well-address to my knowledge.\n- Has a nice introduction on quantized neural networks, which is good for readers that are not familiar with the topic.\n\n**My Questions**: I have some questions on the theory side of the paper.\n\n- The author(s) described the convergence of FedVote in terms of $|| f(\\tilde{w}^{(k)}) ||^2$, which is a valid measure of stationarity for continuous problems. I wonder what is the conclusion to the discrete problem? For example, we have a stationary point $w^*$ such that $|| f( \\tilde{w}^* ) || = 0$. Then what conclusion can we obtain for the following problem\n$$ \n\t\\min_{w \\in \\mathbb{D}^2_n} f(w).\n$$\nCan we say that we are at a global minimum in the convex case?\n\n- In Lemma 1, the author(s) define $s_i =\\frac{2}{M} \\sum_{i=1}^M \\epsilon_{m,  i}$. From the definition we know $s_i \\in (0,  2)$. Why the author(s) conclude that $s_i \\in (0, 1)$?\n\n-  Theorem 1 describes the convergence of FedVote for $\\eta$ that satisfies the assumption. I wonder why the author(s) do not give a Corollary on the convergence rate for a particular choice of $\\eta$ (which is usually done in the literature, e.g., see the analysis in [1])? It is not straightforward for readers to see the convergence (or non-convergence) without a concrete choice of $\\eta$.\n\n- In Remark 2, the author(s) mention that the variance of quantization error will impede the convergence, which also holds for FedPAQ. However, I do not see any non-convergence issue of FedPAQ from [Theorem 2, 1]. Could the author(s) explain more on the non-convergence of FedPAQ?\n\n- On the theory side, could the author(s) elaborate the advantages of the proposed method over FedPAQ?\n\n[1] Reisizadeh et al. FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization. AISTATS 2020.", "summary_of_the_paper": "The author(s) proposed a new algorithm based on plurality voting for federated learning with quantized gradients. Convergence theory is developed and experiments on both iid and non-iid datasets are conducted to evaluate the proposed method.", "summary_of_the_review": "I have some questions about the theoretical analysis of this paper. I hope that the author(s) could kindly elaborate.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jkipdW02Xyh", "reviewer": "Reviewer_mhMk", "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": "Mainly, the paper has the following weaknesses:\n\n- The main proposed method (FedVote) is incremental at best, and the proposal on the adversarial aspect (Byzantine-FedVote) is limited. The normalization mechanism potentially requires careful tuning. Binary weights reduce uplink communication, but downlink savings depend on probability quantization scheme.\n\n- Confined to using binary neural networks\n\n- It is not clear how the quantization of probability values for soft voting are set (i.e., predefined thresholds) and the effects on performance.\n\n- It is not clear how the predefined coefficients ($\\beta$) are set as it relates to reputation-based voting, and the effects on performance.\n\n- Empirical evaluations is limited:\n  - Several other machine learning models/benchmarks are not evaluated on (e.g., [LEAF: A Benchmark for Federated Settings, Caldas et al. 2019]).\n  - For test accuracy experiments, the number of clients used and the number sampled each round is not given.\n  - For communication efficiency experiment, the number of clients used ($M$=31) is quite small (e.g., [Hsu et al. 2019] uses 100 clients). Down-link GB not accounted for.\n\n- Preliminaries should be provided on adversarial FL/Byzantine attack.\n\n- Information on measuring energy usage (Table 4) not provided.\n\nAre Figure 4 (a) and (b) correctly labeled? \n", "summary_of_the_paper": "The paper presents a scheme for federated learning (FL) called FedVote. In FedVote, clients use binary neural networks where a latent restricted range weight vector $\\boldsymbol{h}$ is learned, and stochastic rounding is applied to obtain quantized weights $\\in$ {$-1,+1$}. The communication cost to the server (up-link) is reduced by using quantized weights. The server aggregates weights by summing over all the weights of the clients at each round of training and applying a sign function. This mechanism is referred to as plurality voting (ties are broken randomly). However, the paper also proposes to use soft voting, which normalizes the number of ones (cf. hard sign function) to get probability values. These probabilities are then quantized with a clipping mechanism to restricted maximum and minimum values, using predefined thresholds, and broadcasted to the clients (down-link). The latent weights of the client models are updated using the soft voting results. The paper also adapts work on reputation-based voting (Bendahmane et al. 2014) to deal with adversarial FL in the form of Byzantine attacks. The paper presents convergence analysis for FedVote under the independent and identically distributed data setting. Empirical evaluations is conducted on two datasets ,Fashion-MNIST and CIFAR-10, and applied to two models, LeNet-5 and VGG-7, respectively.\n", "summary_of_the_review": "The contributions in the paper are limited and not well-focused. Overall, I do not think the paper is at a level for acceptance.\n", "strength_and_weaknesses": "", "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": "UGimMOMYMmt", "reviewer": "Reviewer_LKNM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n1) The paper presents a novel communication efficient federated learning algorithm that quantizes local model weights as opposed to quantizing the local gradients. The paper employs the existing approach of quantizing normalized versions of latent weights to achieve this objective.\n2) The paper address the issue of Byzantine clients and proposes a weighted aggregation method to counter such Byzantines.\n3) Theoretical and empirical results in the paper showcase the utility of the proposed algorithm. \n\nWeaknesses:\n\n1) What purpose does Lemma 1 (one-shot FedVote) serve? The assumption that all the error events are i.i.d. would most like not to hold in a multi-round setting. Even in a single round, would one need independent initializations at different clients for the analysis to hold? Also, why can the probabilities $epsilon_{m, i}$ not be arbitrarily close to 1.\n\n2) Section 4.3 states that (without weighted aggregation) the proposed method is going to be vulnerable to the presence of Byzantines as (on average) it behaves as the FedAvg (Lemma 2). Is this conclusion correct even when one is ensuring weight normalization at the clients?\n\n3) In Section 6, what is the underlying quantization rule when sending ternary weights to the server.\n\n4) Please make the plot colors consistent across Fig 1(a) - 1(c).\n\n5) In the introduction the authors claim that \"However, directly quantizing the gradient vector does not provide the optimal trade-off between communication efficiency and model accuracy.\"  Is there any prior work that supports this blanket statement?", "summary_of_the_paper": "This paper aims to reduce the communication cost for federated learning while ensuring that the aggregation method at the server is tolerant to the presence of Byzantine clients. Towards this instead of communicating the local update/gradients or their quantized version, this paper proposes to communicate the quantized model weights to the server. The server performs the aggregation in the quantized space and communicates the aggregate value back to the clients. To enable faithful quantization of the weights during the communication with the server, each client learns normalized weights (by applying a coordinate-wise normalization function to the latent weights). \n\nThe paper also proposes a weighted aggregation mechanism at the server that takes the reputations of different clients into account.  \n\nThe paper analyzes the impact of the weight quantization on the convergence of the underlying federated learning algorithm in an i.i.d. setting. Empirical evaluations on Fashion-MNIST and CIFAR-10 show that the proposed method outperforms existing local update/gradient compression-based schemes. \n", "summary_of_the_review": "The studies an important problem in the context of federated learning, namely designing communication efficient learning algorithms in the presence of Byzantine clients. The paper presents an interesting weight quantization-based algorithm and analyzes its convergence in an i.i.d. setting. The authors also demonstrate the superiority of the proposed algorithm on existing communication efficient federated learning algorithms in the literature on two standard image classification benchmarks. \n\nThat said, there are some questions that remain about the claims made in the paper (see weaknesses above).", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4F5gfNyYq9k", "reviewer": "Reviewer_B8sD", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I like the topic of this paper, but I have some concerns as below.\n\n1. Explanation on the huge gap between FedVote and SignSGD with majority vote [Bernstein’18]. \n    1. It seems like the basic concept of FedVote is from [Bernstein’18]. I’m bit curious why FedVote has some gap compared with [Bernstein’18]. Is it because of the weighted voting strategy of FedVote? Can we do some ablation study to check what made FedVote such powerful, compared with [Bernstein’18]?\n2. Comparison with other Byzantine-tolerant schemes\n    1. There have been many previous works on Byzantine-tolerant schemes, e.g., using coding scheme to defend Byzantine attacks, DRACO[Chen’18], DETOX[Rajput’19], Election coding [Sohn’20], SignGuard[Xu’21], ByzShield [Konstantinidis’21]. Especially, the last four works focus on the voting-based model/gradient averaging. I think this paper should at least mention these works, and also compare the performance. \n    2. There have been naive methods of using median or mean of median schemes for tolerating Byzantines, starting from 2017, e.g., KRUM, multi-KRUM. I guess this paper didn’t compare with these naive methods also. \n    3. After the [Bernstein’18], there have been upcoming works [Karimireddy’19] suggesting that error feedback fixes the issue of SignSGD. I’m not sure whether the authors compared their work with this scheme. \n    4. So in general, I thought that the literature search and comparison is bit weak. SignSGD is 3-year old paper, and there have been many other papers using voting-based aggregation for Byzantine tolerance. \n\n[Bernstein’18] https://arxiv.org/abs/1802.04434\n[Chen’18] https://arxiv.org/abs/1803.09877\n[Karimireddy’19] http://proceedings.mlr.press/v97/karimireddy19a/karimireddy19a.pdf\n[Rajput’19] https://proceedings.neurips.cc/paper/2019/hash/415185ea244ea2b2bedeb0449b926802-Abstract.html\n[Sohn’20] https://proceedings.neurips.cc/paper/2020/hash/a7f0d2b95c60161b3f3c82f764b1d1c9-Abstract.html\n[Xu’21] https://arxiv.org/pdf/2109.05872.pdf\n[Konstantinidis’21] https://arxiv.org/abs/2010.04902", "summary_of_the_paper": "This paper provides a voting-based quantized model averaging method for federated learning. The convergence is proved and the experimental results on Fashion-MNIST and CIFAR-10 show that the proposed scheme outperforms existing schemes.\n", "summary_of_the_review": "This is an interesting paper, but the idea is quite similar to SignSGD paper, and has no thorough comparison with existing works. Better comparison & ablation are needed to better understand why FedVote works better than existing schemes. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewers raised several valid concerns about novelty of quantization idea and lack of discussions related to prior art (AISTATS 2020 paper). The rebuttal did not convince the reviewers to raise their score. We hope the authors will benefit from the feedback and improve the paper for future submission.
Decision: Reject