Year: 2021

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 to the methods directly quantizing the model updates.

heading: 1 INTRODUCTION
text: Federated learning enables multiple workers to solve a machine learning problem under the coordination of a central server (Kairouz et al., 2021). Throughout the training stage, client data will be kept locally and only model weights or model updates will be shared with the server. Federated averaging (FedAvg) (McMahan et al., 2017) was proposed as a generic federated learning solution. Although FedAvg takes advantage of distributed client data while maintaining their privacy, it leaves the following two challenges unsolved. First, transmitting high-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 optimal trade-off between communication efficiency and model accuracy 1. Second, the aggregation rule in FedAvg is vulnerable to Byzantine attacks (Blanchard et al., 2017). Prior works tackled this issue by using robust statistics such as coordinate-wise median and geometric median in the aggregation step (Blanchard et al., 2017; Yin et al., 2018). Another strategy is to detect and reject updates from malicious attackers (Muñoz-González et al., 2019; Sattler et al., 2020). The robustness of the algorithm is enhanced at the cost of additional computation and increased complexity of algorithms.
In this paper, we propose a new method called federated learning via plurality vote (FedVote). We train a neural network at each worker with a range normalization function applied to model parameters. After local updating, binary/ternary weight vectors are obtained via stochastic rounding and sent to the server. The global model is updated by a 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 FedVote as a novel federated learning solution to jointly optimize the communication 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 a high compression ratio and good test accuracy. Given a fixed communication cost, FedVote improves model accuracy on the CIFAR-10 dataset by 5–10%, 15–20%,
1Predictive coding in video and image compression (Li et al., 2015; Gonzalez & Woods, 2014) is an example that directly quantizing the raw signal we intend to transmit does not provide the best trade-off between the coding efficiency and the utility/bitrate.
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, Byzantine-FedVote, exhibits much better resilience to Byzantine attacks in the presence of close to half attackers without incurring excessive computation compared with existing algorithms.

