Federated Learning With Quantized Global Model Updates
Authors: Mohammad Mohammadi Amiri
Deniz Gunduz
Sanjeev Kulkarni
H. Vincent Poor
Venue:  (2021)
Keywords: Federated learning
lossy broadcasting

Abstract: We study federated learning (FL), which enables mobile devices to utilize their local datasets to collaboratively train a global model with the help of a central server, while keeping data localized. At each iteration, the server broadcasts the current global model to the devices for local training, and aggregates the local model updates from the devices to update the global model. Previous work on the communication efficiency of FL has mainly focused on the aggregation of model updates from the devices, assuming perfect broadcasting of the global model. In this paper, we instead consider broadcasting a compressed version of the global model. This is to further reduce the communication cost of FL, which can be particularly limited when the global model is to be transmitted over a wireless medium. We introduce a lossy FL (LFL) algorithm, in which both the global model and the local model updates are quantized before being transmitted. We analyze the convergence behavior of the proposed LFL algorithm assuming the availability of accurate local model updates at the server. Numerical experiments show that the proposed LFL scheme, which quantizes the global model update (with respect to the global model estimate at the devices) rather than the global model itself, significantly outperforms other existing schemes studying quantization of the global model at the PS-to-device direction. Also, the performance loss of the proposed scheme is marginal compared to the fully lossless approach, where the PS and the devices transmit their messages entirely without any quantization.

Under review as a conference paper at ICLR 2021
FEDERATED LEARNING WITH QUANTIZED GLOBAL MODEL UPDATES
ABSTRACT
We study federated learning (FL), which enables mobile devices to utilize their local datasets to collaboratively train global model with the help of a central server, while keeping data localized. At each iteration, the server broadcasts the current global model to the devices for local training, and aggregates the local model updates from the devices to update the global model. Previous work on the communication efficiency of FL has mainly focused on the aggregation of model updates from the devices, assuming perfect broadcasting of the global model. In this paper, we instead consider broadcasting a compressed version of the global model. This is to further reduce the communication cost of FL, which can be particularly limited when the global model is to be transmitted over a wireless medium. We introduce a lossy FL (LFL) algorithm, in which both the global model and the local model updates quantized before being transmitted. We ana- lyze the convergence behavior of the proposed LFL algorithm assuming the availability of accurate local model updates at the server. Numerical periments show that the proposed LFL scheme, which quantizes the global model update (with respect to the global model estimate at the devices) rather than the global model itself, significantly outperforms other exist- ing schemes studying quantization of the global model at the PS-to-device direction. Also, the performance loss of the proposed scheme is marginal compared to the fully lossless approach, where the PS and the devices transmit their messages entirely without any quantization.
INTRODUCTION
Federated learning (FL) enables wireless devices to collaboratively train a global model by utilizing locally available data and computational capabilitics under the coordination of a parameter server (PS) while the data never leaves the devices McMahan & Ramage (2017).
In FL with M devices the goal to minimize a loss function F(0) = EM B.n F, (0) with respect to the global model e Rd, where Fm (0) Bm, EuEB., f (0, u) is the loss function at device m, with B,, representing device m's local dataset of size Bn, B 2 f(---) -) is an empirical loss function. Having access to the global model 0, device m utilizes its local dataset and performs multiple iterations of stochastic gradient descent (SGD) in order to minimize the local loss function Fm (0). It then sends the local model update to the server, which aggregates the local updates from all the devices to update the global model.
B
D m= Bm, and
FL mainly targets mobile applications at the network edge, and the wireless communication links connecting these devices to the network are typically limited in bandwidth and power, and suffer from various channel impairments such as fading, shadowing, or interference; hence the need to develop an FL framework with limited communication requirements be- comes more vital. While communictiinn-cfiiient FL has been widely studied, prior works mainly focused on the Sevices-to-PS links, assuming perfect broadcasting of the global model to the devices at each iteration. In this paper, we design an FI. algorithm aiming to reduce the cost of both PS-to-device and devices-to-PS communications. To address the importance of quantization at the PS-to-device direction, we highlight that some devices simply may not have the sufficient bandwidth to receive the global model update when the model size is relatively large, particularly in the wireless setting, where the devices are away from the base station. This would result in consistent exclusion of these devices, resulting in significant performance loss. Moreover, the impact of quantization in the device-to-PS direction less severe due to the impact of averaging local updates at the PS.

---

Under review as a conference paper at ICLR 2021
Related work There is a fast-growing body of literature on the communication efficiency of FL targeting restricted bandwidth devices. Several studies address this issue by consid- ering communictiins with rate limitations, and propose different compression and quan- tization techniques Konecny et al. (2016); McMahan et al. (2017); Konecny & Richtarik (2018); Dowlin et al. (2016); Koneeny et al. (2015); Lin et al. (2018b); He et al. (2018); M. M. Amiri & Gündüz (2020), as well as performing local updates to reduce the frequency of communications from the devices to the PS Lin et al. (2018a); Stich (2019). Statisti- cal challenges arisc in FL since the data samples may not be independent and identically distributed (iid) across devices. The common sources of the dependence or bias in data distribution are the parlicipaling devices being located in particular geographic region, and/or at a particular time window P. Kairouz et al. (2019). Different approaches have been studied to mitigate the elfect of non-iid data in FL McMahan et al. (2017); Hsieh et al. (2019); Li et al. (2020a); Wang et al. (2020); Eichner et al. (2019); Zhao et al. (2018). Also, FL suffers from significant variability in the system, which is mainly due to the hardware, network connectivity, and available power associated with different devices Li et al. (2019). Active device selection schemes have been introduced to alleviate significant variability in FL systems, where subset of devices share the resources and participate at each iteration of training Kang et al. (2019); Nishio & Yonetani (2019); Amiri el al. (2020b); Yang et al. (2020; 2019). There have also been efforts in developing convergence guarantees for FL under various scenarios, considering iid data across the devices Stich (2019); Wang & Joshi (2019); Woodworth et al. (2019); Zhou & Cong (2018); Koloskova et al. (2020), non-iid data Koloskova et al. (2020); Li et al. (2020a); Haddadpour & Mahdavi (2019); Li et al. (2020c), participation of all the devices Khaled et al. (2020); Wang et al. (2019); Yu et al. (2018); Huo et al. (2020), or only a subset of devices at each iteration Li et al. (2020b); Karimireddy et al. (2020); Rizk et al. (2020); Li et al. (2020c); Amiri et al. (2020a), and FL under limited communicatin constraints Amiri et al. (2020a); Rocht et al. (2011); Alistarh et al. (2018).
FL with compressed global model transmission has been studied recently in Caldas et al. (2019); Tang et al. (2019) aiming to alleviate the communication footprint from the PS to the devices. The global model parameters are relatively fkewed/diverss and the efficiency of quantization diminishes significantly when the peak-to-average ratio of the parameters is large. To overcome this, in Caldas et al. (2019) the PS first employs a lincar transform in order to spread the information of the global model vector more evenly among its dimensions, and broadcasts a quantized version of the resultant vector, and the devices apply the inverse linear transform to estimate the global model. We highlight that this approach requires a relatively high computational overhead due to employing the linear transform at the PS and its inverse at. the devices, where this overhead grows with the size of the model parameters. Furthermore, the performance evaluation in Caldas et al. (2019) is limited to the experimental results On the other hand, in Tang et al. (2019) the PS broadcasts quantized global model with error accumulation to compensate the quantization error.
Our contributions With the exception of Caldas et al. (2019); Tang et al. (2019), the literature on FL considers perfect broadcasting of the global model from the PS to the devices. With this assumption, munication strategy is used, all the devices are synchronizod with the same global model at each itcration. In this paper, we instcad consider broadcasting quantized version of the global model update by the PS, which provides the devices with a lossy estimate of the global model (rather than its accurate estimate) with which to perform local training. This further reduces the communication cost of FL, which can be particularly limited for transmission over a wireless medium while serving a massive number of devices. Also, it is interesting to investigate the impact of various hyperparameters on the performance of FL with lossy broadcasting of the global model since FL involves transmission over wire- less networks with limited bandwidth. We introduce lossy FL (LFL.) algorithm, where at each iteration the PS broadcasts a compressed version of the global model update to all the devices through quantization. To be precise, the PS exploits the knowledge of the last global model estimate available at the devices as side information to quantize the global model update. The devices recover an estimate of the current global model by combin- ing the received quantized global model update with their previous estimate, and perform local training using their estimate, and return the local model updates, again employing
matter what type of local update or device-to-PS com-
2