heading: 2 RELATED WORK
text: Communication-Efficient 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, Bernstein et al. (2018) showed that sign-based gradient descent schemes can converge well in the homogeneous data distribution scenario, while Chen et al. (2020); Jin et al. (2020); Safaryan & Richtarik (2021) extended it to the heterogeneous data distribution setting. In parallel, FedAvg adopts a periodic averaging scheme and targets at reducing the number of communication rounds (McMahan et 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-precision networks using quantized weights while keeping their generalizability. As a special case, binary neural networks (BNNs) are gaining popularity in recent years. By restricting model weight values to {−1,+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 or ternary weights. Gong 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 of distributed quantized neural networks, which was later implemented in the application of intrusion detection (Qin et al., 2020b). 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 a 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-rule-based remedy using the similarity of local updates. Similarly, Yin et al. (2018) took the advantage of coordinatewise median and trimmed-mean to robustify the aggregation. Muñoz-González et al. (2019) and Sattler et al. (2020) detected the adversaries and filtered out their model updates. In this paper, we propose a reputation-based voting strategy for FedVote that is shown to have good convergence performance in the Byzantine setting.

heading: 3 PRELIMINARIES
text: Symbol conventions are as follows. Bold lower cases of letters such as vm denote column vectors, and vm,i is used to denote its ith entry. For a scalar function, it applies elementwise operation when a vector input is given. 1 = [1, . . . , 1]> denotes a vector with all entries equal to 1.

heading: 3.1 FEDERATED LEARNING
text: 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, a server will coordinate the training without seeing the raw data (Kairouz et al., 2021). In a supervised learning scenario, let Dm = {(xm,j ,ym,j)}nmj=1 denote the training dataset on the mth worker, with the input xm,j ∈ Rd1 and the label ym,j ∈ Rd2 in each training pair. The local objective function fm with a model weight vector θ ∈ Rd is given by
fm(θ) , fm(θ;Dm) = 1
nm nm∑ j=1 `(θ; (xm,j ,ym,j)), (1)
where ` is a loss function quantifying the error of model θ predicting the label ym,j for an input xm,j . A global objective function may be formulated as
min θ∈Rd
f(θ) = 1
M M∑ m=1 fm(θ). (2)

heading: 3.2 QUANTIZED NEURAL NETWORKS
text: Consider a neural network g with the weight vector θ ∈ Rd. A forward pass for an input x ∈ Rd1 and a prediction ŷ ∈ Rd2 can be written as ŷ = g(θ,x). In quantized neural networks, the realvalued θ is replaced by w ∈ Ddn, where Dn is a discrete set with a number n of quantization levels. For example, we may have D2 = {−1, 1} for a binary neural network. For a given training set {(xj ,yj)}Nj=1 and the loss function `, the goal is to find an optimal w∗ such that the averaged loss is minimized over a search space of quantized weight vectors:
w? = argmin w∈Ddn
1
N N∑ j=1 `(w; (xj ,yj)). (3)
Prior studies tried to solve (3) by optimizing a real-valued latent weight vector h ∈ Rd (Hubara et al., 2016; Shayer et 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 two levels during the forward pass. The binary weights can be viewed as an approximation of their latent real-valued counterparts. Shayer et al. (2018) trained a stochastic binary neural network, and the normalized latent parameters are interpreted as the Bernoulli distribution parameter ϑi: ϑi , P̂(wi = 1) = S(hi), wi ∈ {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̃sto-bnn , E[w] = −1×[1−S(h)] + 1×S(h) = 2S(h)− 1, (5) will participate in the actual convolution or matrix multiplication operations. In other words, the neural network function becomes ŷ = g(w̃sto-bnn,x). Likewise, Gong et al. (2019) normalized the latent weight but interpreted it from a different viewpoint. They approximated the staircase quantization function with a differentiable soft quantization (DSQ) function, i.e.,
w̃dsq , tanh(ah), (6) where tanh : R → (−1, 1) is the hyperbolic tangent function, and a controls the shape of the function. The neural network function thus becomes ŷ = g(w̃dsq,x).
We now summarize the latent-weight-based BNN training methods and depict an example of a single-layer network in Figure 1. First, a real-valued vector h ∈ Rd is introduced and its range is restricted using a differentiable and invertible normalization function ϕ : R→ (−1, 1). The forward pass is then calculated with the normalized weight vector w̃. The procedure is described as:
ŷ = g(w̃,x), w̃ , ϕ(h). (7) Second, in the back propagation, the latent weight vector h is updated with its gradient, i.e., h(t+1) = h(t) − η∇h`. Finally, the normalized weight vector w̃ are mapped to the discrete space to approximate w∗ via thresholding or stochastic rounding.

heading: 4 PROPOSED FEDVOTE ALGORITHM
text: In this section, we present our proposed method with an emphasis on uplink communication efficiency and enhanced Byzantine resilience. We follow the widely adopted analysis framework in wireless communication to 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, we train a 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 (2), i.e.,
w∗ = argmin w∈Ddn f(w). (8)
For the simplicity of presentation, we mainly focus on the BNN case with D2 = {−1, 1}. We illustrate the procedure in Figure 2 and provide the pseudo code in Appendix B. Below, we explain each step in more detail.

heading: 4.1 LOCAL MODEL TRAINING AND TRANSMISSION
text: We optimize a neural network with a learnable latent weight vector h. In the kth communication round, we assume all workers are identically initialized by the server, namely, ∀ m ∈ {1, . . . ,M}, h(k,0)m = h
(k). To reduce the total number of communication rounds, we first let each worker conduct local updates to learn the binary weights. For each local iteration step, the local latent weight vector h(k,t+1) is updated by the gradient descent:
h(k,t+1)m = h (k,t) m − η ∇hfm ( ϕ(h(k,t)m ); ξ (k,t) m ) , t ∈ {0, . . . , τ − 1}, (9)
where ξ(k,t)m is a mini-batch randomly drawn fromDm at the tth iteration of round k. After updating for τ steps, we obtain h(k,τ)m and the corresponding normalized weight vector w̃ (k,τ) m ∈ (−1, 1)d defined as follows: w̃(k,τ)m , ϕ(h (k,τ) m ). (10)
To reduce the message size, we use the stochastic rounding to draw a randomly quantized version w (k,τ) m using w̃ (k,τ) m , namely,
w (k,τ) m,i =
{ +1, with probability π(k,τ)m,i = 1 2 [ w̃ (k,τ) m,i + 1 ] ,
−1, with probability 1− π(k,τ)m,i . (11)
It can be shown that the stochastic rounding is an unbiased procedure, i.e., E[w(k,τ)m ∣∣w̃(k,τ)m ] = w̃ (k,τ) m . After quantization, the local worker will send the binary weights w (k,τ) m to the server for the global model aggregation.

heading: 4.2 GLOBAL MODEL AGGREGATION AND BROADCAST
text: Once the server gathers the binary weights from all workers, it will perform the aggregation via plurality vote, i.e., w(k+1) = sign (∑M m=1 w (k,τ) m ) . A 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.1. Lemma 1 (One-Shot FedVote) Let w∗ ∈ Dd2 be the optimal solution defined in (8). For the mth worker, εm,i , P(w(k,τ)m,i 6= w∗i ) denotes the error probability of the voting result of the ith coordinate. Suppose the error events {w(k,τ)m,i 6= w∗i }Mm=1 are mutually independent, and the mean error probability si = 1M ∑M m=1 εm,i is smaller than 1 2 . For the voted weight w (k+1), we have
P ( w
(k+1) i 6= w ∗ i ) 6 [ 2si exp(1− 2si) ]M 2 . (12)
In practice, the number of available workers may be limited in each round, and the local data distribution 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 to build an empirical distribution of global weight w, i.e.,
P̂(w(k+1)i = 1) = 1
M M∑ m=1 1 ( w (k,τ) m,i = 1 ) , (13)
where 1 (·) ∈ {0, 1} is the indicator function. Let p(k+1)i , P̂(w (k+1) i = 1) and p (k+1) = [p (k+1) 1 , . . . , p (k+1) d ] >. The global latent parameters can be constructed by following (10):
h(k+1) = ϕ−1(2p(k+1) − 1), (14) where ϕ−1 : (−1, 1) → R is the inverse of the normalization function ϕ. We further apply clipping to restrict the range of the probability, namely, clip(p(k+1)i ) = max(pmin,min(pmax, p (k+1) i )), where pmin, pmax ∈ (0, 1) are predefined thresholds. To keep the notation consistent, we denote w̃(k+1) , ϕ(h(k+1)) as the global normalized weight. After broadcasting the soft voting results p(k+1), all workers are synchronized with the same latent weight h(k+1) and normalized weight w̃(k+1). The learning procedure will repeat until a 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̃(k+1) ] = 1M M∑ m=1 w̃ (k,τ) m , where w̃(k+1) = ϕ(h(k+1)) and w̃ (k,τ) m = ϕ(h (k,τ) m ).

heading: 4.3 REPUTATION-BASED BYZANTINE-FEDVOTE
text: Lemma 2 shows that FedVote is related to FedAvg in expectation. As we have reviewed in Section 2, FedAvg cannot tolerate a single Byzantine attacker. It indicates that FedVote 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). In our design, we modify (13) to P̂(w(k+1)i = 1) = ∑M m=1 λ (k) m 1 ( w (k,τ) m,i = 1 ) , where λ(k)m is proportional to a credibility score. In Byzantine-resilient FedVote (Byzantine-FedVote), we assume that at least 50% of the workers behave normally and treat the plurality vote result as the correct decision. The credibility score of the mth worker is calculated by counting the number of correct votes it makes: CR(k+1)m = 1 d ∑d i=1 1 ( w (k,τ) m,i = w (k+1) i ) . Through multiple rounds, we track the credibility of a local worker by taking an exponential moving average over the communication rounds, namely, ν(k+1)m = β ν (k) m + (1 − β) CR(k+1)m , where β ∈ (0, 1) is a predefined coefficient. The weight λ(k)m is designed as λ (k) m = ν (k) m / ∑M m=1 ν (k) m .
Even though the presentation in this section focuses on the binary weights, the scheme can be naturally extended to quantized neural networks of more discrete levels. We will briefly discuss the implementation for ternary weights in Section 6.

heading: 5 ANALYSIS OF ALGORITHM
text: In this section, we present the theoretical analysis of FedVote when local data are independent and identically distributed (i.i.d.). The empirical results in the non-i.i.d. setting will be discussed in Section 6, and the corresponding analyses are left for future work. We use the gradient norm expectation as an indicator of convergence, which is commonly adopted in nonconvex optimization literature (Reisizadeh et al., 2020; Haddadpour et al., 2021). To simplify the notation, we first denote the stochastic local gradient by g̃(k,t)m , ∇hfm(ϕ(h (k,t) m ); ξ (k,t) m ). The local true gradient and
global true gradient will be denoted by g(k,t)m , Eξ [ g̃(k,t)m ] , g(k) , ∇hf(ϕ(h(k))), respectively. In addition, let ζ(k)m , w̃ (k,τ) m −w(k,τ)m denote the error introduced by stochastic rounding. According to the unbiased property of stochastic rounding, we have Eπ[ζ(k)m ] = 0. With the aforementioned notations, we state five assumptions for the convergence analysis.

heading: 5.1 ASSUMPTIONS
text: Assumption 1 (Lower bound) ∀ h ∈ Rd, w̃ ∈ (−1, 1)d, the objective function is lower bounded by a constant f∗, i.e., f(w̃) > f∗ = minh∈Rd f(ϕ(h)). Assumption 2 (L-smoothness) ∀ w̃1, w̃2 ∈ (−1, 1)d, m ∈ {1, . . . ,M}, there exists some nonnegative L such that ‖∇fm(w̃1)−∇fm(w̃2)‖2 6 L ‖w̃1 − w̃2‖2. Assumptions 1 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 ϕ : R → (−1, 1) is strictly increasing. In particular, we assume its first derivative is bounded for all h(k,t)m,i , i.e., d dhϕ(h (k,t) m,i ) ∈ [c1, c2], where c1, c2 are positive parameters independent of k, t, m, and i.
Assumption 3 is not difficult to satisfy in practice. For example, let ϕ(h) = tanh(ah), we have ϕ′(h) = a [ 1− tanh2(ah) ] , with c2 = a. Note that ϕ quickly saturates with a large h in the local updating. On the other hand, the empirical Bernoulli parameter pi will be clipped for stability, which indicates that h(k,t)m,i will be upper bounded by certain hB. In this sense, we have c1 = a [ 1− tanh2(ahB) ] . The next two assumptions bound the variance of the stochastic gradient and quantization noise.
Assumption 4 The stochastic gradient has bounded variance, i.e., E ∥∥g(k,t)m − g̃(k,t)m ∥∥22 6 σ2ε , where σ2ε is a fixed variance independent of k, t and m.
Assumption 5 The quantization error ζ(k)m has bounded variance, i.e., E ∥∥ζ(k)m ∥∥22 6 σ2k, where σ2k is a fixed variance independent of m.
Note that quantization error is affected by the quantizer type and the corresponding input. For example, if the normalization function ϕ approximates the sign function very well, the stochastic quantization error will be close to zero. Formally, the upper bound σ2ζ can be viewed as a function of input dimension d, which we 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 Qsr defined in (11), then the quantization error satisfies E
[∥∥Qsr(a)− a∥∥22∣∣a] = d− ∥∥a∥∥22. For existing algorithms quantizing the model update δ(k)m , θ
(k) − θ(k,τ)m , the quantizer has the property E [∥∥Q(x)− x∥∥2 2 ∣∣x] 6 q∥∥x∥∥2 2 . With a fixed quantization step, q increases when the input dimension d increases (Basu et al., 2020). We state the result for a widely-used quantizer, QSGD (Alistarh et al., 2017), which has been adopted in FedPAQ, in the following lemma. Lemma 4 Suppose we have an input x ∈ Rd for the QSGD quantizer Q. In the coarse quantization scenario, the quantization error satisfies E [∥∥Q(x)− x∥∥2 2 ∣∣x] = O (d 12)∥∥x∥∥2 2 .

heading: 5.2 CONVERGENCE ANALYSIS
text: We state the convergence results in the following theorem. The proof can be found in Appendix D.5. Theorem 1 For FedVote under Assumptions 1 to 5, let the learning rate η = O (
( c1c2 ) 2 1 Lτ √ K
) , then
after K rounds of communication, we have
1
K K−1∑ k=0 c21E ∥∥∇f(w̃(k))∥∥2 2 6
2 [ f(w̃(0))− f(w̃∗) ] ητK + c22Lη [ 1 M + c21Lη(τ − 1) 2 ] σ2ε
+ L
ητKM K−1∑ k=0 σ2k + 2(c22 − c21) τMK K−1∑ k=0 M∑ m=1 R(k)m . (15)
where R(k)m , − τ−1∑ t=0 ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇f(w̃(k,t)m ))i ] and I(k,t)m , { i | g(k)i g (k,t) m,i > 0 } .
Remark 1 When there is no normalization function and quantization, i.e., ϕ(x) = x with c1 = c2 = 1, σ2k = 0, Theorem 1 recovers the result obtained in Wang & Joshi (2018).
To discuss the impact of quantization error, consider the distribution of different inputs. For the model update δ(k)m , we expect the central limit theorem to render its distribution shape, where each entry δ(k)m,i follows the Gaussian distribution. For the Bernoulli probabilityπ(k,τ)m , we expect the Beta distribution as the conjugate prior to render its distribution shape, where each entry π (k,τ) m,i follows the symmetric Beta distribution. See Figure 3 for the empirical results.
Remark 2 Following the analysis framework in Theorem 1, the order-wise convergence rate is 1 K ∑K−1 k=0 E ∥∥∇f (w(k))∥∥2 2 = O( 1√ K ) +E(d), where E(d) is the error introduced by the quantization. For FedVote with the normalized weight w̃(k,τ)m as the input, when π (k,τ) m,i ’s follow the symmetric Beta distribution, it can be shown that E‖ζ(k)m ‖22 = O (d) based on Lemma 3. For algorithms such as FedPAQ with the model update δ(k)m as the input, when δ (k) m,i’s follow the Gaussian distribution, it
can be shown that E ∥∥Q(δ(k)m )−δ(k)m ∥∥22 = O (d3/2) based on Lemma 4. When the weight dimension d is sufficiently large, FedVote converges faster.
Remark 3 The value of the positive scalar error term R(k)m in (15) depends on the gradient dissimilarity. If the angle between the local gradient ∇fm(w̃(k,t)m ) and the global gradient ∇f(w̃(k,t)) is not large, R(k)m can be treated as a bounded variable.
Remark 4 The choice of nonlinear function ϕ : Rd → (−1, 1)d will affect the convergence. If ϕ 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 a smaller σ2k according to Lemma 3, which leads to a tighter bound in (15). Meanwhile, a larger c2 will negatively influence the convergence.

heading: 6 EXPERIMENTAL RESULTS
text: Data and Models. We choose image classification datasets Fashion-MNIST (Xiao et al., 2017) and CIFAR-10 (Krizhevsky, 2009). Both of them have a total of 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 to simulate the heterogeneity. In particular, for the mth worker we draw a random vector qm ∼ Dir(α), where qm = [qm,1, · · · , qm,C ]> belongs to the standard (C−1)-simplex. We then assign data samples from different classes to the mth worker following the distribution of
Table 1: Test Accuracy in the Byzantine Setting
Dataset Distri-bution signSGD
CoMed
Proposed
FashionMNIST i.i.d. 61.5% 77.7% 91.4% non-i.i.d 61.0% 73.4% 89.4%
CIFAR10 i.i.d. 13.5% 29.3% 76.6% non-i.i.d 11.0% 28.7% 72.0%
Table 2: Effect of the Normalization Function
FashionMNIST
a
0.5 1.5 2.5 10
i.i.d. float 90.7% 90.6% 90.0% 88.2% binary 88.7% 90.4% 89.9% 88.2%
noni.i.d.
float 87.3% 86.9% 85.7% 85.0% binary 83.3% 85.5% 85.2% 84.6%
qm. We set α = 0.5 unless noted otherwise. We use a 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 FedVote design. First, following prior works (Shayer et al., 2018; Gong et al., 2019), we keep the weights of the BNN final layer as floating-point 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) (Ioffe & Szegedy, 2015) after the convolutional layer is necessary to scale the activation. We use the static BN without learnable parameters and local statistics (Diao et al., 2021) to ensure the voting aggregation of binary weights. For the normalization function, we choose ϕ(x) = tanh(3x/2) unless noted otherwise. More details of the experimental setup can be found in Appendix C.1.
Communication Efficiency and Convergence Rate. In this experiment, we consider M = 31 workers with full participation and compare FedVote to different methods within N = 100 communication rounds. The results of partial participation can be found in Appendix C.3. The communication cost is calculated as the accumulative uplink message size from all workers. Figure 4 reveals that FedVote outperforms the gradient-quantization-based methods such as signSGD (Bernstein et al., 2018) that quantizes gradients to 1 bit signs, and FedPAQ (Reisizadeh et al., 2020) that quantizes the updates to 2 bits integers. Compared with FedPAQ, signSGD, and FedAvg, FedVote improves the test accuracy by 5–10%, 15–20%, and 25–30%, respectively, given the fixed communication costs of 1.5–4.7 GB.
Byzantine Resilience. This experiment validates the effectiveness of Byzantine-FedVote. 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 is 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, as they are fragile to Byzantine failure. The results are shown in Table 1. It can be observed that ByzantineFedVote exhibits much better resilience to Byzantine attacks with close to half adversaries.
Table 3: Test Accuracy of TNN and BNN
Dataset Distri-bution BNN TNN
FashionMNIST i.i.d. 91.1% 91.9% non-i.i.d 88.3% 89.4%
CIFAR10 i.i.d. 80.5% 82.5% non-i.i.d 74.6% 77.6%
Normalization Function. From Remark 4, we know that the normalization function can influence the model convergence. We empirically examine the impact in this experiment. For normalization function ϕ(x) = tanh(ax), we choose a 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 2. As a increases, the linear region of the normalization function shrinks, and the algorithm converges slower due to a 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 to 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 extend FedVote 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 follows. For each ternary weight w(k,t)m,i , we still keep a latent parameter h (k,t) m,i to optimize. After τ local steps, we use the stochastic rounding to the normalized weight w̃(k,τ)m = ϕ(h(k,τ)m ) and obtain quantized weight w(k,τ)m . At the aggregation stage on the server, instead of calculating the vote distribution, we directly compute the global normalized weight as w̃(k+1) = 1M ∑M m=1 w (k,τ) m . More details can be found in Appendix C.4. The training results are shown in Table 3. As TNNs can further reduce the quantization error, their performance is better than the BNNs at the cost of additional 1 bit/dimension communication overhead.
Deployment Efficiency. We highlight the advantages of BNNs during deployment on edge devices. In FedVote, 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 energy 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 ∈ Rd1 and output y ∈ Rd2 : y = W>x. For a floating-point weight matrix W ∈ Rd1×d2 , the number of multiplications is d1d2, whereas for a binary matrix Wb ∈ Dd1×d22 all multiplication operations can be replaced by additions. We investigate the number of real multiplications and additions in the forward pass of different models and present the results in Table 4. We use the CIFAR-10 dataset and set the batch size to 100. As to the energy consumption calculation, we use 3.7 pJ and 0.9 pJ as in Hubara et al. (2016) for each floating-point multiplication and addition, respectively.

heading: 7 CONCLUSION
text: In this work, we have proposed FedVote to jointly optimize communication overhead, learning reliability, and deployment efficiency. In FedVote, the server aggregates neural networks with binary/ternary weights via voting. We have verified that FedVote can achieve good model accuracy even in coarse quantization settings. Compared with gradient quantization, model quantization is a more effective design that achieves better trade-offs between communication efficiency and model accuracy. With the voting-based aggregation mechanism, FedVote enjoys the flexibility to incorporate various voting protocols to increase the resilience against Byzantine attacks. We have demonstrated that Byzantine-FedVote exhibits much better Byzantine resilience in the presence of close to half attackers compared to the existing algorithms.

heading: B FEDVOTE ALGORITHM
text: We summarize the proposed FedVote method and its Byzantine-resilient variant in Algorithm 1. When there are no attackers involved, we use Option I. When we require the resilience against Byzantine failure, we choose Option II.

heading: C SETUP AND ADDITIONAL EXPERIMENTS

heading: C.1 HYPERPARAMETERS
text: For the clipping thresholds, we set pmin = 0.001 and pmax = 1−pmin. The thresholds are introduced for numerical stability and have little impact on performance. We use β = 0.5 in Byzantine-FedVote. 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 η over the set {10−4, 3×10−4, 10−3, 3×10−3, 10−2, 3× 10−2, 10−1, 3×10−1}. We set the number of local iterations τ to 40 and the local batch size to 100.

heading: C.2 COMPARISON OF VANILLA FEDVOTE AND BYZANTINE-FEDVOTE
text: 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-FedVote, Vanilla FedVote, and signSGD on the non-i.i.d. CIFAR-10 dataset (α = 0.5) with various numbers of omniscient attackers. Figure 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-FedVote is negligible, confirming its resilience to omniscient attackers.
Algorithm 1: Binary-Weight FedVote with/without Byzantine Tolerance 1 initialize p(0) and broadcast 2 for k = 0, 1, . . . , N − 1 do 3 on mth worker: 4 receive p(k) from the server 5 initialize latent weight h(k,0)m = ϕ−1(2p(k) − 1) 6 for t = 0 : τ − 1 do 7 g̃(k,t)m = ∇hfm(ϕ(h (k,t) m ); ξ (t,r) m ) 8 h(k,t+1)m = h (k,t) m − η(k,t) g̃(k,t)m 9 w̃ (k,τ) m = ϕ(h (k,τ))
10 w (k,τ) m = sto rounding(w̃ (k,τ) m ) . Eq. (11) 11 send w(k,τ)m to server 12 on server: 13 {w(k+1),p(k+1)} = vote({w(k,τ)m }Mm=1) 14 broadcast p(k+1) to workers
15 function vote({w(k,τ)m }Mm=1) 16 for i = 1 : d do
17 w (k+1) i = sign ( M∑ m=1 w (k,τ) m,i )
18
p (k+1) i = 1 M M∑ m=1 1 ( ŵ (k,τ) m,i = 1 ) . Option I
19 p (k+1) i = M∑ m=1 λ (k) m 1 ( w (k,τ) m,i = 1 ) . Option II
20 return {w(k+1),p(k+1)} to the server

heading: C.3 CONVERGENCE OF FEDVOTE WITH PARTIAL PARTICIPATION
text: 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. (2017), FedPAQ (Reisizadeh et al., 2020), and signSGD (Bernstein et al., 2018) in Figure 5 on the non-i.i.d. CIFAR-10 dataset (α = 0.5) without changing other experimental setups. The observation is consistent with the results in Figure 4. FedVote outperforms gradient quantization methods such as FedPAQ and signSGD.

heading: C.4 EXTENSION TO TERNARY NEURAL NETWORKS
text: The stochastic rounding used in the ternary neural networks, wi = Qsr(w̃), is an extension of (11):
wi = { +1, with probability π1 = w̃i 1(w̃i > 0), −1, with probability π2 = −w̃i 1(w̃i < 0), 0, with probability 1− (π1 + π2).
(20)
One can modify the normalization function to optimize neural networks with multiple quantization levels. For example, consider quaternary weight wi ∈ {−2,−1, 1, 2}, the normalization function ϕ(x) can be modified to ϕ(x) = 2 tanh(ax).

heading: C.5 BATCH NORMALIZATION IN FEDVOTE
text: Below we review the commonly-adopted BN function for convenience of presentation. For a onedimensional input x(j) from the current batch B = {x(1), · · · , x(nb)}, the output of BN layer is formulated as
y , BNγ,b(x(j)) = γ x(j) − µ√ σ2 + + b, (21)
where γ, b are learnable affine transformation parameters, and µ, σ2 are the mean and variance calculated over the batch samples. Note that the normal BN layer will introduce the real-valued parameters and track the statistics of the input, all of which may cause problems when being binarized in FedVote. Therefore, we choose to set the parameter-free static BN, i.e.,
y′ , BN(x(j)) = x− EB[x(j)]√ VarB[x(j)] + . (22)

heading: D MISSING PROOFS

heading: D.1 PROOF OF LEMMA 1
text: Lemma 1 (One-Shot FedVote) Let w∗ ∈ Dd2 be the optimal solution defined in (8). For the mth worker, εm,i , P(w(k,τ)m,i 6= w∗i ) denotes the error probability of the voting result of the ith coordinate. Suppose the error events {w(k,τ)m,i 6= w∗i }Mm=1 are mutually independent, and the mean error probability si = 1M ∑M m=1 εm,i is smaller than 1/2. For the voted weight w (k+1), we have
P ( w
(k+1) i 6= w ∗ i ) 6 [ 2si exp(1− 2si) ]M 2 . (23)
Proof. Let Xm,i , 1 ( w (k,τ) m,i 6= w∗i ) , following Bernoulli distribution with parameter εm,i. Let
Yi = ∑M m=1Xm,i, we have
P ( w
(k+1) i 6= w ∗ i
) = P ( Yi > M
2
) . (24)
With independent vote results from workers, Yi follows Poisson binomial distribution with mean µYi = ∑M m=1 εm,i. ∀ a > 0, the Chernoff bound can be derived as
P ( Yi > M
2
) (25a)
= P(eaYi > e aM 2 ) (25b)
¬ 6 exp ( −aM
2
) E [ eaYi ] (25c)
= exp ( −aM
2 ) M∏ m=1 (1− εm,i + eaεm,i) (25d)
= exp ( −aM
2 + M∑ m=1 ln (1 + εm,i(e a − 1))
) (25e)
 6 exp ( −aM
2 + M∑ m=1 εm,i(e a − 1)
) . (25f)
where ¬ is based on Markov’s inequality.  holds due to ln(1 + x) 6 x for all x ∈ (−1,∞).
By assumption we have µYi < M 2 . Let a = ln M 2µYi , we have P ( Yi > M
2
) 6 exp ( −µYi + M2 )( M
2µYi
)M 2
(26a)
6 ( 2µYi M exp ( 1− 2µYi M ))M 2 . (26b)
Let si = µYi M = 1 M ∑M m=1 εm,i and substitute it into (26b), the proof is complete.

heading: D.2 PROOF OF LEMMA 2
text: Lemma 2 (Relationship with FedAvg) For the normalized weights, FedVote recovers FedAvg in expectation: E [ w̃(k+1) ] = 1M M∑ m=1 w̃ (k,τ) m , where w̃(k+1) = ϕ(h(k+1)) and w̃ (k,τ) m = ϕ(h (k,τ) m ).
Proof. From the inverse normalization in (14), we have w̃(k+1) = 2p(k+1)−1. Recall the definition of the empirical Bernoulli parameter p(k+1) given by (13), we have the elementwise expectation
Eπ [ w̃ (k+1) i ] = 1
M M∑ m=1 ( 2P̂(w(k,τ)m,i = 1)− 1 ) (27a)
¬ =
1
M M∑ m=1 ϕ(h (k,τ) m,i ), (27b)
where ¬ follows from stochastic rounding defined in (11). Based on the definition of range normalization in (10), for local normalized weight we have w(k,τ)m,i = ϕ(h (k,τ) m,i ). Substituting the result into (27b) we have
Eπ [ w̃(k+1) ] = 1
M M∑ m=1 w̃(k,τ)m , (28)
which completes the proof.

heading: D.3 PROOF OF LEMMA 3
text: Lemma 3 Suppose we have an input a ∈ (−1, 1)d for the quantizer Qsr defined in (11), then the quantization error satisfies E [∥∥Qsr(a)− a∥∥22∣∣a] = d− ∥∥a∥∥22.
Proof. Let â , Qsr(a), we have
E [∥∥Qsr(a)− a∥∥22∣∣a] = E [ d∑ i=1 (âi − ai)2 ∣∣a] (29a)
= d∑ i=1 ( E [ â2i ∣∣a]− a2i ) (29b)
= d∑ r=1 ( 1− a2i ) (29c)
= d− ‖a‖22. (29d)
The proof is complete.

heading: D.4 PROOF OF LEMMA 4
text: Lemma 4 Suppose we have an input x ∈ Rd for the QSGD quantizer Q. In the coarse quantization scenario, the quantization error satisfies E [∥∥Q(x)− x∥∥2 2 ∣∣x] = O (d 12)∥∥x∥∥2 2 .
Proof. Consider a QSGD quantizer (Alistarh et al., 2017) with s = 1. For detailed results of other quantizers, we refer readers to Basu et al. (2020).
In particular, we have Qqsgd (xi) = ‖x‖2 · sgn (xi) · ξi(x, s), (30)
where
ξi(x, s)|s=1 = { 0 with prob. 1− |xi|‖x‖2 , 1 with prob. |xi|‖x‖2 .
(31)
The variance of quantization error is
E [∥∥Q(x)− x∥∥2 2 |x ] = E [ d∑ i=1 (x̂i − xi)2 ∣∣x] (32a)
= d∑ i=1 ( E [ x̂2i ∣∣x]− x2i ) (32b)
= ‖x‖22 ∑d i=1 |xi| ‖x‖2 − ‖x‖22 (32c)
= ‖x‖2‖x‖1 − ‖x‖22 (32d) 6 ( √ d− 1)‖x‖22, (32e)
which completes the proof.

heading: D.5 PROOF OF THEOREM 1
text: We first introduce some notations for simplicity. Let ∆(k) denote the difference between two successive global latent weights, i.e.,
∆(k) , w̃(k) − w̃(k+1). (33)
We use ε(k,t)m to denote the stochastic gradient noise, i.e.,
ε(k,t) , g̃(k,t)m − g(k,t)m . (34)
Finally, we let ∇f(w̃) denote the gradient with respect to w̃. The following five lemmas are presented to facilitate the proof.
Lemma 5 The global normalized weight w̃(k) can be reconstructed as the average of local binary weight, i.e.,
w̃(k+1) = 1
M M∑ m=1 w(k,τ)m . (35)
Proof. See Appendix D.6.
Lemma 6 (Lipschitz continuity) Under Assumption 3, ∀ x1, x2 ∈ R, we have
|ϕ(x1)− ϕ(x2)| 6 c2|x1 − x2|. (36)
Proof. Without loss of generality, suppose x1 < x2. Based on the mean value theorem, there exists some c ∈ (x1, x2) such that
ϕ′(c) = ϕ(x2)− ϕ(x1)
x2 − x1 . (37)
For the monotonically increasing function ϕ, we have
ϕ (x2)− ϕ (x1) = ϕ′(c) (x2 − x1) (38a) ¬ 6 c2 (x2 − x1) , (38b)
where ¬ holds due to Assumption 3. The similar result can be obtained by assuming x2 < x1, which completes the proof.
Lemma 7 (Bounded weight divergence) Under Assumption 4, we have
E ∥∥w̃(k,τ)m − w̃(k)∥∥22 6 (c2η)2τ ( τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22 + σ2ε ) . (39)
Proof. See Appendix D.7.
Lemma 8 Under Assumptions 2 to 5, we have
E 〈 ∇f(w̃(k)), ∆(t) 〉 > c21ητ 2 E ∥∥∇f(w̃(k))∥∥2 2 (40)
+ c21η
4M
( 2− (c2L)2η2τ(τ − 1) ) M∑ m=1 τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22
− (c1c2L) 2η3τ(τ − 1)
4 σ2ε − η(c22 − c21) M M∑ m=1 R(k)m , (41)
where R(k)m , − τ−1∑ t=0 ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇f(w̃(k,t)m ))i ] and I(k,t)m , { i | g(k)i g (k,t) m,i > 0 } .
Proof. See Appendix D.8.
Lemma 9 (Bounded global weight difference) Under Assumptions 2 to 5, we have
E ∥∥∆(k)∥∥2
2 6
(c2η) 2τ
M M∑ m=1 τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22 + (c2η)2τM σ2ε + 1Mσ2k. (42)
Proof. See Appendix D.9.
Theorem 1 For FedVote under Assumptions 1 to 5, if the learning let the learning rate η = O (
( c1c2 ) 2 1 Lτ √ K
) , then after K rounds of communication, we have
1
K K−1∑ k=0 c21E ∥∥∇f(w̃(k))∥∥2 2 6
2 [ f(w̃(0))− f(w̃∗) ] ητK + c22Lη [ 1 M + c21Lη(τ − 1) 2 ] σ2ε
+ L
ητKM K−1∑ k=0 σ2k + 2(c22 − c21) τMK K−1∑ k=0 M∑ m=1 R(k)m . (43)
where R(k)m , − τ−1∑ t=0 ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇f(w̃(k,t)m ))i ] and I(k,t)m , { i | g(k)i g (k,t) m,i > 0 } .
Proof. Consider the difference vector ∆(k) defined in (33), we expand it as
∆(k) = w̃(k) − w̃(k+1) (44a)
¬ = w̃(k) − 1
M M∑ m=1 w(k,τ)m (44b)
 = w̃(k) − 1
M M∑ m=1 w̃(k,τ)m + 1 M M∑ m=1 ζ(r)m , (44c)
where ¬ follows from (35), and  holds by substituting the definition of quantization error.
From Assumption 2, we have f(w̃(k+1))− f(w̃(k)) 6 − 〈 ∇f(w̃(k)), ∆(k) 〉 + L
2
∥∥∆(k)∥∥2 2 . (45a)
Let (Lη) 2τ(τ−1) 2 + Lητ c21 6 1 c22 , take the expectation on both sides, and use Lemmas 8–9:
E [ f(w̃(k+1))− f(w̃(k)) ] 6 −c 2 1ητ 2 E ∥∥∇f(w̃(k))∥∥2 2
− (c1c2) 2η
4M
( 2
c22 − L2η2τ(τ − 1)− 2Lητ c21 ) M∑ m=1 τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22
+ (c2η)
2Lτ
4
( 2
M + c21Lη(τ − 1)
) σ2ε +
η(c22 − c21) M M∑ m=1 R(k)m + L 2M σ2k (46a)
¬ 6 −c
2 1ητ 2 E ∥∥∇f(w̃(k))∥∥2 2 + (c2η) 2Lτ 4
( 2
M + c21Lη(τ − 1)
) σ2ε
+ η(c22 − c21)
M
M∑ m=1 R(k)m + L 2M σ2k, (46b)
where ¬ follows from the restrictions on learning rate. We rewrite the restriction as
η 6 −Lτ c21
+ √ L2τ2
c41 + 2L 2τ(τ−1) c22
L2τ(τ − 1) (47a)
¬ 6 −1 +
√ 1 +
2c41 c22
L(τ − 1)c21 (47b)
 6 c21 L(τ − 1)c22 , (47c)
where in ¬ we use τ(τ − 1) 6 τ2, and  holds due to the Bernoulli inequality (1 + x) 12 6 1 + 12x, ∀ x ∈ [−1,∞). Based on (47c), we set the learning rate η = O ( ( c1c2 ) 2 1 Lτ √ K ) . Summing
up over K communication rounds yields
1
K K−1∑ k=0 c21E ∥∥∇f(w̃(k))∥∥2 2 6
2 [ f(w̃(0))− f(w̃∗) ] ητK + c22Lη [ 1 M + c21Lη(τ − 1) 2 ] σ2ε
+ L
ητKM K−1∑ k=0 σ2k + 2(c22 − c21) τMK K−1∑ k=0 M∑ m=1 R(k)m . (48a)

heading: D.6 PROOF OF LEMMA 5
text: Proof. From the reconstruction rule (14), we have
w̃(k+1) = 2p(k+1) − 1. (49)
The ith entry of p(k) is defined in (13) as:
p (k+1) i =
1
M M∑ m=1 1 ( w (k,τ) m,i = 1 ) . (50)
Substituting (50) into (49) yields
w̃ (k+1) i =
1
M M∑ m=1 [ 21 ( w (k,τ) m,i = 1 ) − 1 ] . (51)
Note that
21 ( w
(k,τ) m,i = 1
) − 1 =
{ +1, w (k,τ) m = +1,
−1, w(k,τ)m = −1, (52)
we have
w̃ (k+1) i =
1
M M∑ m=1 w (k) i , (53)
which completes the proof.

heading: D.7 PROOF OF LEMMA 7
text: Proof. With the local initialization and update method described in Algorithm 1, we have E ∥∥w̃(k,τ)m − w̃(k)∥∥22 = E∥∥ϕ(h(k,τ)m )− ϕ(h(k,0)m )∥∥22 (54a)
¬ 6 c22E ∥∥h(k,τ)m − h(k,0)m ∥∥22 (54b) = c22E ∥∥∥∥∥ τ−1∑ t=0 −η g̃(k,t)m ∥∥∥∥∥ 2
2
(54c)
= (c2η) 2E ∥∥∥∥∥ τ−1∑ t=0 ( g(k,t)m + ε (k,t) m )∥∥∥∥∥ 2
2
(54d)
= (c2η) 2 ( E ∥∥∥∥∥ τ−1∑ t=0 g(k,t)m ∥∥∥∥∥ 2
2
+ E ∥∥∥∥∥ τ−1∑ t=0 ε(k,t)m ∥∥∥∥∥ 2
2
) (54e)
6 (c2η) 2τ ( τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22 + σ2ε ) , (54f)
where ¬ comes from the Lipschitz condition in Lemma 6.

heading: D.8 PROOF OF LEMMA 8
text: Proof. We have
E 〈 ∇f(w̃(k)), ∆(k) 〉 = E 〈 ∇f(w̃(k)), w̃(k) − 1
M M∑ m=1 w̃(k,τ)m + 1 M M∑ m=1 ζ(k)m 〉 (55a)
¬ = E 〈 ∇f(w̃(k)), w̃(k) − 1
M M∑ m=1 w̃(k,τ)m 〉 (55b)
= E 〈 ∇f(w̃(k)), 1
M M∑ m=1 ϕ(h(k))− ϕ(h(k,τ)m ) 〉 , (55c)
where ¬ follows from Assumption 5. Based on the mean value theorem, for h(k)i , h (t,τ) m,i ∈ R, there exists some c(k)m,i ∈ H (r) m,i such that
ϕ′(c (k) m,i) =
ϕ(h (k) i )− ϕ(h (k,τ) m,i )
h (k) i − h (k,τ) m,i
, (56)
where H(r)m,i is an open interval with endpoints h (k) i and h (k,τ) m,i :
H(r)m,i =
{ (h
(k) i , h (k,τ) m,i ), if h (k) i < h (k,τ) m,i ,
(h (k,τ) m,i , h (k) i ), otherwise.
(57)
Let C(k)m = diag ( ϕ′(c (k) m,1), . . . , ϕ ′(c (k) m,d) ) , we have
ϕ(h(k))− ϕ(h(k,τ)m ) = C(k)m (h (k) − h(k,τ)m ) = η C(k)m τ−1∑ t=0 ( g(k,t)m + ε (k,t) m ) , (58)
Substituting (58) into (55c) yields
E 〈 ∇f(w̃(k)), ∆(k) 〉 = η
M M∑ m=1 τ−1∑ t=0 E 〈 ∇f(w̃(k)), C(k)m g(k,t)m 〉 . (59)
According to the chain rule, g(k,t)m can be written as
g(k,t)m = ∇hfm(ϕ(h (k,t) m )) = D (k,t) m ∇w̃fm(w̃(k,t)m ), (60) where D(k,t)m = diag ( dϕ
dh (k,t) m,1
, . . . , dϕ dh
(k,t) m,d
) . To simplify the notations, let B(k,t)m = C (k) m D (k,t) m .
Note that B(k,t)m is still a diagonal matrix, where the ith diagonal element b (k,t) m,i is
b (k,t) m,i , (B (k,t) m )i,i =
dϕ
dc (k,τ) m,i
dϕ
dh (k,t) m,i
. (61)
Substituting (60) into (59) we have
E 〈 ∇f(w̃(k)), ∆(k) 〉 = η
M M∑ m=1 τ−1∑ t=0 E 〈 ∇f(w̃(k)), B(k,t)m ∇fm(w̃(k,t)m ) 〉 . (62)
We first focus on the following inner product:〈 ∇f(w̃(k)), B(k,t)m ∇fm(w̃(k,t)m ) 〉 = d∑ i=1 (∇f(w̃(k)))i × b(k,t)m,i (∇fm(w̃ (k,t) m ))i, (63)
where (∇f)i denotes the ith entry of the gradient vector. Consider an index set I(k,t)m defined as
I(k,t)m , { i ∈ {1, . . . , d} | (∇f(w̃(k)))i(∇fm(w̃(k,t)m ))i > 0 } . (64)
Since the sign of (∇f(w̃(k)))i(∇fm(w̃(k,t)m ))i is equal to g(k)i g (k,t) m,i , the index set I (k,t) m can also be written as
I(k,t)m , { i ∈ {1, . . . , d} | g(k)i g (k,t) m,i > 0 } . (65)
The result in (63) can be bounded as
E 〈 ∇f(w̃(k)), B(k,t)m ∇fm(w̃(k,t)m ) 〉 (66a)
¬ > c21 ∑ i∈I(k,t)m E [ (∇f(w̃(k)))i(∇fm(w̃(k,t)m ))i ] + c22 ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇fm(w̃(k,t)m ))i ] (66b)
= c21E 〈 ∇f(w̃(k)), ∇fm(w̃(k,t)m ) 〉 + (c22 − c21) ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇fm(w̃(k,t)m ))i ] , (66c)
where ¬ follows from Assumption 3. To simplify the notation, let R(k)m denote the accumulative gradient divergence, namely,
R(k)m , − τ−1∑ t=0 ∑ i/∈I(k,t)m E [ (∇f(w̃(k)))i(∇f(w̃(k,t)m ))i ] . (67)
The expected inner product in (62) can be bounded as
E 〈 ∇f(w̃(k)), ∆(k) 〉 > c21η
M M∑ m=1 τ−1∑ t=0 E 〈 ∇f(w̃(k)), ∇fm(w̃(k,t)m ) 〉 − η(c 2 2 − c21) M M∑ m=1 R(k)m (68a)
¬ = c21η
2M M∑ m=1 τ−1∑ t=0 ( E ∥∥∇f(w̃(k))∥∥2 2 + E ∥∥∇f(w̃(k,t)m )∥∥22 − E
∥∥∇f(w̃(k,t)m )−∇f(w̃(k))∥∥22)− η(c22 − c21)M M∑ m=1 R(k)m (68b)
 > c21ητ
2
∥∥∇f(w̃(k))∥∥2 2 + c21η
2M M∑ m=1 τ−1∑ t=0 ( E ∥∥∇f(w̃(k,t)m )∥∥22
− L2E ∥∥w̃(k,t)m − w̃(k)∥∥22)− η(c22 − c21)M M∑ m=1 R(k)m , (68c)
where ¬ follows from 2 〈 a, b 〉 = ∥∥a∥∥2 2 + ∥∥b∥∥2 2 − ∥∥a − b∥∥2 2 , and  holds due to Assumption 2. From Lemma 7, we can show that
E ∥∥w̃(k,t)m − w̃(k)∥∥22 6 (c2η)2t ( t−1∑ n=0 ∥∥g(k,n)m ∥∥22 + σ2ε ) , (69)
where t = 1, . . . , τ − 1. Substituting (69) in (68c) yields
E 〈 ∇f(w̃(k)), ∆(k) 〉 > c21ητ
2 E ∥∥∇f(w̃(k))∥∥2 2 + c21η 2M M∑ m=1 τ−1∑ t=0 E ∥∥∇f(w̃(k,t)m )∥∥22
− (c1c2L) 2η3
4M
M∑ m=1 τ−1∑ n=0 (τ(τ − 1)− n(n+ 1))E ∥∥g(k,n)m ∥∥22
− (c1c2L) 2η3τ(τ − 1)
4 σ2ε − η(c22 − c21) M M∑ m=1 R(k)m (70a)
¬ > c21ητ 2 E ∥∥∇f(w̃(k))∥∥2 2 + c21η 2M M∑ m=1 τ−1∑ t=0 E ∥∥∇f(w̃(k,t)m )∥∥22
− η 4M (c1c2L) 2η2τ(τ − 1) M∑ m=1 τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22
− (c1c2L) 2η3τ(τ − 1)
4 σ2ε − η(c22 − c21) M M∑ m=1 R(k)m (70b)
 > c21ητ 2 E ∥∥∇f(w̃(k))∥∥2 2 + c21η 4M ( 2− (c2L)2η2τ(τ − 1) ) M∑ m=1 τ−1∑ t=0 E ∥∥g(k,t)m ∥∥22
− (c1c2L) 2η3τ(τ − 1)
4 σ2ε − η(c22 − c21) M M∑ m=1 R(k)m (70c)
where ¬ follows from τ(τ − 1) − n(n + 1) 6 τ(τ − 1), and  holds due to the chain rule in (60) and Assumption 3.

heading: D.9 PROOF OF LEMMA 9
text: Proof. We have
E ∥∥∆(k)∥∥2
2 = E ∥∥∥∥∥w̃(k) − 1M M∑ m=1 w̃(k,τ)m + 1 M M∑ m=1 ζ(k)m ∥∥∥∥∥ 2
2
(71a)
= E ∥∥∥∥∥ 1M M∑ m=1 ϕ(h(k))− ϕ(h(k,τ)m ) + 1 M M∑ m=1 ζ(k)m ∥∥∥∥∥ 2
2
(71b)
= E ∥∥∥∥∥ 1M M∑ m=1 ϕ(h(k))− ϕ(h(k,τ)m ) ∥∥∥∥∥ 2
2
+ E ∥∥∥∥∥ 1M M∑ m=1 ζ(k)m ∥∥∥∥∥ 2
2
+ 2E
〈 1
M M∑ m=1 ϕ(h(k))− ϕ(h(k,τ)m ), 1 M M∑ m=1 ζ(t)m
〉 (71c)
¬ = E ∥∥∥∥∥ 1M M∑ m=1 ϕ(h(k))− ϕ(h(k,τ)m ) ∥∥∥∥∥ 2
2
+ E ∥∥∥∥∥ 1M M∑ m=1 ζ(k)m ∥∥∥∥∥ 2
2
, (71d)
where ¬ comes from Assumption 5. For the first term in (71d) we have
E ∥∥∥∥∥ 1M M∑ m=1 (ϕ(h(k))− ϕ(h(k,τ)m ) ∥∥∥∥∥ 2
2
6 1
M M∑ m=1 E ∥∥∥ϕ(h(k))− ϕ(h(k,τ)m )∥∥∥2 2 (72a)
¬ 6 c22 M M∑ m=1 ∥∥h(k) − h(k,τ)m ∥∥22 (72b)  = (c2η) 2
M M∑ m=1 ∥∥∥∥∥−η τ−1∑ t=0 g̃(k,t)m ∥∥∥∥∥ 2
2
(72c)
= (c2η)
2
M M∑ m=1 ∥∥∥∥∥ τ−1∑ t=0 (g(k,t)m + ε (k,t) m ) ∥∥∥∥∥ 2
2
(72d)
= (c2η)
2τ
M M∑ m=1 τ−1∑ t=0 E ∥∥∥g(k,t)m ∥∥∥2 2 + (c2η) 2τ M σ2ε , (72e)
where ¬ is due to Lemma 6 and  comes from (9). For the second term in (71d) we have
E ∥∥∥∥∥ 1M M∑ m=1 ζ(k)m ∥∥∥∥∥ 2
2
6 1
M σ2k. (73)
Combing the results of (72e) and (73) completes the proof.

Review summaries:
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. 

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).   The paper also proposes a weighted aggregation mechanism at the server that takes the reputations of different clients into account.    The 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.