---

Under review as a conference paper at ICLR 2021
quantization. The PS updates the global model after receiving the quantized local model updates from the devices. We provide convergence analysis of the LFL algorithm investigat- ing the impact of lossy broadcasting the MNIST and CIFAR-10 datasets illustrate the efficiency of the proposed LFI, algorithm. We observe that the proposed LFL. scheme, which leads significant commuiccation cost saving, provides promising performance with no visible gap to the performance of the fully lossless scenario where the communication from both PS--to-dvvie and device-to-PS directions is assumed to be perfect. Also, it is illustrated that the proposed LFL scheme significantly outperforms the schemes introduced in Caldas et al. (2019) and Tang et al. (2019) considering compression from the PS to devices.
the performance of FL. Numerical experiments on
The proposed I.FL, algorithm differs from the approaches in Caldas et al. (2019); Tang et al. (2019), since we propose broadcasting the global model update, with respect to the previous estimate at the devices, rather than the global model itself. We remark that the global model update has less variability/ Aaallityyvvriiaa /variance and peak-to-average ratio than the global model (see Figure 2), and hence, for the same communication load, the devices can have a more accurate estimate of the global model. However, this would require all the devices to track the global model at each iteration, even if they do not participate in the learning process by sending their local update. We argue that broadcasting the global model update to the whole set of devices, rather than a randomly chosen subset, would introduce limited additional communication cost as broadcasting is typically more efficient than sending independent information to devices. Moreover, in practice, the subset of participating devices remain the same for a number of iterations, until a device leaves or joins. Our algorithm can easily be adopted to such scenarios by sending the global model, rather than the model update, every time the subset of devices changes. Also, compared to the approach in Caldas et al. (2019), the LFL algorithm requires significantly smaller computational overhead. Furthermore, unlike Caldas et al. (2019), we provide an in-depth convergence analysis of the proposed LFL algorithm. The advantage of the proposed LFL algorithm over the approaches introduced in Caldas et al. (2019); Tang et al. (2019) is shown numerically, where, despite its significantly smaller communication load, it provides considerably higher accuracy.
Notation The set of real numbers is denoted by R. For x E R, |x| returns the absolute value of x. For a vector of real numbers x, the largest and the smallest absolute values among all the entries of x: are represented by max [ and min [|æ]}, respectively. For an integer i, we let [i] f1,2,..., The no-m of vector æ is denoted by |xl||--
2 LOSSY FEDERATED LEARNING (LFL) ALGORITHM
We consider a lossy PS- de-voce transmission, in which the PS sends a compressed version of the global model to the devices. This reduces the communication cost, and can be particularly beneficial when the PS resources are limited, and/or communication takes place over a constrained bandwidth medium. We denote the estimate of the global model O(t) at the devices by O(t,, where t represents the global iteration count. Having recovered @(t), the devices perform r-step SGD with respect to their local datasets, and transmit. their local model updates to the PS using quantization while accumulating the quantization error.
2.1 GLOBAL MODEL BROADCASTING
In the proposed LFL algorithm, the PS performs stochastic quantization similarly to the QSGD alm introduced in Álistarh et al. (2017) with slight modification broadcast. the information about the global model to the devices. In particular, at global iteration t, the PS aims to broadcast the global model update 0(1) - O(t- (1) 1) to the devices. We present the stochastic quantization technique we use, denoted by -(,,), in Appendix A.
Lemma 1. For the quantization function yp (x, q) and vector Q(x, q) given in (21b) and (22), respectively, we have
Ep (o(((,))) = x.
Ex x) =x² + 1/(49")
(1a)
Ex [({x)))) =x, Ex (2( 1 S ||l| + ed ||]|
+ed
/
(1b)
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 LFL
1: for t= 0....., T do
Global model broadcasting
2: PS broadcasts (()(1) 0(1
-1--)) 1).
3: 0(1)= = ( - 1) Q( -(,-)),,))
Local update aggregation
4:
for m ....., .M in parallel do
5: Device transmits Q(S0m. + (8), 92) Q(0 @(t) + (t).
6: end for
7: (t 1) = (t) EM
Bm Q (t) + 6m (t).92)
B
8:
end for
where Ep represents expectation with respect to the quatization function &p (r:),, and 0 S 1 is defined as A (max {|0]} min {|=13)²² /|al|/
The proof of Lemma 1 is provided Appendix B. We highlight that the value of depends on the skewness of the magnitudes of the entries of where it increases for more skewed entries with a higher variance. We have O, if and only all the entries of a have the same magnitude, and e if and only if æ has only non-zero entry.
Given quantization level @i, the PS broadcasts Q(((() 0( 1), to the devices at global iteration t. Then the devices obtain the following estimate of O()):
(t) = O(t - 1) + ( - O(t - 1).
(2)
which is equivalent to 0(t) ((0) - (0(1)) 0 1),4), where assumed that @(0) = 0(0). We note that, having the knowledge of the compressed vector Q( 0(i
1), vi E [t], the PS can also track Ō()) at each iteration.
2.2 LOCAL UPDATE AGGREGATION
After recovering (t), device m performs a T-step local SGD, where the i-th step corresponds
to (1) = 0 (4) n/ FL.. (0%,()) (t), st (4), i E [7]. where 01 (1)( θ(), and etm (t) denotes the local mini-batch chosen uniformly at random from the local dataset B,n It
then aims to transmit local model update (t) O,* (t) -(t) through quantization with error compensation and transmits Q (t) 5m (t), 92) using quantization level 42, where (l) relains the quantization error, and is updated
5m (t + 1) = A6, (t) + 8m (t) - Q (2 (t) + 8, (t), 42).
(3)
where we set 6m (0) = O. Having received (100m + 6m (1), ()) from device m,, Vm E [M], the PS updates the global model as
Σ M
Bin Q(20m( 5m (t).
@
θ(t)
(4)
m=1
Algorithm 1 summarizes the proposed LFL algorithm.
Remark 1. We do not consider error compensation at the PS with LFL since we have ob- served performance degradation numerically when compensating the quantization error at the PS. We argue that LFL naturally accumulates the quantization error al the PS since il sends the quatized global model updale with respect lo the last global model estimale at the devices. We further highlight that the proposed approach is not limited to any specific quantization technique, and any compression technique can be used within the proposed framework.
3 CONVERGENCE ANALYSIS OF LFL ALGORITHM
Here analyze the convergence behaviour of LFL, where for simplicity of the analysis, we assume that the devices can transmit their local updates, A0... (t), Vm, accurately /in lossless fashion to the PS, and focus on the impact of lossy broadcasting the convergence.
4

---

Under review as a conference paper at ICLR 2021
3.1 PRELIMINARIES
We denote the optimal solution minimizing loss function F(0) by 0" and the minimum loss as F", i.e., 0r _ arg ming F(0), and F - F(0"). We also denote the minimum value of the local loss function at device by Pm- We further define r - ---> -m m== B O, and its magnitude indicates the bias in the data distribution across devices.
Bm F where
For ease of analysis, set T/m (t) ntt). Thus, the i-th step SGD at device m is given by (t) 0% (t) (tt (t, (t)) i [7], E [M],
(5)
where 0% = (1), given in (2). Device m transmits the local model update
(0 -h (t) (t) (t)) Σ Vm (0tm(t), (t), (n))))
m [M],
(6)
and the PS updates the global model
( + 1) = 0(t) ntt) Σ m=1
Bm VF (t) :=1 B
(7)
Assumption 1. The expected squared 12-norm of the stochastic gradients are bounded, i.e.,
Bg V (0 (t), em (t) S G Vi [m) Vm [M], Vt.
(8)
Assumption 2. The loss functions F1,...,FF are L-smooth; that is, Vu, w E R
2(Fm(()) Fm(()) S 2/0 (Fm(w)) L Lll w1l Vm E [M.
(9)
3.2 STRONGLY CONVEX Loss FUNCTION
Here we provide convergence analysis assuming that the loss functions Fi...., FM are p- strongly convex; that is, Vu, w E Rd,
(V) Fm (w)) 2 2(v w, (F)(w)) + p | w1/2 Vm E [M].
(10)
In the following theorem, whose proof is provided in Appendix C, we present the convergence rate of the LFL algorithm assuming that the devices can send their local updates accurately.
Theorem 1. Let 0 < (t) min {1, pr }, Vt. We have
E [[ 1-]]] S A(1) (10(0) 1-11
Σ j=0
B BL 1=j+1
A(),
(11a)
where
A(1) Ε pn(i) (T n()((T - 1)),
(11b)
B(1) & (1 - (n((i (r - n(i((T 1))) mi (
1)TG 2
sd + 7 -
2q1
+ + (1+ 111 ((1) 12 (()) T(T 1)((T 12 2n(
(11c)
for some 0 <ES1, and the expectation is with respect the stochastic gradient function and stochastic quantization.
Corollary From the I.-smoothness of the loss function, for < n1(1) S min {1, } VI, and a total of T global iterations, it follows that
L
E [[F(O(T)) - F* S
(T) 101
A(i) |1((0) 0 -
L Σ B(i) [= A(). (12)
where the last inequality follows from (11a). Considering r7()) = and 1, we have
[F F. s " ((00) 0-3
+ レ/4 (1 jmm
Ed
+ (1 - (1 - (m)) (3))
(13)
z
5

---

Under review as a conference paper at ICLR 2021
Asymptotic convergence analysis Here we show that, for decreasing learning rate over time, such that lim,-+00 n]() = 0, and given small enough E, limy-+2o E [F - = 0. For 0 < nt) I min (1, 1 }, we have 0 S A(t) < 1, and limy-+x I[ A(i) = 0. For simplicity, assume sT(()= 843> for constant values a and B. For j >> 0, B(j) + 0, and for limited j values, M A(i) 0, and so, according to (12), lim EE (F(((T))) - F 0.
ur
3.3 NON-CONVEX Loss FUNCTION
Next, we provide convergence guarantees of the proposed LFL scheme for L-smooth and non- convex loss functions Fi....,FF FMr For the non-convex case, we provide a weaker notion of convergence Liu & Wright (2015) lim El [[) + 0. In the following theorem, we bound 1 T(2) ErD (() with the proof provided Appendix F.
Theorem 2. Performing the LFI. algorithm for T 2 1 global iterations assuming that the PS receives the local model updates accurately leads to
T-1 Σ
2 F*)
2r
Ei=0 (tt) t=
Et- (t)
Et= n(t)
n1(t 1)G
(n(t)(2T - 1)L + 2)
nt)) 1=0
2q1
==
Σ (t)
+ +L'G - -T 11) ET (t)
2G 2 TL
(14)
Σ (t))
3 3 (t)
Choice of in inequalities (45), (63), in which we have
We highlight that e appears in the convergence analysis of the LFL algorithm
E maxx {
Σ M
Bu Fm (0 (t 1), 1), (t 13) }
m=1
B
Σ
Bm
Fm (0 (t 1), (t 1)) [
min
iiml
B
M
B Fm (0in Eth (t 1)) [
I =E
(15)
i=1
B
which follows from (26b), where we note that
0(1) - 1) -nn(t 1) Σ M E
Bm (0 (t- 1) 1)) i=1 B
(16)
On average the entries of -(t)- 1), given in (16), are not expected to have very diverse magnitudes. Thus, the inequality in (15) should hold for a relatively small value of e. We
have observed numerically that & R 10 satisfies inequality (15) for the LFL algorithm.
Impact of number of local SGD steps For the non-convex case, assuming nT(t) n, Vt, it is easy to verify that the upper bound on 7 -TT [[ given in Theorem 2, is simplified as follows:
N(T) a-1
ag + 01 + 0272
(17)
T
where
((F(0) F +T+
Go A L2
a
T/T
3
a1 A (2 - TT. TTT)TT.G22 nT.nII.c((1
sd
02 a 1
ed
(18)
4
2q
We have dh(r)/dr= = -a 72 + +a + 202T, where we note that a + 20² 2 0. For relatively
small a-1 values, particularly a S an + 2az, h(7) increases with v, and T 1 minimizes
6

---

Under review as a conference paper at ICLR 2021
Table 1: CNN architecture for image classification on MNIST and CIFAR-10.
MNIST
CIFAR-10
3 convolutional layer, 32 channels, ReLU activation, same padding
3 x 3 convolutional layer, 32 channels, ReLU activation, same padding
3 x convolutional layer, 32 channels, ReLU activation, same padding
2 x 2 max pooling
dropout with probability 0.2
3 x 3 convolutional layer, 64 channels, ReLU activation, samne padding
3 x 3 convolutional layer, 64 channels, ReLU activation, same padding
3 x 3 convolutional layer, 64 channels, ReLU activation, same padding
max pooling
dropout with probability 0.3
3 convolutional layer, 128 channels,
3 x 3 convolutional layer, 64 channels, ReLU activation, same padding
ReLU activalion, same padding
3 x convolutional layer, 128 channels,
ReLU activation, same padding
2 x 2 max pooling
fully connected layer with 128 units, ReLU activation softmax output layer with 10 units
dropout with probability 0.4
M(T); that is, when the training is started close to the optimal solution (F(0) relatively small), and/or v is relatively large, 7 may be the best choice. On the other hand, for relatively large a-1 values, the best can be the nearest integer to the positive solution of (a1 + 2027)r² a-1=
NUMERICAL EXPERIMENTS
Here we investigate the performance of the proposed LFL algorithm for image classification on both MNIST LeCun et al. (1998) and CIFAR-10 Krizhevsky & Hinton (2009) datasets utilizing ADAM optimizer Kingma & Ba (2017). We consider M = 40 devices, and mea- sure the performance as the accuracy with respect to the test samples, called test accuracy.
Network architecture We train different convolutional neural networks (CNNs) with MNIST and CIFAR-10 datascts. The architectures of these CNNs are described in Table 1.
Data distribution We consider two data distribution scenarios. In the non-iid scenario, we split the training data samples with the same label (from the same class) to M/10 disjoint subsets (assume that M is divisible by 10). We then assign cach subset of data samples, selected at random, to a different device. In the iid scenario, we randomly split the training data samples to M disjoint subsets, and assign each subset distinct device. We consider non-iid and iid data distributions while training using MNIST and CIFAR-10, respectively.
State-of-the-art approaches We consider two approaches with lossy broadcasting intro- duced in Caldas et al. (2019) and Tang el al. (2019) as the state-of-the-art approaches. With the scheme in Caldas et al. (2019), referred to as lossy transformed global model (LTGM), the PS first employs a linear transform to project the global model. It then quantizes the resultant vector after the linear transform, and sends the quantized vector to the devices. The devices employ the inverse of the lincar transform and use the recovered vector for local training. As suggested in Caldas et al. (2019), we consider Walsh- Hadamrd trans- form and employ the stochastic quantization scheme presented in Appendix A at the PS. On the other hand, with the approach studied in Tang et al. (2019), referred to as lossy global model (LGM), the PS directly quantizes the global model plus the quantization error accumulated from the previous iterations and shares the quantized global model with the devices, while updating the qunatization error. For fairness, consider the quantization
7

---

Under review as a conference paper at ICLR 2021
09
0.
Fuly touisss 1=5
15 0.4
0.
Fully lasiem, t-4
Test
(5.3)
LB,
L-4
0.-
T
0.1
50
100
250
200
235
200
250
400
5
120
200
200
400
500
000
700
Global Feration count,
Global iteration count,,
(a) MNIST with non-iid data
(b) CIFAR-10 with iid data
Figure 1: Test accuracy using MNIST and CIFAR-10 for training with local mini-batee size
S (t) = 500 and (1) = 250, respectively.
scheme presented in Appendix A with the LGM scheme, and assume the same technique for transmission in the device-to-I'S direction introduced in Section 2.2.
Benchmark approaches We consider the performance of the lossless broadcasting (LB) scenario, where the devices receive the current global model accurately, and perform the quantization with error compensation approach as described in Section 2.2. We highlight that this approach requires transmission of RLB 33d bits from the PS, where we assume that each entry of the global model is represented by 33 bits. Thus, the saving ratio in the communication bits of broadcasting from the PS using LFL versus LB is
RLB RQ
33d
33
(19)
64 + d1 logg(1 + 1)) 1+ log2(11 + +1)
where (a) follows assuming that d >> 1. We further consider the performance of the fully lossless approach, where in addition to having the accurate global model at the devices, we assume that the PS receives the local model updates from the devices accurately.
In Figure 1 we illustrate the performance of different approaches for non-iid and iid scenarios using MNIST and CIFAR-10, respectively, for training with M = 40 devices. Figure la demonstrates test accuracy of different approaches for non-iid data using MNIST with local mini-batch size |5% (1) 500 and number of local iterations the approaches where the devices perform quantization, and Q1 = 2 for the LFL, and LGM schemes. We observe that the proposed LFL algorithm with (q1. 92) = (2, 2) performs
4. We set q2 2 for all
well as the fully lossless and LB approaches, despite a factor of 12.77 savings in the number of bits that need to be broadcast compared to the LB approach. This illustrates the efficiency of the LFL algorithm for the non-iid scenario providing significant communication cost savings without any visible performance degradation. On the other hand, the performance of the LGM algorithm drops after an intermediate number of training ilerations, which shows that the quantization level y1 = 2 does not provide the devices with an accurate estimate of the global model to rely on for local training. This is particularly more harmful in later iterations as the algorithm approaches the optimal point where a more accurate estimate of the global model is required for training. We highlight that the proposed I.F. algorithm resolves this deficiency with the LGM algorithm through quantizating the global model update rather than the global model providing more accurate estimate of the global model to the devices even with relatively small quantization level Qi = 2. Throughout our experiments, we found that the random lincar transform with the LTGM scheme is not highly efficient in providing a transformed vector with a relatively small peak-to-average ratio, and the quantization level qi should be relatively large to guarantee that the algorithm succeeds in learning. Therefore, we set @1 = 50 for the LTGM scheme, which is a relatively large quantization value. The advantage of the proposed LFL algorithm over the LTGM and LGM algorithms for the non-iid scenario can be clearly seen in the figure.
A similar observation is made in Figure 1b illustrating the perforance of different approaches for iid data using CIFAR-10 10 with local mini-batch size s (4) 250 and number of local iterations - = 5. The the LFL algorithm with (q), (2) = (5, 3) provides x9.2 smaller com- munication load compared to LB with 92 without any visible performance degradation
8

---

Under review as a conference paper at ICLR 2021
10
13
avorage ratio
10"
10"1
Emprical variance
10"1
Emprical
10
10
30
10a1
50
100
252
200
230
300
150
400
0
20
303
25.
200
232
302
250
400
Global Reration count,
Global Iteration count,
(a) MNIST with non-fid data
(b) CIFAR-10 with iid data
Figure 2: Empirical variance and peak-to av-arage ratio of the vector quantized at the PS.
with respect to the fully lossless and LB approaches. It also significantly outperforms the LGM algorithm with (9,,2) 3), which shows the advantage of quantizing the global model update rather than the global model for iid data. We also observe that the accuracy level of the LTGM algorithm drops significantly after around 200 global iterations even for a large quantization level
1000, which shows the deficiency of the linear transform to provide a relatively small peak-to-avere ratio for the transformed vector.
In Figure 2, we investigate the empirical variance and the peak-to-aveed to-arerage ratio of the vector (considering absolute values of its entries) be quantized at the PS with different schemes for the experimental scttings used in Figure 1. This result is provided to better justify the benefits of the proposed LFL scheme over LGM and LTGM shown in Figure 1. We observe that the global model update, which is quantized at the PS with LFL, has significantly smaller empirical variance than the global model, which quantized at the PS with LGM. This justifies the improvement of LFL over LGM reflecting smaller quantization error when quantizing the global model update rather than the global model, particularly towards the end of training, where the empirical variance of the global model with LGM has an increasing trend over time. Also, both the empirical variance and the peak-to-average ratio of the transformed vector with LTGM increascs over time, particularly for training on CIFAR-10. This illustrates that the quantization error increases with time, which may be more harmful towards the end of training while approaching the optimal solution. We note that the relatively small empirical variance of the transformed vector with LTGM is due to the linear transform applied at the PS which scales down the entries of the global model vector. The relatively large peak-to-average rat indicates that the quantized vector with LTGM may not provide an accurate estimate of the actual transformed vector at the PS.
5 CONCLUSION
FL demanding in terms of bandwidth, particularly when deep networks with huge numbers of parameters are trained across large number of devices. Communication is typically the major bottleneck, since it involves iterative transmission over a bandwidth-limited wireless medium between the PS and a massive number of devices at the edge. With the goal of reducing the communication cost, we have studied FL with lossy broadcasting, where, in contrast to most of the existing work in the literature, the PS broadcasts compressed version of the global model to the devices. We have considered broadcasting quantized global model updates from the PS, which can be used estimate the current global model at the devices for local SGD iterations. The PS aggregates the quantized local model updates from the devices, according to which it updates the global model. We have derived convergence guarantees for the proposed LFL algorithm to analyze the impact of lossy broadcasting on the FL performance assuming accurate local model updates Numerical experiments have shown the efficiency of the proposed LFL algorit hmm in providing an accurate est imate of the global model to the devices, where it performs as well as the fully lossless and LB approaches for both non-iid and iid data despite the significant reduction in the communication load. It also significantly outperforms the LTGM Caldas et al. (2019) and LGM Tang et al. (2019) algorithms studying compression in the PS-to-device direction thanks to quantizing the global model update rather than the global model at the PS.
the PS.
9

---

Under review as a conference paper at ICLR 2021
REFERENCES
D. Alistarh, D. Grubic, J. Z. Li, R. Tomioka, and M. Vojnovic. QSGD: Communcattion efficient SGD via randomized quantization and encoding. In Advances in Neural Infor- mation Processing Systems (NIPS), pp. 1700-1720, Long Beach, CA, December 2017.
D. Alistarh, T. Hoefler, M. Johansson, S. Khirirat, N. Konstantinov, and C. Renggli. The convergence of sparsified gradient methods. [Online]. https://an http:///rvvvvrrrr wtt/pd///////ee/eo 180f///0....// 10505. pdf, September 2018.
M. M. Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor. Convergence of up- date aware device scheduling for federated learning at the wireless edge. [Online]. cttps://arrion org/ ppfpp201.11..////1 1040000002.00.011000000000000000 pdf, May 2020a.
M. M. Amiri, D. Gündüz, S. R. Kulkarni, and H. V. Poor. Update aware device scheduling for federated learning at the wireless edge. In Proc. IEEE International Symposium on Informalion Theory (ISIT), Los Angeles, CA, USA, June 2020b.
S. Caldas, J. Konecny, H. B. McMahan, and A. Talwalkar. Expanding the reach of lederated learning by reducing client resource requirements. [Online]. hllps:/ /ttp:///wrrvvooo ww/pp//////////// /81 2.07210.ppp. January 2019.
N. Dowlin, R. Gilad-Bachrach, K. Laine, K. Lauter, M. Naehrig, and J. Wernsing. Cryp- toNets: Applying neural networks encrypted data with high throughput and accuracy, In Proc. International Conference on Machine Learning (ICML), pp. 201-210, New York, NY, USA, 2016.
H. Fichner, T. Koren, H. B. McMahan, N. Srebro, and K. Talwar. Semi-cyclic stochastic gradient descent. [Online].
http://wrwvvv/////ee/ 10111994411..0 10120.pd] pdf. April 2019.
F. Haddadpour and M. Mahdavi. On the convergence of local descent methods in federated learning. [Online]. https://arai https///rriioorr./ wtt.f//990.... y5 December 2019.
Lie He, An Bian, and Martin Jaggi. COLA: Decentralized linear learning. In Proc. Confer- ence on Newral Information Processing Systems (NeurIPS), Montreal, Canada, 2018.
K. Hsieh, A. Phanishayee, O. Mutlu, and P. B. Gibbons. The non-lID data quagmire of decentralized machine learning. [Online]. haaps:///rriuoryy http:////111100010000 December 2019.
Z. Huo, Q. Yang, B. Gu, L. Carin, and H. Huang. Faster on-device training using new federated momentum algorithm. [Online]. httpss//rrii.on//////0000..00000 hptf/2002.020000000 February 2020.
J. Kang, Z. Xiong, D. Niyato, H. Yu, Y.-C. Liang, and D. Kim. Incentive design for efficient federated learning in mobile networks: A contract theory approach. In Proc. IEEE VTS Asia Pacific Wireless Communications Symposium (APWCS), pp. 1-5, Singapore, August 2019.
S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. [Online]. htlps:///rrts
wwtpoo////pp////ee/ http///990000000 10000000.....pp. pdf, February 2020.
A. Khaled, K. Mishchenko, and P. Richtarik. First analysis of local GD on helerogeneous http//dff9990...// 1909 04715.ddf. pdf, March 2020.
data. [Online]. https:/ http///rriioooro// wrtppdf/
D. P. Kingma and J. Ba. Adam: A method for stochastic optimization. arXtv:1412.69880 LG), January 2017.
A. Koloskova, N. Loizou, S. Borciri, M. Jaggi, and S. U. Stich. A unified the- ory of decentralized sgd with changing topology and local updates. [Online]. htlps://wrzzv..r wwteivv.ogg//ffffee pdf//20332000.//// 100003.1042220 10422.pdf, March 2020.
10

---

Under review as a conference paper at ICLR 2021
J. Konecny and P. Richtarik. Randomized distributed mean estimation: Accuracy vs com- munication. Prontiers in Applied Mathematics and Statistics, 4, December 2018.
J. Konecny, B. McMahan, and D. Ramage. Federated optimization: Distributed optimiza- tion beyond the datacenter. arXiv:1511.03577 [cs.LG], November 2015.
Konecny, H. B. McMahan, F. X. Yu, P. Richtarik, T. Suresh, and D. Bacon. Federated learning: Strategies for improving communication efficiency. In Proc. NIPS Workshop on Private Multi-Party Machine Learning, Barcelona, Spain, 2016.
A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. In Technical Report, University of Toronto, 2009.
Y. LeCun, C. Cortes, and C. Burges. The MNIST database of handwritten digits. rezdb/mnist/, 1998.
T. Li, A. K. Sahu, A. Talwalkar, and V. Smith. Federated learning: Challenges, methods, and future directions. [Online]. https:// /arivv. org/pdf/ po0f/190.. 00880007.77.. 0d87..pdf. August 2019.
T. Li, A. K. Sahu, M. Zahoer, M. Sanjabi, A. Talwalkar, and V. Smith. Federated opti- mization in heterogeneous networks. [Onlinej. hilps:/ harpss///rii..aa/ wrg/pd//1812/ 06120.01.... April 2020a.
T. Li, A. K. Sahu, M. Zaheor, M. Sanjabi, A. Talwalkar, and V. Smith. FedDANE: A federated newton-type method. jOnline]. https://arriv.on/ htt/a/riiiii///o/////// org/ http/ddf220011 http///....11..../.... 01920.pdff, January 2020b.
X. Li, K. Huang, W. Yang, S. Wang, and Z. Zhang. On the convergence of FedAvg non-IID data. [Onlinej. https:/ hat/////rvvvu//e wwtpti///ggp/df////e// 190009209719999 pdf, February 2020c.
T. Lin, S. U. Stich, and M. Jaggi. Don't use large mini-batchen batches, use local SGD. [Online]. htips:///rriv wwt..oggg//pll htt//df//1// 11888.0781..771 October 2018a.
Y. Lin, S. Han, Mao, Y. Wang, and W. J. Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. wrXiv:171..0188/0 CVs. February 2018b.
J. Liu and S. J Wright. Asynchronous stochastic coordinate descent: Parallelism and con- vergence properties. STAM Journal Oplimization, 25(1):351-33) 376, 2015.
M. M. Amiri and D. Gündüi. Machine learning at the wireless edge: gradient descent over-the-air. IEEE Transaclions on Signal Processing, 68:2155 2169, April 2020.
Distributed stochastic
H. B. McMahan and D. Ramage. Fedorated learning: Collaborative machine learning with- out centralized training data. https://wuut www.w//wwwwwoo....ooo. com https/cccooooooeeeeeee fedderrtee-aarmiiggcollllaeaee machine-learning hatiiiie--erriiiinnniill-o-----e
April 2017.
H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas. Communication- efficient learning of deep networks from decentralized data. In Proc. AISTATS, 2017.
T. Nishio and R. Yonetani. Client selection for federated learning with heterogeneous re- sources in mobile edge. In IEEE International Conference on Communications (ICC), pp. 1-7, Shanghai, China, May 2019.
P. Kairouz et al. Advances and open problems in federated learning. https://orziu. org/pd/ htdp//91.00497..p0 pdf, December 2019.
[Online].
B. Recht, Re, S. Wright, and F. Niu. Hogwild: A lock-free approach to paralleliv- ing stochastic gradient descent. Tn Advances in Neural Information Processing Systems (NIPS), pp. 693-701, 2011.
E. Rizk, S. Vlaski, and A. H. Sayed. Dynamic federated learning. https:// /wtp///.orr///////00000 08702 pdf, May 2020.
[Online].
11

---

Under review as a conference paper at ICLR 2021
S. U. Stich. Local sgd converges fast and communicates little. https:// https://arziv... wttpp//ggg////eeeee 1tt//180500000 0.00..9700 09767.777770 pdf, May 2019.
[Online].
H. Tang, X. Lian, C. Yu, T. Zhang, and J. Liu. DoubleSqueeze: Parallel stochastic gra- dient descent with double-pass error-compensated compression. In Proc. International Conference on Machine Learning (PMLR), Long Beach, CA, 2019.
J. Wang and G. Joshi. Cooperative SGD: A unified framework for the design and analysis of communication-offiien sgd algorithms. [Online]. https://arziu. org/ org/pdf/ 1808. 1800007788..66... pdff January 2019.
S. Wang. T. Tuor, T. Salonidis, K. K. Leung, C. Makaya, T. He, and K. Chan. Adaptive federated learning in resource constrained edge computing systems. 1EEE Journal on Selected Areas in Communicatiins, 47(6):1205-1221, June 2019.
T. Wang, J.-Y. Zhu, A. Torralba, and A. A. Efros. Dataset distillation. [Online]. https://aran wtggpd/////// 1ttf//811../. 1.959....pp. February 2020.
B. Woodworth, J. Wang, A. Smith, H. B. McMahan, and N. Srebro. Graph ora- cle models, lower bounds, and gaps for parallel stochastic optimization. [Online]. httts://arziun org/pd// 1805. 10222. pdf, February 2019.
H. H. Yang, A. Arafa, T. Q. S. Quek, and H. V. Poor. Age-based scheduling policy for fed- erated learning in mobile edge networks. [Online]. Allps://urriin org/ http//df111/1/ 191..11111....888. 14648.pdf October 2019.
H. H. Yang, Z. Liu, T. Q. S. Quek, and H. V. Poor. Scheduling policies for federated learning in wireless networks. IEEE Transactions on Communications, 68(1):317-333, January 2020.
H. Yu, S. Yang, and Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. [Online]. https://arziv. wtt/pdf/////// 000.000......... 06629.ddf), November 2018
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Fed- erated learning with non-lID data. arXiv:1806. 00582 [es, June 2018
F. Zhou and G. Cong. On the convergence propertics K-step averaging stochastic gradi- ent descent algorithm for nonconvex optimization. In Proc. International Joint Conference on Artificial Intelligence (IJCAI), pp. 3219 3227, Stockholm, Sweden, July 2018
12

---

Under review as a conference paper at ICLR 2021
A
STOCHASTIC QUANTIZATION
Given a E Rd with the i-th entry denoted by 24, we define
Fmax - max { |
(20a)
Tmin - min [
(20b)
Given quantization level y 2 1, we have (z.. 9) - sign (a:) (Imin + (Fmax 2min) up
|m:] Tmin
9)) for E [d].
(21a)
Zmax - Fmin
where ((:,-) is a quantization function defined in the following. For 0 S x - and q 1, let I 10,1,.... - If be an integer such that x E (1/q, (1 1)/2). We then define
[1/9.
with probability (xg 1),
(xx 2
(21b)
1 (1 1)/4,
with probability zq - 1.
We define
Qxx, q) & [Q(z1, Q(aa,
(22)
and we highlight that it is represented by
RQ = 64 (1 + loga 4 + 1)) bits,
(23)
where 64 bits are used to represent, Tmax and Tmin; d bits are used for sign(z;), Vi E [d],
and d'log24 + 1) bits represent & (([2,] (/ - Tmin): q), Vi [d]. We note that
we have modified the QSGD scheme proposed in Alistarh et al. (2017) by normalizing the entries of vector æ with max Fmin rather than ||0||2-
B PROOF OF LEMMA
Given to (x, q) in (21b), we have
Es 1e(2, 4)1 -000=11 ( ( (1+1- xq) + ( (1+1) (xq - 1) = x.
(24)
Also, we have
Ep [e 0)] = (42 (1 + xΩq
11+1)²
11+12
2
(zq 1) = (-12
21xq xq -1
q
q²
1
(9)
2
q² (rq 1) (1 xq + 1)
x²
(25)
4q2
where (a) follows since (aq-- l) (1 - xq + < 1/4. According to (24), (25) and the definition
of Q(x, 7) given in (22), follows that
Ep [Q(x, 4)] = xc
(26a)
E. [ x 1)133 = Σe 1=1
E. [[Q(21 v)13 = (Xmax Fmin
Σ i=1 .1)
Epp
|2,| I Imin
Xmin .
Emax
dl min
20min (Xmax Xminn Σ
Eyp (
|1; Xmin
Fmax
Fmnin
Σ (Imax Fminn En
|0a|| Fmin
+
+ do
+ 2xmin
i=1 (|zg) - Fmin)
i=1
Tmax Fmin
49
(Imax Fminn
2
(c)
ed ||00|
||0|| 1222
lae 2 +
(26b)
4g²
4q
where (b) follows from (24) and (25), and (c) follows since (Xmax Fminn )² //|ax|
13

---

Under review as a conference paper at ICLR 2021
C PROOF OF THEOREM 1
We have
E 1) 11( 0' =E 0(1) | 0=1
[
+
Σ
M
Bm
10
m=1
B
((t) - 0r, >m
Bm
sln (1))
+ 2
(27)
In the following, we bound the last two terms on the right hand side (RHS) (27). From the convexity of 11-112- it follows that
E
Σ M
Bm 2m (1)
M
Bm
E
|
(1)1
m
B
2
mml
B
(t) Σ m=1
Bm
||E
VFm 0 (t), si.
B
S (1)T Σ
Bm
E
Vm (0 (1), (0))) (2)
(1)
(28)
m=1
i=1
B
where (a) follows from Assumption 1.
We rewrite the third term on the RHS of (27) as follows:
2 ((1)
0
M
Bm
A (0)
m=1
B
2t)
E
(0 - -((), Σ Vmn (1,,
m=1 B
Bm
2t(())
E
-0--0(t -O(t), V ( ctm (t))
mm1
B
+ 2n(1)
M
Bm
E 10- T(1, Σ 1=
Fm (l)
(29)
m=1
B
We have
Bm E (0' - -(1), V.... (111, ct (1))
(1) Σ m=1
()) 2n(t) Σ m=1
M
B E
(0" VF..
_ (t) Σ m=1
(6)
Bm
F' ('n(0)) - Fm. Fm. (0(1) - 5リ1 0(()) 0- 0011]]
B
2n(11) F E [((())]
"E [[00000) 0" |(]]
2
- (t)(t) 0( 0- []]
(30)
VFn.. (0% (t)), Vi, m, (b) is the result of assuming ptstrongly loss functions, and (c) follows since F* S F(O(t),, Vt.
where (a) follows since Eg [V (t), (t)
(t), (t))
Lemma 2. For 0 < T(11= 1, we have
(n((t) Σ M Bm E 10 - O(t), Σ VF, (t), ch (t)))
m=1 B
[0(t)) 0r [
$ (1-n) 1)E
+ (t) (T - G2 G2
2
((=+(11n(0)))(00 T(r 1)(27 ((-)))-77--1-11111111111---- 2n(()((T(())))) 1)r.
(31)
Proof. See Appendix D.
14

---

Under review as a conference paper at ICLR 2021
By substituting (30) and (31) in (29), it follows that
2B
(0(1) 0% Σ MM
m=1
Bm
20 (1)
B
S s-un(t) (t) 1)) ||((0) (0((t)--11 111 (t)
(1 + (11 1 (()))) ((=+ T(T
12 -1- (T 1)T,
(32)
which, together with the inequality in (28), leads to the following upper bound on 0 + 0011 when substituted into (27):
E [|0(( + 1) 1) 1 S1 -
|0(00 0- 2 + (1 p(1 - ((1 T(T 1)((T - 1)
+ (t) (72 + 1) G² G)
2
+ 2m((t) 1)r. (33)
6
Lemma 3. For 0(t) given in (2), we have
E |0000 or [ s E [10(t) 0'11]]
-
(n(t= - 1)TG 2
ed.
(34)
291
for some 0 1.
Proof. See Appendix F.
According to Lemma 3, the inequality (34) can be rewritten as follows:
E |0(t + 1) - 0'12]| s (1 un(()(( n(t((T - 1))) E 11((t) - 11
+ (1 - (t) (T - n()(T= - 1))) 11(1 (1(1 G)TG ) ed + (1) (r² + 1)
(t)
+ (1+ + p(1 - (())=(())))()))) 7(r 11) 27((t - 1)1'
(35)
6
Theorem 1 follows from the inequality in (35) having 0 < n()) < min 1, 1 μイ } Vt.
D PROOF OF LEMMA 2
We have
2n((t) Σ ΣM
Bm
E
10'
@t), Fm (0 (t), S'm (t))
m=1 B
1=
Bm
(T)
E
(0 m (t) Ott), Fm (0 (t), et. (t))
m=1
B
1=2
+ 21((() Emer
Bm
Σ
E [(0 0² (1), Fm (0 (1), et. (1))
(36)
B
We first bound the first term on the RHS of (36). We have
(1 Σ M
Bm
Σ
E
(0)
(0)())
(1)
@(), F... (0 (1), c. (0)) 1
B
2
M
Bm
0 (t) a(t) + nn(t)
V (0% (t), eh (t))
E
m=1
B
2
i=2
ntt)
M
Bm
E
|
|0]
+ (T) 11
(37)
m=1
B
1=2
15

---

Under review as a conference paper at ICLR 2021
where (a) follows from Assumption 1. We have
Σ m=1
M
B
E
0 (t)
0(1)
B
2=2
Bm
E
Σ
j=1
21 (6) F (4,, (2)
S
12 (1)G) 7(5 - 1)(27 1)
(38)
where (b) follows from the convexity of 1-112 and Assumption yields
Plugging (38) into (37)
(t)
M m=1
Bin
(0t(()) 0tt) F. (t), (t),
1=2
S 51 1) -
T(T
(39)
For the second term on the RHS of (36), we have
M Bm
(t(()
E
[00
On (t), Vm (0 (t), (0))
m=1 B
1=2
(2)
(l)
M
B
m
E [000 0% (1), VI,,. (0 (1)))
mml
B
im2
S 2n(t)
Bm
E
Fm (0)) Fm m (t))
4 e (t) 1-
m=1 B
i=2
2
2n())
Bm
E
F' (0")
F* + F*t
Fm (0 (t))
/ 110 (t) 00
m=1 B
i=2
2n(()(T 1)T (1)
Σ
M
Bm
Σ (F= E Fm (0th (t)))
m=1
B
i=2
-mi(!) Σ MM Bin Σx
E
[110% (1)
01
2 2n(1)(T- - 1)r um(()) Σ M Bm Σ
Em
E
| (1)
0+ 1
(40)
Vm (0(t)), Vi,m, t; (b) follows from as- suming that the loss functions are u-strongly convex; and (c) follows since F S (0 Vm. We have
where (a) follows since Eg
Fv (t))
- 0l0 - 012 = - om((1) 000 |0(1- 0.1 2 2(00 - 0(1, 0(1) 0*)
(a) -
1 (1) - Ō(1) 2 |0() - 0- 1|= n(() 0 (1) - 8(1) 1| + n() 0(1) 0" 12
nt)) (0()) - o1. ((t)) - 1) |l0 0(t) |(
(41)
where (a) follows from Sahuchy-Schwaz. inequality. Plugging (41) into (40) yields
(t) M
Σ m=
Em E (0 0 (t), Vm (0 (t), (i,))))
| + 111 ((t)) T(T 1)(27 - 1) + 2n(t)(r - 1)r,
S - [(()) 0"
6
(42)
where we used the inequality in (38) and r7()) < 1. Plugging (39) and (42) into (36) completes the proof of Lemma 2.
16

---

Under review as a conference paper at ICLR 2021
E
PROoF OF LEMMA 3
We have
E
((1) 0-1 = E
(()
+ EE
00 1
2B (01), 07)
E
(
+ EE
0
2E (0(t) 0*)]
(43)
where (a) follows since
E
((t) =E
0 [(t-
+ [(((()) 0(t - ((t-1).9:) = - [[())),
(44)
where the last equality follows from (26a). In the following, upper bound E
0
We have
[0]
=R 0( 11[2] + I |00(000) - 0( 1), 1), |1]
E
((1)
2
+ 2E (0(1 ((1(((())))))))))))))))))))))()) 0(1 1), 21
[ 1/15] + + ||000 00 1)
s(t)d 4
101)-000
- 0 111
E
(0(1 1())(() - O( 17)}
+ 2E
[1000 + (t)(t)
ed
E (|o(e) A(t 1)
(45)
where (a) follows from (26) for some 0 S = - 1 defined
maxx { [(t) 0(t μ min { { - O( -
--1))
E
Et) A
(46)
[1()) 0(: 11122
E
noting that
M Bm Fm (0t - 1), St 1)).
@(t) - O( - -nn(t - 1)
(47)
B
m=1
and in (b) we define e maxx{=(t)). According (47), from the convexity of 11-112 it follows
that
E
|0000 0( -(1-1)11 1]]? < 11 1) ( < 72 1)
B m E
Vm (0% (t 1), St 1)) [
B
(48)
where (a) follows from Assumption 1. Accordingly, (45) reduces to
|000
| < EE [110)]]]] + (n( (n(--1)))) 1--G ed.
E
(49)
2q1
Substituting the above inequality into (43) yields
E
[(())
0-
1
< E
[
+ E
[100 21E
((0(t), 0 (n(t- - 1)TG
Ed
2
291
+ nn(t 1)TG ed.
((()) 0 12
(50)
29
17

---

Under review as a conference paper at ICLR 2021
F
PROOF OF THEOREM 2
According to the L-smoothness of the loss functions Fi,..., ,...., we have
F(O(L 1)) - F
0(1), VF(O(O)) + 10((+1) + -
(51)
In the following we bound the average of the two terms on the RHS of the above incquality.
Lemma 4. We have
(0 + 1) VF((()) (7(6- (((t-1)(G.) / ) (edd)())2r-1)
-1)
291
2
+ ? T(T - 1)(27-1) (T()T E
VF
(52)
6
Proof. See Appendix G.
Lemma 5. We have
1[] -) =2))))))))))))))))))))))) 2t) + ( (1-1)-Ga 2
2zd.
(53)
241
Proof. See Appendix I.
Substituting the results in Lemmas 4 and 5 into (51) yields
TF R |F(((())) < [ - [[ + 1))]) (nit-1)G) 2 (n(t) - + 2)=dTL+++++++ 2f
1)(2T - 1)
291
3
(54)
For any T, by summing the above inequality over t have
7()E |1
2 (F((())
-(((00)))(((((()))
n(t 1))) 2 (2)))
2q1
1=0
T-1
nt(t) + 1 - 1)(27 -
T
2G
L
Σ
Σ
(t).
(55)
t=0
t=
We bound the first term on the RHS of the above incquality as follows:
M
B B
< ((((0)) - Σ
m
m
M
Bm F. = F(O(0)) F* +r. (56)
F(O(0)) - F + F
B
Substituting the above results in (55) and dividing both sides of the incquality in (55) by Σi- n(!) complete the proof of Theorem 2.
18

---

Under review as a conference paper at ICLR 2021
G PROOF OF LEMMA 4
We have
[[(0(1+1) 1) - O(), VF(O(O)) - [[ - -(1) - + -0,
[B[(O(L + ((), VF((()))) B[(0()) (((0))))))
= 18(((t + 1) - ((t), V2(O(())) - ((((()) - 1) 0( 1), (F))
@ [[(( +1 - ((),, VF(O(()))
M T Bm Vm (0%)() VF(O()))
@ B (-n(t) Σ Σ
M
Bm BI VF (t). VF(O(t))) (57)
= nt (VF((())) VF(((()) - (7())
B
m=1
where (a) follows since E,p (0(
and the fact that O()) 0( 1) is indepen-
dent of the stochastic quantization Q()()) - Ō( - 1), and Eg [V FV (0 (t), S. (0)] =
V Fm ((i,())) Vi, m, results (b). We bound the first term on the RHS of (57) as follows:
(t) (FF(O(t), VF(O(())] = (tt)
E VF(O(t)) - VF(O
E VF((()))
2
- E = < 71())2²
E
[|(((t) - -
71()
[IFF
(58)
2
2
Lemma 6. We have
1)m0}² 2
E (1101)-000133)
ed.
(59)
2q1
Proof. See Appendix H.
Plugging (59) into (58) yields
s (nit= (nit- Pitt-INGL
) ((dn(())
2
n(t))
(t) E (
E
|
|
F
(((())))
291
2
2
(60)
The second term on the RHS of (57) is bounded as follows:
M
Bm
(()
Fm (0 ( VF(O())]
B
(t)
Σ
Bm
Fm (0t( - V
Σ
B Fm (0 (1) 1 [FF(
2
B
(1))
M
Bm
27 - E [[(FF((())1)] (v (0')())) VF... (0(1))
Σ
2
B
1=2
m=1
m1(()
M
Bm
((((T-))
(vFm (0) (1) - V (0())))
E
2
B
2
2
m=1
12
M ΣΣS
Bm
0 ())(1) 00011 n(t((T -1 1)
[
B
2
2
S <((() Σ
Σ
M
Bm
[10 m (1) 0(0)2 + +1(0(1= - 0(0113) n(t)(= 1)
||
2
1=2
TTT
1) 1) +
ntt (n(t-1))GH) 1)TGL "dn(()((- - 1) n(t)(T-1)
V (F((())
6
24
2
(61)
19

---

Under review as a conference paper at ICLR 2021
where (a) follows from the convexity of 1.112 and (b) follows from (38) and (59). Plugging
(60) and (61) into (57) yields
& (n(t= ( 2 (edn(t)(er-1))
-2)
241
2
+11(1))2? T( 1)((T - 11) n(t)T E
VF(0(() (62)
H PROOF OF LEMMA 6
We have
E
E||0(()
0(0) E
[[(()) 0(t - 1) Q((()) - 0(t 1).
E 0(1) O( - 1)|12] + ( A(t 1),
2E (0(t) - (tt-1).Q(0(1) 0( 1).
E ((t)) 0(t - ||][ + 10 - O(t - 11).
2
ed
(|(()) - 0( 1)1[2]
E
49
ed
E
Ilnt n((
1) Σ Σ
Bm VF m (0 (t 1), (t 1)) 1
4q
B
m=li i=1
n(t
1)TG
Ed,
(63)
24:
where (a) follows since (tt) - - 1) is independent of the stochastic quantization Q(
@ 11) and Ep [Q(x, 91)] æ, the second incquality in (1b) leads to (b), and (c) is the
result of the convexity of 11.112 and Assumption
I PROOF OF LEMMA 5
We have
E
[[10((+1) - [(011]] s 22 + 1) - 0(0112] + 2F [1000) - [001
(64)
For the first term on the RHS of the above inequality, we have
0( +1 [001 2E
M
Bn F
(0 (1), si. (t) |
2E
B
m=l
(t)r
B
(0 (t), (t,)))))))) [|] VF m
B
1 (t)
(65)
where (a) and (b) follow from the convexity of 11-112 and Assumption 1, respectively. Plugging (65) and (59) into (64) yields
) 2qi
1)TG 2
E (0(++))-00013) < 2
2ed.
(66)
20


Reviews:
[{"review_id": "dQdSdRZuyJ_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies federated learning with quantization. The problem setting is very standard, including both iid and non-iid cases. This work proposes a new algorithm, called lossy FL, to save the communication costs, especially from the broadcasting direction. To my understanding, the algorithm is new but still very similar to double-squeeze (Tang 2019). The presentation of the paper is generally good. However, there are several major issues regarding the quality and significance of this work.\n\n1. The convergence analysis is based on the assumption that the problem is strongly convex. But from the motivation of this work and numerical results, the problems would be nonconvex. The current analysis is restrictive.\n\n2. There is no analytic result of quantifying the upper bound of \\tau, which is one of the key differences between federated learning and distributed training. There are already many works there.\n\n3. The comparison with double-squeeze is definitely not fair, since the aggregation rule of the double-squeeze did not consider the \\tau step local update.\n\n4. The numerical results are very limited, where the CNN network is very small. There is no need to perform quantization for this neural net. Also, MNIST and CIFAR-10 are all small datasets. I don’t know why there were 40 devices used. To show the advantage of federated learning, the speed up in terms of the training time should be compared and plotted.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "LI--RzOIiBt", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the setting of Federated Learning, the authors propose to quantize both (1) the model send from PS to devices, and (2) the update from device to PS. Although the idea of model-broadcast-compression has appeared in previous work, the authors improve upon previous works in that (1) the authors propose to compress-and-send model updates instead of the model itself, which have smaller variance and peak-to-average ratio and therefore have more effective quantization compression, and (2) do not require pre-processing like linear transformation. The authors further show the effectiveness of their proposed algorithm, LFL, by offering a convergence analysis under appropriate conditions, and offering thorough experimental evaluations.\n\nPros:\n+ The authors show convergence results under the strong-convex and smooth condition, making this work more theoretically-grounded than previous related work.\n\n\nCons:\n+ I am not convinced that sending updates instead of sending models is a valuable idea.\nSending updates instead of sending models is definitely not a new idea in the quantization optimization community, but mostly from device to PS direction, and not the other way around. I believe there are some challenges or tradeoffs to do the PS-to-device directions, but the authors did not sufficiently address this in the paper. For example, two trade-offs that I would expect are, (1) now devices have more computation responsibility, but they are usually weak in computation and sensitive in power consumption, (2) we are essentially quantizing the updates twice (once from devices to PS, and once from PS to devices). This double quantization will inevitably lead to larger quantization variance, and therefore slower convergence of the model, especially when we are close to the end of the learning.\n\n\n+ The contribution is not clearly highlighted in the theory nor in the simulation.\nThe authors mention that \"in Tang et al. (2019) the PS broadcasts quantized global model ... Instead, we propose broadcasting the global model update ... We remark that the global model update has less variability/variance and peak-to-average ratio than the global model...\"\nThe authors indicate that, claimed improvements come from the fact that the model update has a smaller variance/peak-to-average ratio than the model.\nI believe that this intuition is important in terms of differentiating this work among all model-broadcast-compression works.\nHence I would expect the authors to conduct corresponding experiments, and corresponding highlights in the analysis, showing that the variance/peak-to-average ratio of model updates are indeed $c$ times smaller than the model itself, and the gain (e.g. reduction of communication cost, reduction of computation iteration) is proportional to $c$.\n\n+ The authors mention that \"(some devices might not be able to participate all learning iterates) ... Our algorithm can easily be adapted to such scenarios by sending the global model, rather than the model update\".\nI would recommend the authors conduct another set of experiments, maybe in the future, to take random devices join/drop-out into consideration. \nThere should be a join/drop-out probability thresholding, below which LFL is more efficient than the previous work, and above which LFL is less effective.\nThis would complete the picture of the 'scope' of LFL.\n\n+ The contribution section is way too lengthy. Probably move the second paragraph to the related work section.\n\n+ What is the architecture the authors used to conduct the experiments? And how the communication cost is evaluated?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "9DPZn9wK7TT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis paper suggests a lossy federated learning (LFL) algorithm where the PS broadcasts a quantized version of the global model to devices. This approach helps reduce the communication cost of federated learning and is in particular useful when the communication bandwidth is limited. Associated convergence analysis is given to present the effect of lossy broadcasting on the performance of federated learning. From experimental results, it is shown that the proposed algorithm with (q_1, q_2) = (2, 2) shows almost the same performance as the lossless schemes while enjoying a considerably reduced amount of communication bits.\n\nReasons for score:\nI vote for accepting. I totally agree with the importance and timeliness of this topic. My main concern is about the justification of the assumption and I hope that the authors can address this in the rebuttal.\n\nConcerns:\n- It would be better to explain the practical motivation behind the assumption that the devices transmit the lossless local updates to the PS focusing on lossy broadcasting only. For me, it is not clear how this assumption reflects the practical scenarios.\nIf the bandwidth of the communication channel between a device and the PS is limited by the amount that only can be achieved by quantization, can't we even do the iterations because the bandwidth required for device-PS communication exceeds the bandwidth limit for this channel?\n\n- For Figure 1, it would be better if some reasons could be presented that the performances of LGM and LTGM tend to change differently over iteration for non-iid and iid data. I think this would help to understand the strength of the proposed method.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6_RLg9BJxo", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In the paper, authors propose a novel quantization algorithm to reduce the communication cost between server and clients in federated learning, where the communication are limited and unstable. In their method, both the global model and\nthe local model updates are quantized before being transmitted. The authors also analyze the convergence of the proposed algorithm under certain conditions and execute federated simulations to evaluate it. Results show that the proposed algorithm converge as fast as the lossless broadcasting with no accuracy degradation. \n\nThe following are my concerns: \n1) In practice, it is not guaranteed that devices don't change in a certain amount of federated rounds. The proposed algorithm requires that the local devices have a good estimate of the global model, which is not true in real life. In this case, the server needs to send the global model to new devices. Since the target of the paper is to reduce the communication cost, the authors should perform experiments and investigate the effect of new participated devices. What is the upper bound of the new participated devices when this algorithm works better than other compared algorithms?\n\n2) It is better to show the convergence regarding the computational time and communication time.  \n\n3) There have multiple tasks more difficult than EMNIST and CIFAR10 in Tensorflow Federated, e.g. Stackoverflow.  MNIST and CIFAR10 is a little bit weak to prove the effectiveness of the proposed algorithm. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Although the reviewers acknowledge some contributions of the paper, it has some limitations on both theoretical results and numerical experiments. It is still unclear about the effectiveness of the proposed method. The authors should consider the following issues for the future submission: 

1) The justification of $\tau$ is not clear in federated learning with respect to communication efficiency (please see Reviewer 1’s comments).

2) The bounded stochastic gradient assumption is not applicable in the strongly convex case. This issue has been discussed clearly in [Nguyen et. al, “SGD and Hogwild! Convergence Without the Bounded Gradients Assumption”, ICML 2018]. Therefore, the constant G in Section 3.2. would damage the complexity bound since it could be arbitrarily large. 

3) Although the goal is to illustrate the benefits of the proposed quantization approach, the numerical experiments and the theoretical contributions are limited. The theoretical results are incremental from the existing optimization theory (both strongly convex and non-convex). Moreover, network architecture and data sets are not enough to justify the efficiency of the method. 

Decision: Reject