Analysis of Error Feedback in Compressed Federated Non-Convex Optimization
Authors: Xiaoyun Li
Ping Li
Venue: Submitted to ICLR 2023 (2023)

Abstract: Communication cost between the clients and the central server could be a bottleneck in real-world Federated Learning (FL) systems. In classical distributed learning, the method of Error Feedback (EF) has been a popular technique to remedy the downsides of biased gradient compression, but literature on applying EF to FL is still very limited. In this work, we propose a compressed FL scheme equipped with error feedback, named Fed-EF, with two variants depending on the global optimizer. We provide theoretical analysis showing that Fed-EF matches the convergence rate of the full-precision FL counterparts in non-convex optimization under data heterogeneity. Moreover, we initiate the first analysis of EF under partial client participation, which is an important scenario in FL, and demonstrate that the convergence rate of Fed-EF exhibits an extra slow down factor due to the ``stale error compensation'' effect. Experiments are conducted to validate the efficacy of Fed-EF in practical FL tasks and justify our theoretical findings.

Under review as a conference paper at ICLR 2023
ANALYSIS OF ERROR FEEDBACK IN COMPRESSED FEDERATED NON-CONVEX OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
Communication cost between the clients and the central server could be bottleneck in real-world Federated Learning (FL) systems. In classical distributed learning, the method of Error Feedback (EF) has been popular technique to remedy the downsides of biased gradient compression, but literature applying EF to FL is still very limited. In this work, we propose a compressed Fl. scheme equipped with error feedback, named Fed-EF, with two variants depending on the global optimizer. We provide theoretical analysis showing that Fed-EF matches the convergence rate of the full-precision FL counterparts in non-convex optimization under data heterogeneity. Moreover, we initiate the first analysis of EF under partial client participation, which is an important scenario in FL, and demonstrate that the convergence rate of Fed-EF exhibits an extra slow down factor due to the "stale error compensation" effect. Experiments are conducted to validate the efficacy of Fed-EF in practical FL tasks and justify our theoretical findings.
INTRODUCTION
Federated Learning (FL) has seen numerous applications in, e.g., computer vision, language process- ing, public health, Internet of Things (IoT) [19; 44; 62; 39; 49; 29; 25]. A centralized FL system includes multiple clients each with local data, and one central server that coordinates the training process. The goal of FL. is for n clients to collaboratively find global model, parameterized by 0, such that
a Σ f((0). BERd
8" arg min f(0) == arg min BER
(1)
where f:(0) ED-P. (F: D)] is a non-convex loss function for the i-th client w.r.t. the local data distribution D. Taking standard local SGD [42; 53] as an example, in each training round, the server first broadcasts the model to the clients. Then, each client trains the model based on the local data, after which the updated local models are transmitted back to the server and aggregated. The number of clients, nt, can be either tens/hundreds (cross-silo FL [41; 21J. e.g., clients are companies) or large as millions (cross-device FL [26; 29], e.g., clients are personal devices). There are two primary benefits of FL: (i) the clients train the model simultaneously, which is efficient terms of computational resources; (ii) each client's 's data are kept local throughout training and never transmitted to other parties, which promotes data privacy. However, the efficiency and broad application scenarios also brings challenges for FL method design:
Communication cost: In most FL algorithms, clients are allowed to conduct multiple train- ing steps (e.g., local SGD updates) in each round. Though this has reduced the communica- tion frequency. the one-time communication cost is still a challenge in real- wollworld FL systems with limited bandwidth, e.g., portable devices at the wireless network edges [5; 61; 29].
Data Heterogeneity: Unlike in the classical distributed training, the local data distribution in FL (D; in (1)) can be different (non-iid), reflecting many real-world scenarios where the local data held by different clients (e.g., app/website users) are highly personalized. When multiple local training steps are taken, the local models could become "biased" towards minimizing the local losses, instead of the global loss. This data heterogeneity may hinder the global model to converge to a good solution [34; 67; 33].
Partial participation (PP): Another practical issue, especially for cross-device FL, is the partial participation (PP) where the clients do not join training consistently, e.g., due to

---

Under review as a conference paper at ICLR 2023
unstable connection or user change. That is, only fraction of clients are involved in each FL training round, which may also slow down the convergence of the global model [10; 12].
FL under compression. In order to overeome the main challenge of communication bottleneck, several works have considered federated learning with compressed message passing. Examples include FedPaQ [47], FedCOM [18] and FedZip [40]. All these algorithms are built upon directly compressing model updates communicated from clients to server. In particular, [47: 18] proposed to use unbiased stochastic compressors such as stochastic quantization [3] and sparsification [57]. which showed that with considerable communication saving, applying unbiased compression in FL could approach the learning performance of un-compressed FL algorithms. However, unbiased (stochastic) compressors typically require additional computation (sampling) which is less efficient in real- world large training systems. Biased gradients/compressors are also common in many applications [2].
Error feedback (EF) for distributed training. One simpler and popular type of compressor is the deterministic compressor, including fixed quantization [13]. Topk sparsification [54; 52; 35], SignSGD [50; 8], etc., which belong to biased compression operators. In classical distributed learning literature, it has been shown that directly updating with the biased gradients may slow down the convergence or even lead to divergence [28: 2]. A popular remedy is the so-called error feedback (EF) strategy [54]: in each iteration, the local worker sends a compressed gradient to the server and records the local compression error, which subsequently used to adjust the gradient computed in next iteration, conceptually "correcting the bias" due to compression. It is known that biased gradient compression with EF can achieve same convergence rate as the full-precision counterparts [28; 35).
Despite the rich literature on EF in classical distributed training, it has not been well explored in the context of federated learning. In this paper, we provide a thorough analysis of EF in FL. In particular, the three key features of FL, local steps, data heterogeneity and partial participation, pose interesting questions regarding the performance of EF in federated learning: (i) Can EF still achieve the same convergence rate as full- prelisirciion FL algorithms, possibly with highly non-iid local data distribution? (ii) How does partial participation change the situation and the results? ? We present new algorithm and results to address these questions:
Our contributions.
We study FI. framework with biased compression and error feedback, called Fed-ER, with two variants (Fed-EF-SGi) and (FM-EEF-MM)) depending on the global optimizer (SGD and adaptive AMSGrad [46], respectively). Under data heterogeneity, Fed-EF has asymptotic convergence rate O VTKR where T is the number of communication rounds, K is the number of local training steps and n is the number of clients. Our new analysis matches the convergence rate of full pull-precision FL. counterparts, improving the previous convergence result [6] on error compensated FL (see detailed comparisons in Section 3). Moreover, Fed-EF-AMS is the first compressed adaptive FL algorithm in literature.
Partial participation (PP) has not been considered for standard error feedback in distributed learning. We initiate new analysis of Fed-EF in this setting, with local steps and non-iid data all considered the same time. We prove that under PP, Fed-EF exhibits a slow down of factor vn/m compared with the best pell-precision rate, where m is the number of active clients per round, which is caused mainly by the "delayed error compensation" " effect.
Experiments are conducted to illustrate the effectiveness of the proposed methods, where we show that Fed-EF matches the performance of full-precision FL with significant reduction in communication, and compares favorably against the algorithms using unbiased compression without error feedback. Numerical examples are also provided to justify our theory.
2 BACKGROUND AND RELATED WORK
Distributed SGD with compressed gradients. In distributed SGD training systems, extensive works have considered compression applied to the communicated gradients. Unbiased stochastic compressii
compressors include stochastic rounding and QSGD [3; 66; 58; 38], and magnitude based random
sparsification [57]. The works [50; 7; 8; 28; 24] analyzed communication compression using only the sign b1-bit) information of the gradients. Unbiased compressors can be combined with variance reduction techniques for acceleration, e.g., [17]. On the other hand, examples of popular biased compressors include TopK [37; 54: 52], which only transmits gradient coordinates with largest magnitudes, and fixed (or learned) quantization [13; 66). See [9] for summary of more biased
2

---

Under review as a conference paper at ICLR 2023
compressors. There exist other compression schemes, such as vector quantization [64; 40], low-rank approximation [56] and sketching [22], which will not be the focus of this paper.
Error Feedback (EF) for biased compression. It has been shown that directly implementing biased compression in distributed SGD leads to worse convergence and generalisation [2; 9]. Error feedback (EF), as proposed in [54], can fix this issue [28]. With EF, distributed SGD under biased compression can match the convergence rate of the full-precision distributed SGD, e.g., also achieving linear speedup (O (1))TTn) w.r.t. the number of workers n in distributed SGD [23; 51; 4; 68; 55]. Recently, variant of EF, called EF21, was proposed [48], which is different from EF in algorithm design. [15] applied EF21 to FL under several settings. Our work is different, where we analyze the standard EF FL, design new algorithms and derive faster convergence rates with different analysis.
Finally, in federated learning, as mentioned earlier, several works have applied compression to the cleent-to-eerver communication, e.g., [47: 40; 18]. Among the limited related literature on adopting [6] which is a special case of the Fed-EF
EF to FL, the most relevant method is @Sparse-local-See framework studied in this paper. In Section 3 and Section 4, we will compare our proposed Fed-EF framework with these related methods in terms of both algorithm and theory. Our algorithm also exploits adaptive gradient method AMSGrad [46], which has been applied to distributed and federated learning [45; 35J. See, for instance, [14; 65; 30] for the series of works adaptive gradient methods.
3 FED-EF: COMPRESSED FEDERATED LEARNING WITH ERROR FEEDBACK
In this paper, we consider deterministic compressors which are simple and computational efficient. Throughout the paper, [n]] will denote the integer set [t..... Definition (qe- deviate compressor). The ge ge-deviate compressor C: Rd + R.d is defined such that for Vr E TR. 30 < ic < s.I. [[C(x) - x1 I o ||==| In particular, two examples are [54; 68):
Let S = {i E [d] |x,l 2 t} where is the (1 - (1-))--quca quantile of [ i E [d]. The TopK compressor with compression rate k is defined as C(x); = 24. ifi S: C(x); 0 otherwise.
Divide [d] into M groups fe.g.. neural network layers) with index sets Ig 1.... M, and de == [Ia]. The (Grouped) Sign compressor is defined as C(x) =
|xg 11 sign(xr,),... "I 11 sign (I ) with xı, the sub-vector of x indices I, das
d1
Larger qe indicates heavier compression, and ge 0 implies no compression, i.c. C(x) = x. Additionally, these two com- pression operations can be combined to derive the so-called "heavy-Sign", where we first apply TopK and then Sign. This strategy is also q-deviate (see Appendix A for details) and will also be tested in our experiments in Section 5.
Test Accuracy (%)
40
Aul precision
Can simply use biased compressors in communication- efficient FL? As an example, in Figure 1, we report the test accuracy of a Multi-Layer Perceptron (MLP) trained on MNIST in non-iid FL environment (see Section 5 for more description), of Fed-SGD [53] with full communication v.s. Sign compression. We observe a catastrophic performance loss of using biased compression directly.
wio EF
50
100
Round
Figure 1: MLP trained by Fed-SGD on MNIST: full-precision vs. Sign com- pression, n 200 non-iid clients.
Fed-EF algorithm. To resolve this problem, error feedback (EF), which is a popular tool in distributed training, can be adapted federated learning. In Algorithm 1, we present a FL framework with biased compression, named Fed-EF, whose main steps are summarized below. In round t: 1) The server broadcast the global model 0, to all clients (line 5); 2) The i-th client performs K steps of local
SGD updates to get local model (kk) compute the compressed local model update Âr, updates the local error accumulator Ct,i, and sends the compressed Å, back to the server (line 6- 6-12); 3) The server receives & E [n] from all clients, takes the average, and perform a global model update using the averaged compressed local model updates (line 15-19).
Depending on the global model optimizer, we propose two variants: Fed-EF- (green) which applies SGD global updates, and Fed-EF-AMS (blue), whose global optimizer is AMSGrad [46].
3

---

Under review as a conference paper at ICLR 2023
Algorithm 1 Compressed Federated Learning with Error Feedback (Fed-EF)
1: Input: learning rates V), !|t+ hyper--arameters 31, $22.
2: Initialize: central server parameter 01 E R2 C R4; e1,i 0 the accumulator for each worker;
me 0, 0o 0g
3: for = 1, .,.... T do
4: parallel for worker i E [n] do:
5: Receive model parameter 8, from central server, set 8/ 0,
6: for k = L,..., K do
Compute stochastic gradient 92,4 at ((
7:
Local update ((*++1) 0 m92.s
(R)
8:
9:
end for
10:
Compute the local model update A,,
(k+1) -
11:
Send compressed adjusted local model update De.- = C(Dr,t + ex,)) to central server Update the error 1,+ Ct,i + Ar.: Ar,i
12:
13:
end parallel
14:
Central server do:
15:
Global aggregation Â, ! n2 -imm De,i
Update the global model 8,41 0₂ n
Fed-EF-SGD
17:
m, 31m-- 1 + (1 -1)
Fed-EF-AMS
18:
U = 320 + (1 - 32) Úe = max(22; 12-1)
19:
Update the global model O.+1 O2 1) Vitte
20:
end for
In Fed-EF-AMS, by the nature of adaptive gradient methods, we incorporate momentum (m²) with different implicit dimension-wiss learning rates n/6,, Additionally, for conciseness, the presented algorithm employs one-way compression (clients-to-server). In Appendix D, we also provide two- way compressed Fed- EF framework and demonstrate that adding the server-to-clients compression would not affect the convergence rates.
Comparison with prior work. Compared with EF approaches in the classical distributed training, e.g., [54; 28; 68; 38; 16; 35], our algorithm allows local steps (more communication-effiienin and uses two-side learning rates. When 7 1, the Fed-EF-SCC method reduces to QSparse-local SGD [6]. In Section 4, we will demonstrate how the two-side learning rate schedule improves the convergence analysis of the one-side learning rate approach [6]. On the other hand, several recent works considered compressed FL using unbiased stochastic compressors (all of which use SGD as the global optimizer). FedPaQ [47] applied stochastic quantization without error feedback local SGD, which is improved by [18] using a gradient tracking trick that, however, requires communicating an extra vector from server to clients, which is less efficient than Fed-EF. [40] provided empirical study on directly compressing the local updates using various compressors in Fed-SGD, while we use EF to compensate for the bias. [43] proposed FedLin, which only uses compression for synchronizing a local memory term but still requires transmitting full- full-precision updates. Finally, to our knowledge, Fed-EF-AMS is the first compressed adaptive FL method in literature.
communication-aa
THEORETICAL RESULTS
Assumption 1 (Smoothness). For Vi E [n), fi is L-smooth: [[V](()) V S L vll-
Assumption (Bounded variance). For Vt E [T]. Vi Vie [n),, Vk [K]: (i) the stochastic gradient is
unbiased: E (k) [[g.2]] (((0 ); (ii) the local variance is bounded: E 1119 v.((0! ) < o2:
(iii) the global variance is bounded: E (..))) v (0.))) og
4

---

Under review as a conference paper at ICLR 2023
Both assumptions standard in the convergence analysis of stochastic gradient methods. The global variance bound og in Assumption 2 characterizes the difference among local objective functions, which, is mainly caused by different local data distribution X; in (1), i... data heterogeneity. Assumption 3 (Compression discrepancy). There exists some QA < such that [1I 1 C(A
ex,x) - Ei= et,)) - E Ei + e(aa)l in every round E [7].
In Assumption 3, if replace "the average of compression". Ei compression of average", C(2 - + et.s).. the statement immediately holds by Definition I with QA Thus, Assumption 3 basically says that the above two terms stay close during training. This is a common assumption in related work on compressed distributed learning, for example, a similar assumption is used in [4] analyzing sparsified SGD. In [18], for unbiased compression without EF, a similar condition is also assumed with an absolute bound. In Appendix B, we provide more discussion and empirical justification to validate this analytical assumption in practice.
Ct,)), by "the
4.1 CONVERGENCE OF FED-EF: LINEAR SPEEDUP UNDER DATA HETEROGENEITY
Theorem 1 (Fed-EF-SGD). Let 0t = arg min f(0), and denote = max qA). C1 := 2 19
Q-- Under Assumptions
when "n S "KLmmx(4nnC the squared gradient norm of Fed-EF-SCO EF-SGD iterates in Algorithm can be bounded by
1 T E [IV & f(0.) f(0*) + 20m1 0² + (62 mITK
T Σ
In Theorem 1, the LHS is the expected squared gradient norm at a uniformly chosen global model from = 1,..., T, which is a standard measure of convergence in non-convex optimization (i.e., "norm convergence"). The first term is dependent from the local stochastic variance, and the last term represents the influence of data heterogeneity. In general, see that larger q (i.e., higher compression) would slow down the convergence.
the initialization, the second term o² comes
In our analysis of Fed-EF-AMS, we will make the following additional assumption of bounded stochastic gradients, which is common in the convergence analysis of adaptive methods, e-g., [46; 69; 31: Note that this assumption is only used for Fed-EF-AN EF-AMS, but not for Fed-EF-SGD.
Assumption 4. (Bounded gradients) It holds that |9
(k) || S G. Vt Vi [n], Vk [K].
We provide the first convergence analysis of compressed adaptive FL method as below.
Theorem 2 (Fed-EF-AMS), With same notations in Theorem 1, let C1 := I- + -- Under As-
8g
2g
sumptions 1 4, if the learning rates satisfy Th: S SKT.
Ve min 11 2(1-9214 Ve (1+02)1.06
max 3///8 }.
the Fed- Fee--EF-ASS iterates in Algorithm satisfy
1
E [[] f(0:) f((*)
5nt KL2 (30++200)) (0² + +6Kog)
+
miKK
2V
L6 + 4C7)
1)G'd
3m
0² +
ne
TVe
Te
With some properly chosen learning rates, we have the following simplified results.
Corollary (Fed-EF, specific learning rates). Suppose the conditions in Theorem and Theorem 2 are satisfied respectively. Choosing 1n 1 KVT
and y @(VKn), Fed-EF-SGD satisfy
T T for Fed-EF AMM-EF-AMS, it holds that
E E[IVS(0M1) o ((0h) - S(0))
1
Vn T3/2 (0² + +Koz))
0² +
VTKn
VTKn
T
E E[I = 0( ((()) ((0)))
1
Vn T3/2
- VTKn
(0² + +Ko))).
VTKn
TK
5

---

Under review as a conference paper at ICLR 2023
Discussion. From Corollary 1, see that when T 2 K, Fed-EF-AMS and Fed-EF- have the same rate of convergence asymptotically. Therefore, our following discussion applies to the general Fed-EF scheme with both variants. In Corollary 1, when T Kn, the global variance term of vanishes and the convergence rate becomes O(1/VTKn). Thus, the proposed Fed-EF enjoys linear speedup w.r.t. the number of clients n, i.e., it reaches a 6-stationary point (i.e., # E E ((+))l I 6) as long as TK- = ((1/n5²), which matches the recent results of the full-precision counterparts [60; 45] ([45] only analyzed the special case 31 O, while our analysis is more general). The condition T 2 K' to reach linear speedup considerably improves O(K of the federated momentum SGD analysis in [63]. In terms of communication complexity, by setting K (11/n)), Fed-EF only requires 7' = ((1/5) rounds of communication to converge. This matches one of the state-of-the-art FL communication complexity results of SCAFFOLD [27].
Comparison with prior related results. As special case of Fed-EF-SGD (1 = 1) and the most relevant previous work, the analysis of DSparse-local-See
[6] did not consider data heterogeneity, and their convergence rate ( ((IVVTK) VTK) did not achieve linear speedup either. Our new analysis improves this result, showing that EF can also match the best rate of using full communication in federated learning. For FL with unbiased compression (without EF), the convergence rate of
FedPaQ [47] is also (1//TT)) [18] refined the analysis and algorithm of FedPaQ, which matches our (11/5) communication complexity. To sum up, both Fed-EF-SGD and Fed-EF-AMS are able to achieve the convergence rates of the corresponding full-precision FL. counterparts, as well as the state-of-the-art rates of FL with unbiased compression.
4.2 ANALYSIS OF FED-EF UNDER PARTIAL CLIENT PARTICIPATION
Whilst being popular strategy in classical distributed training, error feedback has rarely been analyzed under partial participation (PP), which is an important feature of FL. Next, we provide new analysis and results of EF under this setting, considering both local steps and data heterogencity in federated learning. In each round f, assume only m randomly chosen clients (without replacement) indexed by MM, S [n] are active and participate in training (i.e., changing [m]] to MM at line 4 of Algorithm 1). For the remaining (n - m) inactive clients, we simply set Cr, = 1,-1,ix vi [m] MM The convergence rate is given as below.
Theorem 3 (Fed-EF, partial participation). In each round, suppose randomly chosen clients in Mr participate in the training. Under Assumptions 1 to 3, suppose the learning rates satisfy KL. Fed-EF-SGD admits
w S min 96C'm 53760(m-m)C3s 1n 3201n
m²
1 T
MAL
81p;C1
0² + 3mm CL
B[I
E
0
T
miTK
m
m²
m
KL
C2 560mm m)L (0² + 6Kog),
+
2
m
m²
x2 where C1 = (1- and C' = n_m Choosing ((VKK)) m = 0 vm -0m_m
KVTT we have
Σ [[IIS of Vn f(01) ((0)) T
1
+ TTm
VTKm
TTKm
Remark 1. We present Fed-EF-SGD for simplicity. With more complicated analysis, similar result applies to Fed-EF-AMS yielding the same asymptotic convergence rate as Fed-EF-SGD..
Remark 2. When m = n (full participation), Theorem 3 recovers the (11 (TK/)TKn) rate Corol- lary 1. When q = 0, we recover the O( K/Tm) rate of full-precision Fed-SGD under PP [60].
Effect of delayed error compensation. The convergence rate in Theorem 3 involves m in the denominator, instead of n as in Corollary 1, which is a result of larger gradient estimation variance due to client sampling. Compared with the O ((yK/Tm) rate of [60] for full-precision local SGD under PP, Theorem 3 is slower by factor of Vn/m. mm. which is consequence of the mechanism of error feedback. Intuitively, with full participation where each client active in every round, EF itself can, to a large extent, be regarded as subtly "delaying" the "untransmitted" gradient information

---

Under review as a conference paper at ICLR 2023
(C(A))-A)) A1) to the next iteration. However, under partial participation, in each round t, the error accumulator of a chosen client actually contains the latest information from round - 8, where can be viewed the "lag" which follows geometric distribution with E[s] = n/m. In some sense, this shares similar spirit to the problem of asynchronous distributed optimization with delayed gradients (e.g., [1; 36)) The delayed error information in Fed-EF under PP is likely pull the model away from heading towards a stationary point (i.e., slower down the norm convergence), especially for highly non-convex loss functions. In Section 5, we will propose a simple strategy to justify (and mitigate) the negative impact of this error staleness on the norm convergence empirically.
NUMERICAL STUDY
We provide numerical results to show the efficacy of Fed-EF in communicationn-effcceen FL problems and justify our theoretical analysis. Due to space limitation, we include representative results here and place more results and experimental details Appendix A.
Datasets. We present experiments on two popular FL datasets. The MNIST dataset [32] contains 60000 training examples and 10000 test samples of 28 28 gray-scale hand-written digits from 0 9. The FMNIST dataset [59] has the same input size and train/test split as MNIST, but the samples are fashion products (e.g., clothes and bags). More results on CIFAR dataset are included in Appendix
Federated setting. In our experiments, we test = 200 clients. The clients' local data are set to be highly non-iid (heterogeneous), where we restrict the local data samples of each client come from at most two classes. We run T = 100 rounds, where one FI. training round is finished after all the clients have performed one epoch of local training. The local mini-batch size is 32, which means that the clients conduct 10 local iterations per round. Regarding partial participation, we uniformly randomly sample m clients in each round. We present the results at multiple sampling proportion p m/n (e.g., p 0.1 means choosing 20 active clients per round). To measure the communication cost, we report the accumulated number of bits transmitted from the client to server (averaged over all clients), assuming that full-precision gradients are 32-bit encoded.
Methods and compressors. For both Fed-EF variants, we implement Sign compressor, and TopK compressor with compression rate k {0.001, 0.01, 0.05). We also employ more compressive strategy heavy-Sign where Sign is applied after TopK (i.e., a further 32x compression over TopK under same sparsity). We test hv-Sign with {0.01, 0.05, 0.1]. We compare our method with the analogue FL approach using full-precision updates, and the analogue algorithms of Fed-EF using unbiased stochastic quantization "Stoc" without error feedback [3]. For this compressor, we test parameter b E {1,2, 4). For SGD, this algorithm is equivalent to FedCOM/FedPaQ [47; 18].
5.1 FED-EF MATCHES FULL--PRECISION FL WITH SUBSTANTIALLY LESS COMMUNICATION
Firstly, we demonstrate the superior performance of Fed-EF in practical FL tasks. For both datasets, we train ReLU activated CNN with two convolutional layers followed by one max-post pooling, one dropout and two fully-connected layers before the softmax output. In Figure 2 and Figure 3, we compare our method with Stoc without EF with = 0.5 and p = 0.1, respectively. We have tested each compressor with multiple compression ratios, see Appendix A for the complete results. Here, we present curves (respective compression ratios) chosen by the following rule: for each method, we present the curve with highest compression level that achieves the best full-precision test accuracy; the method does not match the full- full-precision performance, we present the curve with the highest test accuracy. From Figure 2 and Figure 3, we see that:
In general, higher compression ratio leads to worse performance, as expected from the theory. The proposed Fed-EF (including both variants) is able to achieve the same performance as the full-precision methods with substantial communication reduction, e.g., hv-Sign and TopK reduce the communication by more than 100x without losing accuracy. Sign also provides 30x compression with matching accuracy as full full-precision training.
On MNIST, the loss and accuracy of Stoc (stochastic quantization without EF) tend to be slightly worse than Fed-EF-SGD with hv-Sign, yet requiring more communication.
With more aggressive p = 0.1, with proper compressor, Fed-EF still matches the perfor- mance of full-precision algorithms. While Sign performs well MNIST for both Fed-EF
7

---

Under review as a conference paper at ICLR 2023
SANEET COD Age
AMSS-gg
P
Test Aczurayy (%)
Train Loss
10
Train LeinLoss
AMM
Accuress
50
80
5022
MNIST
MNIST P 0.5
540 dre
MNIST 0.5
1600
10
10
10
10
10"
108
log. Communicated Bits
log. Communicaled Bits
log. Communicated Bits
1og.
Communicated Bis
2.5
2.5
FMNIST P
80
FMNNST 0,5
c
AND
Test Accur accuracy (%a
Train Loes
60
Age
Train Loss
Accuracy
86 8
80
580 dros
AMBS Shee
502
FMNIST
FMNIST p 0.5
10
10
10"
10
10
10
10
10
10"
10
10"
10"
10"
10"
10
log. Communicated
log. Communicated
log. Commuricated Bits
log.
Communicated
Figure 2: Training loss and test accuracy v.s. communicated bits, participation rate p = 0.5. "sign". "topk" and "hv-sign" are applied with Fed-EF, while "Stoe" is the stochastic quantization without EE
100
100
2.5
MNIST p 0.1
AMS dgn AMS Sho
p
Text Accurany (N)
MNIST p 0.1
Train Lose
Train Loss
2
Test Accuras
560 eiga
50
$20 Li
560
2210 sign
560 dree
2015-180
529--ra
MNIST 0.1
A015 Ioidgn
0.5
10
10"
10"
10
10
10
10
10"
10"
10
10a
10"
10"
10
log. Commuricated
log. Communicated
log. Communicated
log.
Communicated Bits
2.5
2.5
80
80
/ooo (%)
FMNIST p 0.1
Bac (%))
FMNNST 0.1
Train Loss
12
522 dign
Train Loss
sign
Tell Poegrecy
8 g.
Fast Accurasy
60
in
520
AMS 1.
3
20
FMINST = 0.1
FMNIST 0.1
0.5
0.5
10a
10
10
10
10
10f
104
10a
104
10a
10a
10a
10
108
log Commuricated
log.
Communicated
log. Communicated Bits
log.
Communicated
Figure 3: Training loss and test accuracy v.s. communicated bits, participation rate p 0.1. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF
variants, we notice that fixed sign- based compressors (Sign and heavy-Sign) consid- erably outperformed by TopK for Fed-EF-AMS on FMNIST. We conjecture that this is because with small participation rate, sign-based compressors tend to assign same implicit learning rate across coordinates (controlled by the second moment f), making adaptive method less effective. In contrast, www.mmmmdae-peeeeeeeeee compressors (e.g., TopK and Stoc) may better exploit the adaptivity of AMSGrad.
5.2 ANALYSIS OF NORM CONVERGENCE AND DELAYED ERROR COMPENSATION
We empirically evaluate the norm convergence verify the theoretical speedup properties of Fed-EF and the effect of delayed error compensation in partial participation (PP). Recall that from Theorem 1, in full participation case, reaching 5-stationary point requires running @ (1/nn²)) rounds of Fed-EF (i.e., linear speedup). From Theorem 3, when is fixed, our result implics that the speedup should be super-lineat against m, the number of participating clients, due to the additional stale error effect. In other words, altering is expected to have more impact the convergence under PP.
We train an MLP (which also used for Figure 1) with one hidden layer of 200 neurons. In Figure 4, report the squared gradient norm and the training loss MNIST under the same non-iid FL setting as above (the results on FMNIST are similar). In the full participation case, we implement Fed-EF-SGD with 20, 40, 60, 100 clients; for the partial participation case, we fix 200 and
8

---

Under review as a conference paper at ICLR 2023
0.0
20
20 40
20
0.6
40
0.6
60
50
[
50
Train LosE
60
100
100
m 100
MNIST
ANIST
-0
100
MNIST 200
100
Round
Round
Round
Round
Figure 4: MLP on MNIST with -o00-0.01 compressed Fed-EF: Squared gradient norm (left two) and train loss (right two) against the number of training rounds, averaged over 20 independent runs.
0.8
1.5
0.9
1.1
0.6
0.8
0.7
0.6
0.8
0.7
0.2
MNIST 0.1
0.5
FMNIST p
0.5
MNIST
0.6
FMNIST 0.1
0
50 Round
100
50
100
50
100
50
100
Round
Round
Round
Figure 5: Squared gradient norm of Fed-EF (TopK-0.01) under PP with error restarting, S = 10. Left two panels: logistic regression. Right two panels: MLP. n 200, r = 1, m 0.1.
alter m = 20, 40, 60, 100. According to our theory, we set rj = 0.1 V (or 0.1 mm) and v 0.1. We see that: 1) In general, the convergence of Fed-EF is faster with increasing
m, which confirms the speedup property: 2) The gaps among curves in the PP setting (the 2nd and 4th plot) is larger than those in the bull-participation case (the 1st and 3rd plot), which suggests that the acceleration brought by increasing m under PP is more significant than that of increasing n in pull-caatiiipation by a same proportion, which is consistent with our theoretical implications.
To further embody the intuitive impact of delayed error compensation under PP, we test a simple accumulator was last
strategy called "error restarting": for each client i in round 1, if the updated more than S (a threshold) rounds ago (i.e.. before round t - S), we simply restart the error accumulator by setting E, = O, which effectively eliminates the error information that "too old". In Figure 5, we first run Fed-EF for 50 rounds, and then apply error restarting with threshold S = 10. As we see, after prohibiting heavily delayed error information, the gradient norm is smaller than that of continuing running standard Fed-EF, i.e.. the model finds a stationary point faster. These results illustrate the influence of stale error compensation in Fed-EF, and that properly handling this staleness might be promising direction for improvement in the future.
6 DISCUSSION AND CONCLUSION
We propose Fed-EF, Federated Learning (FI.) framework with compressed communication and Error Feedback (EF). Two variants, Fed-EF-SGI and FcM-EF-AMS, are designed based on the choice of the global optimizer. Theoretically, we present convergence analysis in non-convex optimization showing that Fed-EF achieves the same convergence rate as the full-precision FL counterparts, which improves upon previous results. The Fed-EF-AMS variant is the first compressed adaptive FL method literature. Moreover, we develop new analysis of error feedback in distributed training systems under the partial participation setting. We prove additional slow down factor related to the participation rate due to the delayed error compensation of the EF mechanism. Experiments validate that compared with full- pill-preiision training, Fed-EF achieves significant communication reduction without performance drop. We also present numerical results to justif'y the theory and provide intuition regarding the impact of the delayed error feedback on the norm convergence of Fed-EF. Our work supports the effectiveness of error feedback in federated learning, and provide insight on its convergence under practical FL setting with partial participation. Our paper expands several interesting future directions, e.g., to improve Fed-EF by other tricks, especially under partial participation, and to study more closely the property of different compressors. More mechanisms in FL (e.g., variance reduction, fairness) can also be incorporated into our Fed-EF EF scheme.

---

Under review as a conference paper at ICLR 2023
REFERENCES
[1] Alekh Agarwal and John C. Duchi. Distributed delayed stochastic optimization. In John Shawe- Taylor, Richard S. Zemel, Peter L. Bartlett, Fernando C. N. Pereira, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems, pages 873-881, 2011.
[2] Ahmad Ajallocian and Sebastian Stich. Analysis SGD with biased gradient estimators. arXiv preprint arXiv:2008.0005// 2020.
[3] Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: communication-efficeen SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pages 1709-1720, Long Beach, CA, 2017.
[4] Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advances in Neural Information Processing Systems (NeurIPS), pages 5977-5987, Montréal, Canada, 2018.
[5] Mohammad Mohammadi Amiri and Deniz Gündüzz. Federated learning over wireless fading channels. IEEE Trans. Wirel. Commun., 19(5)3356-3357, 2020.
[6] Debraj Basu, Deepesh Data, Can Karakus, and Suhas N. Diggavi. Qsparse-local-sgd: Dis- tributed SGD with quantization, sparsification and local computations. In Advances Neural Information Processing Systems (NeurIPS), pages 1667,, Vancouver, Canada, 2019.
[7] Jeremy Bernstein, Yu-Xiang Wang. Kamyar Azizzadenesheli, and Animashree Anandkumar. SIGNSGD: compressed optimisation for non-convex problems. In Proceedings of the 35th International Conference on Machine Learning (ICMI), pages 559-568, Stockholmsmässan, Stockholm, Sweden, 2018.
[8] Jeremy Bernstein, Jiawei Zhao, Kamyar Arizzadenesheli, and Anima Anandkumar. signSGI with majority vote is communication efficient and fault tolerant. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
[9] Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 2020.
[10] Zachary Charles, Zachary Garrett, Zhouyuan Huo, Sergei Shmulyian, and Virginia Smith. On large-cohort training for federated learning. In Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 20461-20475, 2021.
[11] Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of A class of adam-type algorithms for non-convex optimization. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
[12] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-chre -f-chicce selection strategies. CoRR, abs/2010.01243, 2020.
[13] Tim Dettmers. 8-bit approximations for parallelism in deep learning. In Proceedings of the 4th International Conference on Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
[14] John C. Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. In Proceedings of the 23rd Conference on Learning Theory (COLT), pages 257-269, Haifa, Israel, 2010.
[15] lyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. Ef21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint arX.v:2110.03299, 2021.
[16] Avishek Ghosh, Raj Kumar Maity, Swanand Kadhe, Arya Mazumdar, and Kannan Ramchandran. Communication--fficie -efriiinnneiiintnntttee and byzantine-robuu distributed learning with error feedback. IEEE J. Sel. Areas Inf. Theory, 2(3):942-95 953,, 2021.
10

---

Under review as a conference paper at ICLR 2023
[17] Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: faster non-conve. distributed learning with compression. In Proceedings of the 38th International Conference Machine Learning, ICML 2021, 18-24 July 2021. Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 3788-3798. PMIR, 2021.
[18] Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi, Federated learning with compression: Unified analysis and sharp guarantees. In The 24th International Conference on Artificial Intelligence and Statistics, AISTATS 2021, April 13- 15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pages 2350-2358. PMLR, 2021.
[19] Andrew Hard, Kanishka Rao, Rajiv Mathews, Swaroop Ramaswamy, Françoise Beaufays, Sean Augenstein, Hubert Eichner, Chloé Kiddon, and Daniel Ramage. Federated learning for mobile keyboard prediction. arXiv preprint 18X 11881100060 1.03604, 2018.
[20] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 770-778, Las Vegas, NV, 2016.
[21] Yutao Huang, Lingyang Chu, Zirui Zhou, Lanjun Wang, Jiangehuan Liu, Jian Pei, and Yong Zhang. Personalized cross-silo federated learning non-iid data. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI, pages 7865-7873. AAAI Press, 2021.
[22] Nikita Ivkin, Daniel Rothchild, Enayat Ullah, Vladimir Braverman, Ion Stoica, and Raman Arora. Communication-efiiien distributed SGD with sketching. In Advances in Neural Information Processing Systems (NeurIPS), pages 13144-13154, Vancouver, Canada, 2019.
[23] Peng Jiang and Gagan Agrawal. A linear speedup analysis of distributed deep learning with sparse and quantized communication. In Advances in Neural Information Processing Systems (NeurIPS), pages 2530-2541, Montréal, Canada, 2018
[24] Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign sgd for federated learning with theoretical guarantees. arXiv preprint 2rXi: 2020.
[25] Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cum- mings, Rafael G. L. D' D'Olveeira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Har- chaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Hang Qi. Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranceth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. Found. Trends Mach. Learn., 14(1-2):1-210, 2021.
[26] Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. Breaking the centralized barrier for cross- device federated learning. In Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6- 14, 2021.
2021, virtual, pages
[27] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank J. Reddi, Sebastian U. Stich, and Ananda Theertha Suresh. SCAFFOLD: stochastic controlled averaging for federated learning. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virfual Event, volume 119 of Proceedings of Machine Learning Research, pages 5132-5143. PMLR, 2020.
[28] Sai Praneeth Karimireddy. Quentin Rebjock, Sebastian U. Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 3252-3261. Long Beach, CA. 2019.
11

---

Under review as a conference paper at ICLR 2023
[29] Latif U. Khan, Walid Saad, Zhu Han, Ekram Hossain, and Choong Seon Hong. Federated learning for internet of things: Recent advances, taxonomy, and open challenges. IEEE Commun. Surv. Tutorials, 23(3):1759-1799 2021.
[30] Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In Proceedings of the 3rd International Conference on Learning Representations (ICLR), San Diego, CA, 2015.
[31] A. Krizhevsky and G. Hinton. Learning multiple layers of features from tiny images. Master's s thesis, Department of Computer Science, University of Toronto, 2009.
[32] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11))2278-25) 1998.
[33] Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Chal- lenges, methods, and future directions. IEEE Signal Process. Mag., 37(3):50-60, 2020.
[34] Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In 8th International Conference on Learning Representations, ICLR 2020, Addis Abuba, Ethiopia, April 26-30, 2020, 2020.
[35] Xiaoyun Li, Belhal Karimi, and Ping Li. On distributed adaptive optimization with gradient compression. In Proceedings of the 10th International Conference on Learning Representations (ICLR), Virtual Event, 2022.
[36] Xiangru Lian, Yijun Huang. Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 2737-2745, 2015.
[37] Yujun Lin, Song Han, Huizi Mao, Yu Wang, and Bill Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. In Proceedings of the 6th International Conference on Learning Representations (ICLR), Vancouver, Canada, 2018.
[38] Xiaorui Liu, Yao Li, Jiliang Tang, and Ming Yan. double residual compression algorithm for efficient distributed learning. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo. Sicily, Italy), volume 108 of Proceedings of Machine Learning Research, pages 133-143. PMLR, 2020.
[39] Yang Liu, Anbu Huang, Yun Luo, He Huang, Youzhi Liu, Yuanyuan Chen, Lican Feng. Tianjian Chen, Han Yu, and Qiang Yang. Fedvision: An online visual object detection platform powered by federated learning. In The Thirty--Forrth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty- Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, pages 13172-13179. AAAI Press, 2020.
[40] Amirhossein Malekijoo, Mohammad Javad Fadaeieslam, Hanieh Malekijou, Morteza Homay- ounfar, Farshid Sazzadeh-Shabdin and Reza Rawassizadeh. Fedzip: A compression framework for communication-effiiinn federated learning. arXiv preprint arXiv:2102.011593 2021.
[41] Othmane Marfoq, Chuan Xu, Giovanni Neglia, and Richard Vidal. crroughhut-optinne topol- ogy design for cross-silo federated learning. In Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020.
[42] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. cnapuuiccation-ffficieee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1273-1282. Fort Lauderdale, FI., 2017.
[43] Aritra Mitra, Rayana H. Jaafar, George J. Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. In Advances in Neural Information Processing Systems 34: Anmual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6- 14, 2021, virtual, pages 14606-14619, 2021.
12

---

Under review as a conference paper at ICLR 2023
[44] Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6625-4625. PMIR, 2019.
[45] Sashank Reddi, Zachary Charles, Manzil Zaheer, Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Hugh Brendan McMahan. Adaptive federated optimization. In Proceedings of the 9th International Conference Learning Representations (ICLR), Virtual Event, 2021.
[46] Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In Proceedings of the 6th International Conference on Learning Representations (ICIR), Vancouver, Canada, 2018.
[47] Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsami. Fedpaq: communication-effiiee federated learning method with periodic averaging and quantization. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy], volume 108 of Proceedings of Machine Learning Research, pages 2021-2031. PMLR, 2020.
[48] Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. EF21: A new, simpler, theoretically better, and practically faster error feedback. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2021.
[49] Nicola Rieke, Jonny Hancox, Wenqi Li, Fausto Milletari, Holger R Roth, Shadi Albarqouni, Spyridon Bakas, Mathieu N Galtier, Bennett A Landman, Klaus Maier-Hein, al. The future of digital health with federated learning. NPJ digital medicine, 3(1):1-7, 2020.
[50] Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-pan aata-parlllel distributed training of speech dnns. In Proceedings of the 15th Annual Conference of the International Speech Communication Association (ISCA), pages 1058-1062, Singapore, 2014.
[51] Zebang Shen, Aryan Mokhtari, Tengfei Zhou, Peilin Zhao, and Hui Qian. Towards more efficient stochastic decentralized learning: Faster convergence and sparse communication. In Proceedings of the 35th International Conference Machine Learning (ICML), pages 4631-4660 1631-4 Stockholmsmässan, Stockholm, Sweden, 2018
[52] Shaohuai Shi, Kaiyong Zhao, Qiang Wang, Zhenheng Tang, and Xiaowen Chu. A convergence analysis distributed SGD with communication-efficicae gradient sparsification. In Proceedings of the 28th International Joint Conference Artificial Intelligence (IJCAI), pages 3411-341140 1-347, Macao, China, 2019.
[53] Sebastian U. Stich. Local SGD converges fast and communicates little. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[54] Sebastian U. Stich, Jean- Cean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances in Neural Information Processing Systems (NeurIPS), pages 4447-4458, Montréal, Canada, 2018
[55] Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint arXiv: (9t.:::999005550 2019.
[56] Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Powersgd: Practical low-rank gradi- ent compression for distributed optimization. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 1423--1425,, 2019.
[57] Jianqiao Wangni, Jialei Wang. Ji Liu, and Tong Zhang. Gradient sparsification for communication-effiicee distributed optimization. Advances in Neural Information Pro- cessing Systems (NeurIPS), pages 1299-1309, Montréal, Canada, 2018
13

---

Under review as a conference paper at ICLR 2023
[58] Jiaxiang Wu, Weidong Huang. Junzhou Huang, and Tong Zhang. Error compensated quantized SGD and its applications to large-scale distributed optimization. In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 5321-5329, Stockholmsmässan, Stockholm, Sweden, 2018.
[59] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: (ato::778.077777 2017.
[60] Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participation in non-iid federated learning. In 9th International Conference Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021, 2021.
[61] Howard H. Yang, Zuozhu Liu, Tony Q S. Quek, and H. Vincent Poor. Scheduling policies for federated learning in wireless networks. IEEE Trans. Commun.,
2020.
[62] Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Trans. Intell. Syst. Technol., 10(2):12:1-1::11 2019.
[63] Hao Yu, Rong Jin, and Sen Yang. On the linear speedup analysis of communication efficient mo- mentum SGD for distributed non-convex optimization. In Proceedings of the 36th International Conference Machine Learning (ICML), pages 7184-7193, Long Beach, CA, 2019.
[64] Mingchao Yu, Zhifeng Lin, Krishna Narra, Songze Li, Youjie Li, Nam Sung Kim, Alexander G. Schwing, Murali Annavaram, and Salman Avestimehr. Gradiveq: Vector quantization for handwidth-efficient gradient aggregation in distributed CNN training. In Advances in Neural Information Processing Systems 31: Anmual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 5129-5139, 2018.
[65] Matthew Zeiler. Adadelta: an adaptive learning rate method. arXiv preprint arXiv: 1212.570, 2012.
[66] Hantian Zhang, Jerry Li, Kaan Kara, Dan Alistarh, Ji Liu, and Ce Zhang. ZipML: Training linear models with end-to-end low precision, and a little bit of deep learning. In Proceedings of the 34th International Conference Machine Learning (ICMI., pages 4035-4043, Sydney, Australia, 2017.
[67] Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806. 00582, 2018.
[68] Shuai Zheng, Ziyue Huang, and James T. Kwok. Communication distributed blockwise momentum SGD with error-feedback. In Advances in Neural Information Processing Systems (NeurIPS), pages 11446-15 11456, Vancouver, Canada, 2019.
[69] Dongruo Zhou, Jinghui Chen, Yuan Cao, Yiqi Tang, Ziyan Yang, and Quanquan Gu. On the convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint 1808,00,, 2018.
14

---

Under review as a conference paper at ICLR 2023
Appendices
CONTENTS
Experiment Details, Algorithms and More Results
16
A.1 Biased Compression Operators ................................
16
A.2 Competing Methods: Stochastic Quantization Without Error Feedback
17
A.3 Results CIFAR-10 Trained by ResNet-18
18
A.4 More Results on MNIST and FMNIST
19
A.5 Data Split and Parameter Tuning
20
Compression Discrepancy
25
B.1 Simulated Data
25
B.2 Real-world Data
26
Proof of Convergence Results
27
C.1 Proof of Theorem 2: Fed-EF-AMS
27
C,2 Proof of Theorem 1: Fed-EF-SGD
33
C,3 Intermediate Lemmas
35
C.4 Proof of Theorem 3: Partial Participation
40
D Way Compression in Fed-EF
45
15

---

Under review as a conference paper at ICLR 2023
A EXPERIMENT DETAILS, ALGORITHMS AND MORE RESULTS
In this section, we provide more theoretical justification of the compressors, and more implementation details of the empirical results.
A.1 BIASED COMPRESSION OPERATORS
In our Fed-EF, the biased compressors are implemented as follows. Sign is implemented exactly following Definition 1. For TopK, we also apply in "layer-wise" manner. Let & denote the proportion of coordinates selected. For each layer with d; parameters, we pick max(1, [kd,] J) gradient dimensions. The maximum operator avoids the case where layer is never updated. The heavy-Sign is implemented by first applying TopK (per layer) and then applying Sign.
For completeness, we provide more theoretical details of the biased compression operators, TopK, Sign and heavy-Sign. Recall in Definition that [[C(z) - ==|² < o ||= for some qc < 1. We first justify that TopK and Sign are both valid compressors, In the sequel, || always denotes the l2 norm and || || is the 1 norm.
Proposition A.1 well-known (e.g.. [54; 68]), and we provide the proof for clarity. Again, note that in TopK, k is the compression rate, which is the fraction, instead of the number, of selected coordinates.
Proposition A.1. For the TopK compressor which selects top k-percent of coordinates, we have oe = 1 For the (Group) Sign compressor, of = min 7,
Proof. For TopK, the proof is trivial: since C(x) - x only contain (1 - k)d coordinates with lowest magnitudes, know [|C(x)) =||>/||>*| I 1 k.
For Sign, recall that Z₁ is the index set of block (group) i. By definition, for the i-th block (group) TI, E Rd4, we have
| 11
[C((I,) - =2,112 |
sign (ZZ,) )1
dj
||zz,11 11? + | 11
221221, 11?
dc
d,
|, 1| || /l///d.
Since we have M blocks, concatenating the blocks leads to
M
[C(x) - = | 1|2 | /2/
M
||
||æ2 ll7/d
ΣM 11
||a7z 112/dd |
(1
||:0112
|, 12
< (1 min ME[M]
||
<
min (E[M] d, |x/
de I
where the last inequality is because 1 norm is larger than la norm.
We now show that heavy-Sign is also valid compressor. Proposition A.2. The heavy-Sign compressor satisfies Definition I with o2 = min d,
Proof. Let Cj denote the TopK compressor and C, be the Sign operator. Thus, the heavy-Sign operator can be expressed as C(x:) C. (=)) It holds that
[[C(x) x=| (Cx(()) -C(()) Cx(x) - xxl2 (Cx(())))) Cx(x))1 + [[Cx(I) xx12.
16

---

Under review as a conference paper at ICLR 2023
because TopK zeros out the unpicked coordinates. By Proposition A.1, continue to obtain
[[C(z) z11² - (1 - min ic|M] d;
+|Cx - z/|2
|| min
- (x)x - (1 min d, ||
=
M di
iE[M] d;
where the fact that [[ This completes the proof.
| and ||C(,))] |||=||| by Proposition A.
A.2 COMPETING METHODS: STOCHASTIC QUANTIZATION WITHOUT ERROR FEEDBACK
Algorithm 2 Federated Learning with Unbiased Compression (Competing method Stoc)
1: Input: learning rates 7). Mj. hyper-parameters 31,
32, c
2: Initialize: central server parameter 01 12d C R2. e1,
the accumulator for each worker;
me 0, 01 0, h 0
3: for = 1, .,,.,,,......................... T do
4: parallel for worker i E [n]] do:
5: Receive model parameter 0, from central server, set 0,1 = 0,
6: for |: -,....... do
Compute stochastic gradient 9 at e(k)
7:
1,1
Local update o(++1) 0 m (R) end for
8:
9:
Compute the local model update A,,i 0 (K+1) - 0
10:
11: Send quantized local model update A.,; = Q(A.;)) to central server using (2)
end parallel
13:
Central server do:
14:
Global aggregation A
Update the global model 0,+1 02 n/A
Stoc with SGD
16:
m, -1m-- -1- A1
Stoc with AMSGrad
17:
U = 320 + (1- 3,) Úe = max(u/; 12-1)
18:
Update the global model 0.+1 O2 vi
me
19:
end for
In Algorithm 2, for completeness, we give the details of the competing method, called Stoc, in our experiments. Instead of using the error feedback scheme, this method directly compresses the transmitted vector from clients to server by unbiased stochastic quantization Q(-) proposed by [3]. For vector Rd the operator Q(-) is defined
(x(x) ||>||| sign(x) ((x,b) b).
(2)
where is number of bits per non-zero entry of the compressed vector Q(x). Suppose 0 < l < 2d-1 is the integer such that |z,//||>>|| is contained in the interval [1/20-1 (1 1) 2 '.. The random variable E(x; b) is defined by
E(xrb) = l/s, (1 + 1)/a, otherwise,
with probability 1 - g( 2i
b). [
with g(a, 6) = a 26-1 for a E [0, 1]. Simply, 0 is always quantized to 0. The Stoc quantizer is unbiased, i.e., [[[(x)[z) = In addition, also introduces sparsity to the compressed vector in probabilistic way, with [(]])(x))ll) < 2 2b-1vd Vd.
17

---

Under review as a conference paper at ICLR 2023
Stoc also has two corresponding variants, using SGD and using AMSGrad as the global optimizer. For the SGD variant, Stoc is equivalent to the FedCOM method in [18], which is also the FedPaQ algorithm [47] with tunable global learning rate.
For the full-precision algorithms, we simply set &r,; A in line 11 of Algorithm 2. For SGD, becomes the one studied in [60] which is the standard local SGD [42] with global learning rate. For adaptive optimizer, it becomes FedAdam [45]. Note that [45] used Adam, while we use AMSGrad (with the max operation). Empirically, the performance of these two options are fairly similar.
A.3 RESULTS ON CIFAR-10 TRAINED BY RESNET-18
We present more experiment results of Fed-EF on the task of CIFAR-10 [31] image classification. This dataset contains 50000 natural images of size 32 32 each with 3 RGB channels. There 10 classes, c.g., airplanes, cars, cats, etc. We follow a standard strategy for CIFAR-I0 10 dataset to pre-process the training images by random crop, a random horizontal flip and normalization of the pixel values to have zero mean and unit variance. For test images, we only apply the normalization step. For this experiment, we train ResNet-18 [20] network for 200 rounds. The clients local data are distributed in the same way as described in Section 5, which is highly non-iid.
Test Accuracy (%)
150
CIFAR p =
Test Acouracy (%)
50
CIFAR p p=00 0.5
Test Accuracy (%)
CIFAR p 0.5
40
40
40
30
-0D-uul
30
SGD-ful
30
SOD-sign
5GDD-ggn
SGD-uil
SGD 0opp--00p000
SCID-hv-lgg
20
80D--xps-0.01
20
SGD
3GDD-tw-aggn-0.0
20
3GD tapk
S0D-mxps0005
9GD-h--iin
10
10
10
105
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
60
60
60
Test Accuracy (%6
150
-AMS
sign
topk-a..00
Test Accuracy (%)
50
AMSS the-sggn 0.01
sign
Test Accuracy (%)
50
CIFAR 0.5
AMS tock-0.01
AMS-h---ign- th--sig-0.05 0.05
40
AMS topk- 0.05
40
AMS SiiE-----ign.... D.1
40
30
30
30
20
20
20
AMS-sign
CIFAR p
CIFAR 0.5
AM45-100 145--opk
MMS-Tw-do
10
10
10
10
10
108
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 6: CIFAR-10 dataset trained by ResNet-18. Test accuracy of Fed-EF with TopK, Sign and heavy-Sign compressors. Participation rate 0.5, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" the stochastic quantization without EF. 1st row: Fed-EF. SGD. 2nd row: Fed- EF-AMS. The last column presents the corresponding curves that achieve the full-precision accuracy using lowest communication.
In Figure 6, we plot the test accuracy of Fed-EF with different compressors, and Stoc without EF. Again, that Fed-EF (both variants) is able to attain the same accuracy level as the corresponding full- full-precision federated learning algorithms. For Fed-EF-SGD, the compression rate is around 32x for Sign, 100x for TopK and ~300x for heavy-Sign. For FeM-EF-AMS, the compression ratio also be around hundreds. Note that for Fed-EF-AMS, the training curve of TopK-0.001 is not stable. Though it reaches high accuracy, still plot TopK-0.01 in the third column for comparison.
18

---

Under review as a conference paper at ICLR 2023
50
50
50
Test Accuracy (%6
Test Accuracy (%)
CIFAR p 0.1
Test Accuracy (%)
CIFAR p 0.1
40
40
40
--SGD full
-530-sig
30
50. 1000-oo4--.001
30
30
-GDD-ul
800D-top--3.05
SGD-sign
-00--u
20
20
830-m -..0-0.01
20
SGD-aggn
80D my sign-0.05
S-D-sopk
CIFAR 0.1
80D sigh-011
SGD
10
10
10
10
10
10
10
10
10 to
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
50
50
50
Test Accuracy (%)
-AMS--Ull
AMSS-sig
Test Accuracy (%)
MMS-ALI
AMAS-+ign
Test Accuracy (%)
CIFAR p 0.1
40
AMSS-opp-0000
40
AMS AMS-hrvsign 0.51
40
AMS--opt-0.01
MMB-hw-llgn
AMS-topi-0..
AMS-hr-agg-0.1
30
30
30
-MS
20
20
20
AMS sign
CIFAR = 0.1
CI = 0.1
AMS topk
AMS
10
10
10 10
10
10
10
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 7: CIFAR-10 10 dataset trained by ResNet-18. 18. Test accuracy of Fed-EF with TopK, Sign and heavy-Sign compressors. Participation rate p 0.1, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF. 1st row: Fed-EF- SGD. 2nd row: Fed-EF-AMS. The last column presents the corresponding curves that achieve the full-precision accuracy using lowest communication.
In Figure we report the results for aggressive partial participation with p = 0.1. Similarly, for SGD, all three compressors are able to match the full-precision accuracy, with significantly reduced number of communicated bits. For AMMS, similar to the observations on FMNIST, we see that TopK outperforms Sign and heavy-Sign, and matches the performance of full-precision method with 100x compression ratio. Sign also performs reasonably well.
In conclusion, results on CIFAR-10 and ResNet again confirm that compared with standard full-precision FL algorithms, the proposed Fed-EF scheme can provide significant communication reduction without performance drop, under data heterogeneity and partial participation.
A.4 MORE RESULTS ON MNIST AND FMNIST
We provide the complete of experimental results each method under various compression rates. In Table 1 Table 4, for completeness we report the average test accuracy at the end of training and the standard deviations (over 5 independent runs), corresponding to the curves (compression parameters) in Figure 2 and Figure 3. Figure 8 to Figure 11 present the results for participation rate p 0.5. and Figure to Figure 15 report the results for p 0.1.
Fed-EF-SGD TopK
No EF
Sign
Hv-Sign
Stoc
Full-precision
MNIST
90.87 (E0.84)
91.04 (#11.0))
91.18 (#1.10)
90.16 (EE.96)
90.85 (=0089)
FMNIST
71.13 (+.068)
71.16 (++0.77)
71.07 (+0.83)
71.26 (+0.87)
71.20 (+71.
Table 1: Test accuracy (%) with client participation rate p 0.5, of Fed-EF-SGD with Sign, TopK and heavy-Sign compressor and Stoc (stochastic quantization) without EF, The compression parameters (i.e., & and b) of the compressors are consistent with Figure 2.
19

---

Under review as a conference paper at ICLR 2023
Fed-EF-AMS TopK
No EF
Sign
Hv-Sign 91.77 (=1.2
Stoc
Full-precision
MNIST
92.32 (=0098)
92.74 (=t0.84)
92.36 (=0.93)
92.23 (=0.73)
FMNIST
71.35 (+0.61)
71.90 (+0.78) 70.73(+1.03)
71.94 (+0.95)
71.97 (=0.86)
Table 2: Test accuracy (%) with client participation rate 0.5, of Fed-EF-AMS with Sign, Topk and heavy-Sign compressor and Stoc (stochastic quantization) without EF, The compression parameters (i.e., k and b) of the compressors are consistent with Figure 2.
Fed-EF -F-DDF-
No EF
Sign 90.15 (=06
Topk
Hv-Sign
Stoc
Full-precision
MNIST
90.61 (#+0,93)
90.42 (+
90.27 (#1.18)
90.22 (=0.82)
FMNIST
67.69 (+0.73)
67.47 (+0.80)
67.72
67.71 (#0.78)
67.50 (=0.85)
Table 3: Test aceuracy (%) with client participation rate p 0.1, of Fed-EF-SGI with Sign. Topk and heavy-Sign compressor and Stoc (stochastic quantization) without EF. The compression parameters (i.e., & and b) of the compressors are consistent with Figure 3.
Fed-EF-AMS
No EF
Sign
TopK
Hv-Sign
Stoc
Full-precision
MNIST
88.67 (EL.IT)
88.97 (11,166
77.49 (+155)
88.76 (+E1.22)
89.05 (=:1004)
FMNIST
57.60 (+2.34)
64.09 (++0,91) 50.77(42.87)
64.35 (+100
64.18 (+00900)
Table 4: Test accuracy (%) with client participation rate p 0.1, of Fed-EF-AMS with Sign, TopK and heavy-Sign compressor and Stoc (stochastic quantization) without EF, The compression parameters (i.e., k and b) of the compressors are consistent with Figure 3.
A.5 DATA SPLIT AND PARAMETER TUNING
In our experiments, for 200 clients, we first split the training samples into 2n 400 shards, where each shard contains samples from only one class. Then, each client is randomly assigned with two shards uniformly. This way, in expectation, around 180 clients would have samples from two classes, and about 20 clients would have samples from only one class. This corresponds to a strong data heterogeneity among the clients.
For the (0.001, 0.01, 0.05) for TopK, k {0.01, 0.1] for heavy-Sign and b {1, 4] for Stoc. For the AMSGrad optimizer, we set 31 = 0.9, 32 = 0.999 and = 10-5 as the recom- mended default [46]. For each method,
of the compressors (i.e., the compression rate), we test k E
tune ') over {10-4 10 10,00, 1,0-,,001,11 10] and m over {10-4 10 10 1001,11, 1}. We found that the compressed methods usually have same op- timal learning rates the full alll-rrcision training. The best learning rate combinations achieving highest test accuracy are given in Table
Red-EF-SGD
Fed-EF-AMS
1
MNIST FMNIST
10
10-3
10-3
10
1
10-1
10
10-1
10
CIFAR-10
1
10-1
10
10
Table Optimal global (1)) and local (nz) learning rate combinations to attain highest test accuracy.
20

---

Under review as a conference paper at ICLR 2023
3
3
SCD-ul SCD-sign
9G0-uul
SGD-sign
8GD sign
SOD lopk O. 0.001
S0D-hwesig--0
SGD stcp bl
Train Loss
SGD fopk-0.01
Train Loss
SCD fie-dgn 0.05
Train Loss
SGD b8
SGD-tpp Hop.-opo-ooo 0.05
SGD-he-sgg-001
MNIST p 0.5
MNIST p
MNIST 0.5
10
10
10
10
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
-AIS-LUI
AAMS f.ll
AMS-Uu full--
AMS slan
AMS sian
AMS-+gg
Train Loss
AMS--0pp--000
AMSS-Iopk-O 001
Train Loss
AMSS
Train Loss
sice
AMSS-opp 1op.-oooo-.0..0 0.05
AMS s.gn-0.1
MNIST P 0.5
MNIST p 0.5
MNIST 0.5
10
108
10
10a
10
10
10
10a
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 8: MNIST dataset trained by CNN. Training loss of Fed-EF with TopK, Sign and hiavy-Sign compressors, and Stoc without EF Participation rate p 0.5, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-ER, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-EE Aa--EF-AMS.
2.5
Train Loss
SGD-ful
Train Loss
2
6GD-Ul
Train Loss
SGD-JI
8GD-sign
-SDD-iig
1.5
SC0C-topkk0.06
SGD
SCD topk-0..00 0.001
1.5
SGD-tw- sign--
SGD-tw-sign-e
slgn-0.01
05
SGD sto0 b4
8GD sloc
FMNIST P =
FMNIST p 0.5
FMNIST p 0.5
0.5
0.5
0.5
10
10
10
10
10
10
108
10
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
3
3
AMS--ul
AMS- full
Train Loss
MMS kopa- 0.001
AMSS-eign
Train Loss
AMG -he---h--gg--1111
-igg
Train Loss
AMS SI2D
AMS sign
MIS 1.00--0p--00111
AMS MMMS--h--gin--000
AMS
AMS 1M8-topk-0.00 05
AMS-hh-aign-0:1
FMNIST 0.5
FMNIST 0.5
FMNIST 0.5
10a
10
10a
10
10a
10a
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 9: FMNIST dataset trained by CNN. Training loss of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoc without EF. Participation rate 0.5, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-EF-AM
21

---

Under review as a conference paper at ICLR 2023
100
100
100
Test Accuracy (%)
MNIST 0,5
Mp
Test Accuracy (%)
p
Test Accuracy (%)
MNIST p 0.5
-9GD
SGD sign
slgn
SGD-sign
3GD-topk-0.00
SGD 9GD-hh--ign-0.0
S3D-stoe b1
SGD-topk-0.01
300-hr-sign-0.C
5G0
80D-topk-005
S3D slgn 0.1
0
0
0
102
10
10
10
102
10
10
10
10a
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
100
100
100
= 0.5
MNIST p
MNIIT 0.5
Test Accuracy (%)
Test Accuracy (%)
Test Accuracy (%)
AMMS-Ull
AMS-ful
-MM--uul
AMS--aig
AMS-sign
AMS sign
AMAS-1spt-0000 0.001
AMS-h--ign-0 0.01
AMS stoc-bl
A7AS-xxp--000
AMS-hu-agn-0--
AMS-axpp-0.0
AMS-huaaggn-::1
0
0
10
10
106
10
102
10
108
10
102
10*
108
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 10: MNIST dataset trained by CNN. Test accuracy of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoc without EF Participation p 0.5, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-EF-AMS.
80
FMNIST 0.5
80
FMNIST 0.5
80
FMNIST p
0.5
Test Accuracy (%))
Test Acouracy (%))
Test Accuracy (%)
60
60
60
40
40
40
S0D-Al
SGD-sign
BGD-slgn
SGD sigh
20
5O0D-topa-0.0 001
20
SGD-iw-sig-0
20
S0D -00---o---111
SGD-lop 1:0D-iopk-00 0.01
SGD stoo-bd
SGD
3G0-1opp-0.05
BGD-iw-sign.0.
SGD stoe-bil
0
0
0
10
10
8
108
102
10
10
108
102
10
10
108
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
80
80
80
FMNIST 0.5
FMNIST p
FMNIST 0.5
Test Accuracy (%)
Test Accuracy (%)
Test Accuracy (%))
80
60
80
40
40
40
AMAS-Uil
full
AMMS-A
AMS-sign
AtAS-aign
20
AMAS-topi-0.00
20
AMSS hw----i-----.0
20
AMS sloo b1
AMA5-tspa-0.0
AMS for din--ign--.0
AM45-4too- b2
AMS 0.00
AMS AMS-ttn-sign-011
AM45-ttec b4
1
1
8
80
10
10
10
10
102
10
10
108
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 11: FMNIST dataset trained by CNN. Test accuracy of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoe without EF. Participation rate p 0.5. non-iid data. "sign", "topk" and "hy-sign" are applied with Fed-EF, while "Stoe" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-BF-AMS.
22

---

Under review as a conference paper at ICLR 2023
3
3
MNIST 0.1
SCD
SCD-sign
S0D-agg
5CD RED-hh-sign00. 0.01
SGD si00-1 01
Train Loss
Train Loss
N
SCD-tw sin 0.05
Train Loss
SGD stoe 02
5CD-hvvagn-0
50D-4koo-a
-00D-ul
SCD-sign
960-topk-0.00
5000topk-0.0"
MNIST p 0.1
MNIST p 0.1
1000-ookk0000
102
10
10
10
102
10
10
10
102
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
-MM
-NS-UUl
AMS
sign
AMS sign
AMS-sign
3
3
AMS hh 0.0
3
AMB shcolbt
Train Loss
AMS topa-0.0 0.01
Train Loss
AMS AMSS-th-iign-..00
Train Loss
AMS b2
AMS topk- 0.08
AMS-thssig--11
stc0-b4
MNIST 0.1
MNIST p
MNIST == 0.1
104
108
10
10
10
10
10
10
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 12: MNIST dataset trained by CNN. Training loss of Fed-EF with TopK. Sign and heavy- Sign compressors, and Stoc without EF. Participation p 0.1, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-EF-AMS.
2.5
2.5
2.5
Train Loss
-GD-
SGD-sign siin
Train Loss
90D-ful SGD sign
Train Loss
SGD-sign
SGD topk-0.00
GDDhh-sign
5CD-ak00-81
SGD-tap -000------.0
(-DD-h--ign---- .608
5CD 100---too.0 02
SGD-iopk-0005
hrisggn 0.1
SGD-stoc-ol of
FMNIST 0.1
FMNIST p 0.1
FMNIST p 0.1
0.5
0.5
0.5
102
10
8
108
102
10
8
108
102
10
8
108
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
AMS
Train Loss
3
AMS
AMS topk-0
AMS sign
Train Loss
AMS aign--0-
AMSS tin---g---0011 01
sign
Train Loss
3
AMS stcp be
AMS stao-bt
AMS sign
topk-000000
AMS hvsiin--
AMS
FMNIST p 0.1
FMNIST p 0.1
FMNIST p 0.1
1
8
8
2
10
8
108
10
10
10
1
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 13: FMNIST dataset trained by CNN. Training loss of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoe without EF. Participation rate p 0.1, non-iid data. "sign", "topk" and "hy-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-BF-AMS.
23

---

Under review as a conference paper at ICLR 2023
100
100
100
Test Accuracy (%6
MNIST p 0.1
Test Accuracy (%)
MNIST p 0.1
Test Accuracy (%)
MNIST p 0.1
//
SGD tull
SGD-slan
SGD-sign
SGD-sign
800--1op-00.00 0.001
SGD-me-igg-000
SGD-stoc-bl
80Dew-algn-0
9GD-ropk-0.06
SGD-w-slgn-00
0
0
0
10
10
10
102
10
10
10
102
10*
10
10
log. Communicated Bits
log.
Communicated Bits
log. Communicated Bits
100
100
100
MNIST p
MNIST 0.1
Test Accuracy (%)
Test Accuracy (%)
Test Accuracy (%)
-MMS-UJI
AMS-1oph-0.001
OMB-xopk-0.01
AMS--ull
1MG-1op.-0.05
AMS-4
AMG-hr-sggn-0.00
AMS 9000011101111
AMS-tr--ggn-DD 0000
AMS AMS--tto--0
P
0.1
AMS MM--hy--ggn-...
10
10
106
10
102
10
108
10
10
10a
108
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 14: MNIST dataset trained by CNN. Test accuracy of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoc without EF Participation p 0.1, non-iid data. "sign", "topk" and "hv-sign" are applied with Fed-EF, while "Stoc" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-EF-AMS.
80
80
80
Test Acouracy (%))
FMNNIST p
Test Acouracy (%))
FMNIST p = 0.1
Test Accuracy (%)
FMNNIST p
60
60
60
40
40
40
SGD Jull
S0D-sign
-ign
SGD sign
20
300-ttpk-0.00 001
20
SGD hiesign 0.01
20
50D-aloo--1
1.DD-topk-..0
SGD ty-sgnn 0.05
5GD-4ko6-02
SGD SGD-h--sign-0.
800-atoe
0
10
10
8
10
102
10
8
108
102
10
10
108
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Test Accuracy (%)
60
FMNIST 0.1
Test Accuracy (%)
FMNIST p 0.1
Test Accuracy (%)
60
40
40
40
AMS Jull
AMGS full
20
AMS sign
20
AMS--iggn
20
AMS-ttagl AMS-ttopk-O.00 001
AMS hv-sign 0.01
AMS :too b1
AMS-topk--.00
FMNIST p 0.1
MMS stoc b2
AMS-hh-agn-001
MMS-5 SWSS-too
0
0
1
8
8
10
10
10
10
102
10
10
10
log. Communicated Bits
log. Communicated Bits
log. Communicated Bits
Figure 15: FMNIST dataset trained by CNN. Test accuracy of Fed-EF with TopK, Sign and heavy- Sign compressors, and Stoe without EF. Participation rate p 0.1. non-iid data. "sign", "topk" and "hy-sign" are applied with Fed-EF, while "Stoe" is the stochastic quantization without EF, 1st row: Fed-EF-SGD. 2nd row: Fed-BF-AMS.
24

---

Under review as a conference paper at ICLR 2023
B COMPRESSION DISCREPANCY
In our theoretical analysis for Fed-EF, Assumption 3 is needed, which states that [ Σi c( et,)) - Σi (At.: et,))ll I Bll
for some QA < 1 during training. In the following, we justify this assumption to demonstrate how it holds practice. To study sparsified SGD, [4] also used similar and stronger (uniform bound instead of in expectation) analytical assumption. As result, our analysis and theoretical results are also valid under their assumption. Please more related discussion therein.
(A..
B. SIMULATED DATA
We first conduct simulation to investigate how the two compressors, TopK and Sign, affect qAA- In our presented results, for conciseness we use n 5 clients and model dimensionality d= 1100. Similar conclusions hold for much larger and d. We simulate two types of gradients following normal distribution and Laplace distribution (more heavy-tailed), respectively. Examples of the simulated gradients are visualized in Figure 16 and Figure 17. To mimic non-iid data, we assume that each client has some strong signals (large gradients) some coordinates, and we scale those gradients by scaling factor 2, 10, 100. Conceptually, larger represents higher data heterogeneity.
130
The simulated gradients of heterogeneous clients, from N(0, ?2) with 0.01. The gradient on each distinct client is scaled by 2, 10, 100 (left, mid, right), respectively. Larger implies higher data heterogeneity.
Figure 16:
The simulated gradients of 5 heterogeneous clients, from Lap(O, A) with A 0.01. The x-axis is the dimension. The gradient on each distinct client is scaled by = 2, 10, 100 (left, mid, right), respectively. Wee the gradients have heavier tail than normal distribution. Larger implies higher data heterogeneity.
Figure 17:
25

---

Under review as a conference paper at ICLR 2023
0.8
Sign
Topk-0.1
0.8
Topk.0.1
0.6
0.6
6
0.4
0.4
0.2
0.2
5
10
100
1
5
10
100
Scale
Scale
Figure 18: The compression coefficient 9.4 in Assumption on simulated gradients. TopK is applied with sparsity k 0.1. Left: Gaussian distribution. Right: Laplace distribution. 9 is computed by = o
- where 6(x) = 1/2 Σ C(A., + ex,)) and x 1/2 Ei=1(44 (Ar,; + er,)). The dashed
curves are respectively the compression coefficients oe from Definition 1, which is calculated by replacing ((x) C(2
E A,, + ex,a). We that in all cases, QA 1.
We apply the TopK-0.1 and Sign compressor in Definition to the simulated gradients, and compute the averaged 4A in Figure over 10 independent runs. The dashed curves are respectively the "ideal" compression coefficients de such that [[ Σ D.,i + - " (Ar, + ex,:) s (Ar.i + et.;)] ?] from Definition 1. We see that in all cases, Q4 is indeed less than 1.
[ Σ
This still holds even when the data heterogeneity increases to large as 100.
B.2 REAL-WORLD DATA
We report the empirical q4 values when training CNN on MNIST and FMNIST datasets. The experimental setup is the same as in Section We present the result in Figure 19 with r = 0.01 under the same heterogeneous setting where client data are highly non-iid. The plots for other learning rate combinations and iid data are similar. particular, we see for both compressors and both datasets, the empirical CA is well-bounded below throughout the training process.
0.99
Empiricalq
Empirical
0.99
Empirical
0.98
0.98
0.98
0.96
0.97
MNIST FMNIST
MNIST FMNIST
FMNIST
0.96
0.97
0.94
0
10
20
30
40
50
0
10
20
30
40
50
0
10
20
30
40
50
Round
Round
Round
Figure 19: The compression coefficient q,4 in Assumption 3 in our experiments (Section 5) for CNN trained on MNIST and FMNIST dataset, averaged over multiple runs. 1) 1, r) 0.01, non-iid client data distribution. Left: Sign compression. Mid: TopK compression with & 0.01. Right: TopK compression with 0.1.
26

---

Under review as a conference paper at ICLR 2023
C PROOF OF CONVERGENCE RESULTS
In this section, we provide the proof of the convergence rates of Fed-EF. For illustrative purpose, we first present the proof for the more complicated Fed-EF-AMM in Section C.I, and the proof of Fed-EF-SGD would follow in Section C.2. Section C.3 contains intermediary lemmas and Section C.4 provides the analysis of Fed-EF partial participation.
C.1 PROOF OF THEOREM 2: FED-EF-AMS
Proof. We first clarify some notations. At round i, let the full-precision local model update of the i-th worker be Dr, the error accumulator be Ct,i, and denote A.,; = C(g., + ex.)) Define A. J E A,,,, A = -: A., and E = E C, The second moment computed by the compressed local model updates is denoted as 12 = 3 + (1 11-Bay 11-,,,),, =2 Also, the first order moving average sequence
and é; = max(0;-1; J.).
m, = - + (1- - -,) and mi = B Bim + (1- 31 )
where m. represents the first moment moving average sequence using the uncompressed local model updates. By construction we have mi (1 B1) Σ!= AA,
Our proof will use the following auxiliary sequences: for round 1...., T,
E41 = (1-
Σ
g Er,
E,+3
4/11 = 0141 1) Vūt +
Then, we can write the evolution of 02 as
E1+1
0+1 =041
Vūz
=0 (1- (1-31) Σ1 81-1 A, + (1 B1)
+1
g(+l-1 &
-==]
Vū: +6
(1- - B1) Σ E+= BP_T (A, + (1 - 3)
0 11
Vo+ +E
(1- B1) E BI-TET -1
m/
0
Vor +e
V
E,
mf
0, 11 VO-ITE
m7(
V E
Vox +c
Vut-1+e +E
( 0 1 Vo, +e
ml
+ 1
Vo )
/ Vi-++t
m
0
+ nDrE,
Vo, +c
where (a) uses the fact of error feedback that for every i E [n], De, + Eet1i εr,1 = at initialization. Further define the virtual iterates:
Dr, + et, and
31
m
Ft+1 == 8141
11
81
/ 03 +
27

---

Under review as a conference paper at ICLR 2023
which follows the recurrence:
31
mi
T++1 = -8/
11 - 31 Vēl te
my
31
m
8
1f
1i + "I 1- B1 0/ +
nDr 87
B1 + - -1); +
I-31 m4-1 + +I
0
1
Vūa +e
m4-1
Å.
8 " 1
11
+ +nDDE
31 V0 +E
Vē, +
31
St
+ "1 Br
Damb_1 + D1E
V0 +
The general idea is to study the convergence of the sequence Tt, and show that the difference between It and Og (of interest) is small. First, by the smoothness Assumption we have
L f(141) S f(x)) (Vf(z)) -00-)--))) 21) 11141111 xel1?
Taking expectation w.r.t. the randomness at round t and re-arranging terms, we obtain
B[f - f(x))
$ 5 (V
/00 }1 + + (V((
A
81
Demb_1+ + DrEi)
1
B1
172 T E
A.
31
+
Dimi-1 D(E,1?]
2
Vo +
1-
=nnB -
A
(x:),
B1
DemiL1 DrEi)
Vo +
1
Br
11
L
A
81
A
Dam D1E
+ + (VS(0.) vs(a)),
2
Vūr
+
1- B1
Vor +
111
IV
Bounding term I. We have
A
I = E ((:),
Vo } - nnE (V)(
tor Ai)
Vū++e
A Vo-1+e )
< 1 (V)())),
mp KG
where Assumption 4 on the stochastic gradient magnitude. The last inequality holds by simply bounding the aggregated local model update by
| .ll
11
k Re
S
KKG
71
and the fact that for any vector in Rdd the la norm is upper bounded by the I norm.
28

---

Under review as a conference paper at ICLR 2023
Regarding the first term in (4), we have
-n (V.))), A.
(0() D. -KK +
-nnB( U |V
( +
V)(0.)
=E
+ 1/
- -,
+e
0--1+e"
mi
E B (0.)
V)(O.)
E
K Σ
m9i + +mKV
(k)
4n/ (1+
01-1 +e
C +e
(6)
Ty K
G2 [(0)111
(1 +
(1 1---1 1-
n ( VRV f(0)
a
K
ΣE V + +VV(()))
E
(ú--1 + +2/1/1 in(0=-++))1p
where (a) uses Lemma C.6 and (b) is due to Assumption 2 that Dt.5 is an unbiased estimator of (
To bound term V, we note the inequality that (a, b) < a 20 O. Therefore, we have
for any a, b E IR and
K 2
E
T
E
n
K
-
2K
V
K
K
V
f 12
m
2VE
2nK Ve
mk
E
V ((.))
m
E
K
V
v.(0.)11
2/
2n
i=1
k=
K 2/
T.2
n
K
s E
(0.))
+
E
0.11
2
where the last inequality is result of the L-smoothness assumption on the loss function f((x). Applying Lemma C.1 to the consensus error, we can further bound term V by
KKK E
KLL
V
[[]
K(22 + +6Ko)) 30n [[]])))))))
2/c
2
47mK
K2
E
[[
(0²
-6K6K))))
64Ve
2//
V15(1-92)
when we choose V)t S EKL. Further, if we set m <
we have
4n + K²
60
64
G +
+
(1 92)2
196
49
Hence, we can establish from (4) that
mm K
5mm 12
I
E B[I
(02
6Ko)) +1)++110 m K D.lla.
(5)
8/C
2/
29

---

Under review as a conference paper at ICLR 2023
Bounding term II. By Lemma C.5, we know that ||E]]| I tp KG. Thus, we have
2mg 1-9²
and by Lemma C.3, |mm/l 1
B1
31 Dim4-1 + DrEi)| + - -Vf(0.))
11 S B| (V
Demiy + DrEi))
1-B1 B1
1- B1
31
Dimi-11 + D&Eill
I-P: mh + E,
31 Demb- + Dr&il]
+ 1²2 LE(1]
f +e
1- B1
7 G
S Smc.KGBBIIDD
B D.llil:
(6)
where C1 :=:=000
81 T-9i T-qe. and the second inequality is due to the smoothness of f(0).
2g
Bounding term III. This term can bounded as follows:
31
III I LE
Vūe 11 + +, LE [1]
Demt_ - - [1²]
1- B1
1 L [[| A, |2] + 2/ LE [|| De(
31
m4_1 - Ex]1
1
31
T2 K2 120n 112
[ [0,))] 4n r²
ne
20n m x L3
(02 + kK + 1ス
(7)
where we apply Lemma C.2 and use similar argument as in bounding term II.
Bounding term IV. Lastly, for term IV, we have for some p > O,
IV
(8)
n/ (V)(O.) V(()))
Vū--+ >} + tR (VS(0.) VI(a.), 1
A.
V0 +E Vorite ا اممر
(a) nP E | + " [[I))(())) vf(x:)1 L
I-p1 m +
[II|
2c
2p
Vo-1 +
(6) pm(T; K2 + 600m Kt 2
2pmmi K
10pmi K32
| 1(0.)
(a2 + +6Kog)
en
2
m/- + E,
11 TTRCLKKE
EE
[12]
E D.Il
2p
8y-1 +c
Ve
(60m? K2 1)
2pmp K
10pmp (0² +6Koy)
E
V f().)
0²
en
12
88
C
E
ml
E [1E
(9)
De (1 - B1)
2
Ve
where (a) is consequence of Young's inequality (p will be specified later) and the smoothness Assumption 1, and (b) is based on Lemma C.2.
Now that we have bounded all four terms in (3), the next step is to gather the ingredients by taking the telescope summation over = 1, 1..., T. Before moving on, for the ease of presentation, we first do this for the third term in (9). For this term, according Lemma C.3 and Lemma C.5, summing
30

---

Under review as a conference paper at ICLR 2023
over t 1..,. T, we conclude
17 L2
37
Pe
(1 31
T
B[I + Tr o² 20T + +6Kog)
(60m2 + 1)
p(1 -31)2E
L22
16T K 8² + LO 6Koz)
Kn K2 L2 + 1)
E [(IV
p(1 02
(60m) 2 + 1)
B [(IV1(
pe
4T 4T
M (0² + +KKgg)
o²
(10)
pme
Pc
0f with C2 == (1-8.)² +
1g
(1-9-)2-
Putting together. We are in the position to combine pieces together to get final result by integrating (5), (6), (7), (9) and (10) into (3) and taking the telescoping sum over I.... T. After
re-arranging terms, when vi min { Xitt") ). have
(1-g)v=
[f f(11)
5T
T mKK
E ((
(0² (o²+6K0g) + mGK
8VE
2/E
n GR.K22
+ + K Σ E D+lla+
Σ
Ve
12 K2 + 120 12
1f o²
[(
TEE
20T 20TH K3
T
(02 + 6Koz) + t
Σ D11
km (60m) K2
2T pT K
10T 10T K3
E
0²
(0 +Kox)
6
en
207² C222222
C2KT2 2²
(60m) 12 +1) Σ E[IVS(())
pe
pne
20T 20
(02 +6Ko)) + 1 C T
Σ Drll
PE
Ve
T
T1
E [V]
+ T2 (02 + +6Ko²)
+ +T 02
Y4
D|| 2 LL Σ El D.II1
(11)
31

---

Under review as a conference paper at ICLR 2023
where
MpK
Lf2 + 120n K L²)
Ti =
8//E
K2 L2 +1)
22 (60n) +1)
PC
S Mi 2T
+ 2mmp
+ An
8VE +
(12)
5TTM K212
10T poT K 20
20
T2 =
2/e
pc
4T 17 KI. 2T K
T3
PNE T4 - (C +1)KG² + TRROLKKEEE CRRC
Ve
where to bound Y use the fact that rn S SKL We look the upper bound (12) of Y which contains 5 terms. In the following, we choose = Ln in (9) and (10). Suppose we choose < 1. Then, when the local learning rate satisfies
(1 -1-- Vc
Vc
Vc 1/3 ) LJ
m I min
'8L' 4(1 + +2)) 128mL' 256C2mL
(6800)
K
< Ve min
{ Ve' (1 (1+ 92) max 16, 21) 3//1/3
2(1 - 92)L
8KL
each the last four terms can bounded by
y 48ve"
Thus, under this learning rate setting.
Tı MK K
16
Taking the above into (11), we arrive at
T
mIK V
E B[[VS[O) < s(x)) E[S((T((T)))
T2. + (o2 (o²+6Ko²)
+ Y, 0² r d PoR
Ve
where Lemma C.7 on the difference sequence D, is applied. Consequently, we have
-(x1)- E[((T++))+ T. (a² + +KKo)) T, o²
E [|V s
T
TiTK
(C++1)G2d 2mmFLKGGd
MICILKG'
TVe
Te
Te
f(z1) - E(f((TT))
+T (0² + +6K0g) +
WiTK
(CI (CI+1)GPd 3mmGGLKG'
TVv
Te
where we make simplification at the second inequality using the fact that C < C2 since C 2 1. Moreover, T2 and Y is defined as (recall that we have chosen Lm)
KL²
20mm L 10mp2K2 2
20mm 20 C3
+
2Ve
E
5np KT2
(30 + 2013
2
4rmy
21T
4r
mp L + 4C2)
T3
+
766
32

---

Under review as a conference paper at ICLR 2023
Finally, to connect the virtual iterates 2a with the actual iterates 0,, note that 81, and f(2r+1) 2 f(0") since 0 arg ming f(0). Replacing T/ and I33 with above upper bounds, this eventually leads to the bound
f(0i) - -((0))
KT2
((C30+200)) (o2+6Ko)
E [
[ 2
T
mMlK
(L +4C7)
(C1 (CI+1)Ged 3mCLLKGPd
d²
ne
TVE
Te
which gives the desired result. Here use the fact that CN S Cf. This completes the proof.
C.2 PROOF OF THEOREM 1: FED-EF-SGD
Proof. Now, we prove the variant of Fed-EF with SGD as the central server update rule. The proof follows the same routine as the one for Fed-EF-AMS, but is simpler since there are moving average terms that need to be handled. Note that for this algorithm, we do not need Assumption that the stochastic gradients are uniformly bounded.
For Fed-EF-SGD, consider the virtual sequence
It+1 81+1 1/ē411
0, n 1/
0, Σe i=1
A ; +
e241,5
=0, n 7/ct
Zx m
(13)
where the second last equality follows from the update rule that Di, + 64+1 = De, + ee, for all i E [n] and t E [T].
By the smoothness Assumption 1, we have
L. f(1+11) S f(x)) + (V)( 2z) + " || - xell?
2
Taking expectation w.r.t. the randomness at round t gives [[f((++1)] f(x)))
172L E [ [
((VEE((V A,)]
172 E |
= =- A,)I +
|| + B (V)(0)) - vf(xx),
(14)
2
We can bound the first term (14) using similar technique as bounding term I in the proof of Fed-EF-AMS. Specifically, we have
-nE[(V A.)]
- (V -
-A, + m) (VV()))
= KE (VV (
Note that the second term in the above be bounded in the same way bounding term V in Fed-FF-AMS (without the v/e factor). Thus, with 1)I S SRI we have
3rm K
B (O.) A.) < mph KE | (0))
[[IVS(0)))]]
(0² + 6Ko
4
2
k K
5 K2
E [[IV)(()))I]]
(02 + (Koz)
The second term in (14) can be bounded using Lemma C.2 as
72L E |
[|
< n K" L (60y) 22 + 1)E [(.))
2
2n KL
13 o +6Ko))
33

---

Under review as a conference paper at ICLR 2023
The last term in (14) can be bounded similarly in Fed-EF Fed-EF-AMS by
n
(V V f(z)), Ai)
<
A, 12]
[(( V[(x))
2
2p
2
[1 + 1/2
E [||11
(15)
2
2
(6)
L
+ n 0² + K + +6Ko?)
2nd K2 (60n) K 2² 1)B
2
n
+ K2
L
1
(60m)
L2 + 1)
2
1- q2
2
==1
16
80n
(1 p2- (0² + [Kog)
+ (1 g2)
where (a) uses Young's s inequality and (b) uses Lemma C.2 and Lemma C.4. When taking telescoping sum of this term over 1.., T, again using the geometric summation trick, we further obtain
(V V(()))
+1) E[[ISS(())))
Σ
2T C
0²
(Kog),
n
where C1 = 1 +
19a
Now, taking the summation over terms in (14), we get
[1-
T
[1 (- MiK + (-
K<20 + 1)
Σ E [[IV)(
2T (C1 + 1)KL 107 ()
Since m7 I SKL, we know that k2 + < 2. Therefore, provided that the local learning rate such that
2KL max(4, nC1 +1) M
have
mi K
T
[[ $ $(() - E[s(x++)]] + 2Tt + 1)KL 0²
E
8
n
+ +10T + 13 +KKo)) +6
leading to
2
E 1 (0.))11 < [(x) [[((
(1 + 1)L 8
T
miTK
n
+10m (C1 + 1)
ʃ(0,) s(0)) TK
2m 1)L x²
+
n
+ 10mi (C) + 1)K2 6Koo))
which concludes the proof.
34

---

Under review as a conference paper at ICLR 2023
C.3 INTERMEDIATE LEMMAS
In our analysis, we will make of the following lemma on the consensus emror Note that this is general result holding for algorithms (both Fed-EF-SGID and Fed-HF-AMS) with local SGD steps.
Lemma C.1 ((45)). For S SLK. for any round t, local step k E [K] and client E [n], under
Assumption I to Assumption 2, it holds that
B[110% 0,11 s Kn22 + +KKoz) 30n K'E E [f(0))
We then state some results that bound several key ingredients in our analysis.
Lemma C.2. Recall Å. E De,i- Under Assumption I to Assumption for Vt, the following
bounds hold:
1. Bound by local gradients:
K
E
|
E
n
2. Bound by global gradient:
K o² + 20m L2 0022+6Kg 6Kog)
E [+1] < (2n) K2 + 12
+
n
Proof. By definition, have
E| Bl1
mgr.i
(k)
12|
" n
K
K
$ [[|
v5( )1 +
12]
Si (:(o!!)) [|?]
n²
m| K
where the second line is due to the variance decomposition, and the last line is result of Assumption 2 that the stochastic gradients are independent and unbiased. This proves the first part. For the second part, note that
K
E | 12] =
(K) m99s
Kn.f(())
2n K E
(0) + 2m
K
(k)
K
(1.))11
91,1
n
k=1
2n
K
= = V f(0
E(I)
(M)
- v.((()))
n²
2nd n2
< < [1
E
Σ
(k)
+V/(!!
(..())))
2nf n²
K
< 2n 2 (()))
+
E
Σ
v((((( + ++((((
v..(6.))
1=1
35

---

Under review as a conference paper at ICLR 2023
The expectation A can be further bounded as
T2
K
A 21E [1
9
(R)
(..(0
2E
VA(.))))
k=1
k=1
(0)
K
2 2nKo² 2 + 22nK
k=1
(6)
E S 2nKo² + -2nKL² Σ>
B 0el1
km
(c)
x 60nf 2 K L (1) =2
2nko2 D + 6Ko
where (a) is implied by Assumption 2 that each local stochastic gradient It.6 can be written as (k) Dr. = (O + St,i where et; is a zero-mean random noise with bounded variance o², and all the noises for & E [T], i [n], k E [K] are independent. The inequality (b) is due to the smoothness Assumption I, and (c) follows from Lemma C.I. Therefore, we obtain
R 0² + K2 +6Kog)
111 < (2n) + 120m K 22)11111
which completes the proof of the second claim.
Lemma C.3. Under Assumption I to Assumption 2 we have:
|m/|ll S n KG, for Vt.
Σ E m1 s (2n 120ml K L
E (())))
t=1
T Tnf K 0²
+
+KKoz)
n
Proof. For the first part, by Assumption we know that
|m||l = 31)1 Σ 8T-
A
1=1
K
= (1- 31)
3
-
M
19
(k)
1=1
< K.G.
For the second claim, by Lemma C.2 we know that
K 0²
E [1 < (2m) k2 K2 + 120 B +
K3 +
2=0'2(2+66K3, 6Koz)
36

---

Under review as a conference paper at ICLR 2023
Let Dr, denote the j-th coordinate of A. By the updating rule of Fed-EF, we have
E |1 E [|[[11 - -11 Σ A 17
7=1
(1--B1)
j=1
(
(1 - 31)
E
81 ا
j=1
r=1
$ (1 5:) Σ
B A 17|
T=1
$ (21 + 120m xT)) - B1) Σ - [IV [(0)]
T=1
2 K 0² + 4
- 200 (o² + 6Kog).
where (a) is due to Schwartz inequality. Summing over 1.... T, we obtain
E | < (2n K2 120n K² 3)
3 E [[,))
Tm K 0²
+ 4
I <2n K22 + 120m LLL3)
Σ
E3 [0)))11
Tní K 0² + 220
+4
n
which concludes the proof.
Lemma C.4. Under Assumption 2, we have for Vt and each local worker Vi E [n].
4n/ 2
||e,,112
(1 (1-92)2 Vt,
1/ K2 (60m) K2 - 1)
92 - (
[|[[@r+1|13 [|
T=1
16m 9² K +
80m q² 2 3 L2
0²
(1 Q2)2 (0² 6Ko7).
(1 Q2) pn
Proof. To prove the second claim, we start by using Assumption 3 and Young's inequality get
1 [ + E
I + 1
+ 1
< ( + 1)
+ 21
< 1 + q²
2q
| 2
A 1
(16)
1 q²
37

---

Under review as a conference paper at ICLR 2023
where (16) is derived by choosing p initialization G1,1 vi, we have
1-g" 24
and the fact that q 1. Now by recursion and the
E[ [|?] 5
24
q
B [|?
12
2
==1
1p K" (60ml
(a0np?"" 12 1)
Σ
1 o²
y
V [(0+)11
- 9²
2
==1
9
80n
90
+ 02)2
0²
+
dpy2 (0² +KKg)
which proves the second argument, where we use Lemma C. to bound the local local model update. In addition, we know that | S vh KG by Assumption 4 for any t.
o² follows from (16) by similar recursion argument used on (1 23
The absolute bound ||ex, | <
local error Ct.i, and the fact that Icc S max {ac, 9A} = q-
Lemma C.5. For the moving average error sequence & it holds that
R222
| S (1-
Vor
T
8q2 K2 (60m/ 12 + 1)
T
[[[1&111] ك
Σ EE [
(1- 21-
807 1
+
(02 + 6Ko
-2)
(1 (1-9² q2)²
Proof. The first argument can be simply deduced by the definition of &, that
||&||| (1 --111 Σ o a
2g
< ||e,,1l1
q2
Denote the quantity
+ q²
K, := Σ
T V [(00))1
2
T=1
38

---

Under review as a conference paper at ICLR 2023
By the same technique as in the proof of Lemma C.3, denoting Et, the j-th coordinate of e, can bound the accumulated error sequence by
E || [|1((1 31)
Σ
Bf
T 2111
T=1
s 81)
E
j=1
(4)
S (1 2
E
8
$ (1 - 31)
E [| [|
T=1
(6) 16 2 92 K
80
0²
(1 02)2 (0² + 6Koz)
22)2
4(1 ;1) n K2 (60n) 1 + 1)
Σ K Kr
1-
where (a) is due to Sauchy-Schwartz inequality and (b) a result of Lemma C.4. Summing over t= -,..,, T and using the technique of geometric series summation leads to
E [|]]|]]]] v G 0²
P (1 Q2)²
(0" + +6Kog)
(1 -2
4(1 B:)gg mp K2 (60m) 12 1)
T
Kr
--
(=1+=1
16TTp122 K 0
80T 80T K (0a 6KKz
(1 122
4 22 (60m) K2LL + 1)
T
ΣΣ
1 1-92
q2
16T'142K (1 22)
SOT 22 L2
(a2 (02+6Kog)
(1 -1-6 -22
8q218 K² (60n) x² + +1) T
Σ E B[(
(1 (1-9²) 9²)²
The desired result is obtained.
4n 0 x2
Lemma C.6. It holds that Vt E [2], Vi E [d], G, S
G².
(1-
Proof. For any t, by Lemma C.4 and Assumption 4 we have
|| = |IC(A, + et)
< |IC(A, + +e) - (Ai + +e)) + (A. + ez)
< 2(9² + +1)1Aa+ eel2
9
s 4(9² + k2
(2-
41 k2
G²
(1 q2²
39

---

Under review as a conference paper at ICLR 2023
Consider the updating rule of 0g maxfus, 8(-1)- We know that there exists a [t] such that it = Dz. Thus, we have
92 G2,
,, 8, = (1 82)
Σ 82 T 22
91,1 S
(1 (1-92)²
which proves the claim.
Lemma C.7. Let Dt =
be defined as above. Then,
Vo--te
Vocte
T
d 6
Σ
Dill S
Ve Σ
Dz 2 S
Proof. By the updating rule of Fed-EF-AMS, i--1 S 0e for Vt. Therefore, by the initialization 0g 0, we have
Delli
VoL.t +6
t=l
00.s te
Vor
d
Ve
For the sum of squared l2 norm, note the fact that for a 2 b > 0, it holds that
(a (a- b)2 - (a - (a + b) = =a² 6².
Thus.
Σ
1
1
)²
10--1. +e
Vūn, te
t=1
T
1
01
+
0,,te
(=1
which gives the desired result.
C.4 PROOF THEOREM PARTIAL PARTICIPATION
Proof. We can use similar proof structure as previous analysis for full participation Fed-EF-SGD as in Section C.2. Like before, we first define the following virtual iterates:
1
F++1 0,+1
es+1i
0 n
A
1
Σ
Cetly - - Σ e441
m
iEMi
i
1
= 02 A.A..
Σ
Cz,
el,
(17)
m
iEMi
M
1
=0; n
7) m
Cl1
i=1
24 A.....
40

---

Under review as a conference paper at ICLR 2023
Here, (17) follows from the partial participation setup where there is accumulation for inactive clients. The smoothness loss functions implies
f(z+11) & f()) (Vf(z)), z1) + / $11241 x2ll?.
Taking expectation w.r.t the randomness at round t, we have [[ - f(x))
Tf² 18 [ [e
<>b At.Me)) +
11
2
11² ++
(VS(0,))
B "BII
[2] + (VB(((()))) - ( Ac..))
(18)
Note that the expectation is also with respect to the randomness in the client sampling procedure. For the first term, since the client sampling is random, we have E[A.,M,] = B[A.]. Thus,
I= E (V f(0)), A..M.)) 1 (O.). A. MKVJ((0.) + MKV KVV.(())
K
->>KK
v ((:))) 77 (V.)).)
(Vi(0 Vf(O.)))
nvK
1=1
(4)
ME -m ([V)
K
VF(0))1
K
K
V((O)))
ff( [2]
2Kn
2Kn
(6)
K
mm KI [1V 1(0))
[IIV (0.))1
1/t KL2
n
K
5nl K(o2 + 6K + 30n/ [IV
E
)|
2
2kn
i=1 k=1
K
5mm
K2L2
(02 + 6Koz)
m77h
V Si )|3]
4
2
2K
1=1 k=
when 17I S SKE. where (a) is result of the fact that (21, 22) || because of Lemma C.I.
+ ||
|| 22 (b)
For term II, we have
KL II 1 KL d²
12
B(11
21
2n(n
3n mi K2 L(30n) 22L
15 K 3
3n K
+ C
(a² + +KKo))
+
07
2m with C n-m Furthermore, we have that
2m
2m
2
III < 27 LE Σ
et,
1
B[IAA.MM.11..
E
2
The second term is the same as term II. We now bound the first term. Denote ēz,s = = De.i - A..- we have
E
177
=
m²
1
Ee.
E.M
Σ lfi Miler + Σ lli & MeJecd1
1
1=1
41

---

Under review as a conference paper at ICLR 2023
By the updating rule of Czt the inner expectation, conditional on e, (ct,1 Ct,n), can be computed as
m
m(m- - 1)
E, + 11 -
m
Σ |ee
T
n(n - 1) (t)
n
+ (n - m) (n- m - 1)
m(n - m)
Σ
Σ et.j
er, +
n n(n2 1)
n(n 1)
in
m
n
E ,,, 1|
m(n m)
Σ
C,,
+
n1 m
Ci,el
n
n(n 1)
n
i=
i#1
i=1
m(n- m)
n
m(n m
n
Σ
Ct, +
et,
n nnn - 1)
n(n - 1) (tj
igj
m
71
e1,5
2
m
n
C 1
m(n m))
Σ
"
(ér,éess + tt,ee, - ((,51,))
T
n
n(n - 1)
1=1
it.
m
n m
Ei,1 21?
1=1
m(n m)
n
m(n m)
n
Σ 1=1
(er,s - ex,))12 ex,))1
Σ (1 + 11))
n(n
1)
n(n 1)
1=1
m(n m) nin - 1)
1
(1e + 11ec,
T n
Therefore, by Definition and Assumption we obtain
m
mq² BII
(er. + ++,+) n
e1
n
m
n
m
SEg
(n m)
n
(2g² 1), 112 P+
mn(n
1)
m(1 1 + 7)2² + (n - m)
m(1 + 1/7)g²
Elll
et,ill
B[I
A.. |1=]
i=1
i=1
(n - m)
((2g² + 1)]le,, + 2 11.1%)
mn(n 1)
i=1
We have by Lemma C.I that
20q2n K E| 11| 5 (1- (1- (a² + (Koz) + 60n2 2 K2
1
1 + q²
)d (-T
1 1-6 x2
2
E|| 11 11 < 5n K(0² + 6Koz) + 30n k E [
which implies
(n - m))
(229² + 1) + 2
mn(n - 1)
i=1
(n in-m! m)
70q2m2 K
(o2 + 6Koo)) + 180n K2 K2
1 +
d²
BB
E
[IV
m(n 1)
(1 92yz
q²
2
T=1
k0n
E [[IV
(1 (1-97 91-
42

---

Under review as a conference paper at ICLR 2023
Recall q max Let (1 (1- -22)//p²² We have
m(1 + +)q²² + (n - m) =1 (1 (1-9) (1-92)
< 1,
2n
m (1 + 1/7)g² m(1 + q2)
2mq²
n n(1 q²)
n(1 q²)
By the recursion argument used before, applying Lemma C.2 (adjusted by n2 /m3 factor) we obtain
1 m
n1
E
1=1
2mg"
(1 (1 - r²) m
t-v πt
K
(i 7, [P] + The K o²
5 111 (2) r=1
2m
m
n2
n
1=1 k=1
2n(n m)
70q²' K
180m 2 q² K2
1 + q²
+ (1 - 9²) mm)m² (n 1)
(0² + +6Ko
Σ
)r E
| f(. [[]
[[]((111111 92)2
1 q²
2
60
E [ [7]
(1 q2)2 n
92
(1 - ))) 1 )
4n Kn
5 (1 72 mm
|1²
2n
(1 - )
280m 92 (n m)K
(0² + {Koog) + 720nf (n K2
+ q²
B [
(1 q2))mmm
(1-
2
240 q2 - m)k (1 - 92) m2
E [(.))(
Summing over t 1,.... T gives
E
1=1
Y=1
4nf
Anp
o
4Tnig Kn
q²) m
(1 (1-9" pm
k=
280T 7/ (n m)K
16807/ q² (n m K2 K2
T
(0" + +Koz))
+
(1 - mm²
Now we turn back to (18). By taking the telescoping sum, we have
E[f(x - f(x1)
< __m
T
E
[(VOOI +
5Tm2222
(02 (02+6A6
+6Ko,)
TP 2Kn
T
E
K
V fi (PP
4
2
1=1
KL
12 L
0²
E
211
m
n(n 1)
t=1
31ya 2 1/ C² K2 L(30n 12 +1)
T
CrT (0² + 6Ko +
3T C
E [[
m
m
m
8n7 2T
T Σ
K
E
|P| +
(1 - q2)3m12 02
g2) Pmm
k=
560T n2 (n- m) KL
13 (m m KL
(02 6Ko
E [[] [.].
(1 92 pm²
(1 92 3m
43

---

Under review as a conference paper at ICLR 2023
When the learning rate is chosen such that
m I min { 66' 96C"n' 53760(n m) 4nj 32C KL'
m
we can get
T
f(0i) - f((0)
S m²
0²+ g 3rmCC"L,
[[]V)(
+
+
o
T
mIKK
m
5ml KI? +
15mm
560m - (m-m)lm 10 + 102 6Kog)
2
m²
where C1 = /21 22)². Denote B = n/m. When choosing 1) = (VKK( ?11 = 0 rate can be further bounded by
1
the
KVTB
T
0 -
VB
K
E [[V
T
vTKm
VTKmB
vTKm
VTmB"
VB
(0 + +6Ko?))
TKB Km
VKKm
which can be further simplified by ignoring smaller terms
π Σ
o( v
f(01) f(0))
((0))
VTKm 0² + VK
VTm r
Vm VTKm
This completes the proof.
44

---

Under review as a conference paper at ICLR 2023
Algorithm 3 Fed-EF Scheme with Two-Way Compression
1: Input: learning rates V,, M/t+
hyper-parameters 31, $32.
2: Initialize: central server parameter 01 E R2 C R24 e1, the accumulator for each worker;
mo = 0, 0o = 0g = Φ1 = He = 0; 0, = 01 for all i [x]]
3: for 1,... .,.............................. T do
4: parallel for worker E [n]] do:
5: Receive H, from the server and set 00,7 0 + He
Download compression
6: for k = l,..,, K do
Compute stochastic gradient (k)
9t,5 at (
7:
Local update 0(A++1) 0 m9t.; end for
(k)
8:
9:
Compute the local model update A., 0 (K+1) -0; 02
10:
11:
Send compressed adjusted local model update De.; = C(Dr,i + ex,i) to central server Update the eπrо Et+11 = Ct,i + D..: A.,i
12:
end parallel
14:
Central server do:
Global aggregation Â, 1 Σ À
15:
Compress 11, ((A,+0))
Fed-EF-SGD
17:
m, 81m4-1 + (1 (1-31)4 B1)
Fed-EF-AMS
18:
U = 320 + (1 32)
ú, = max(U;, 12-1)
19:
Compress H; = C( my
+ )i)
V0,+c
20:
Update server error accumulator Φ1+1 = @e + (0t+1 - 0²) He
21:
Update global model 0.+1 = 0₂ - -, and broadcast H, to clients
22:
end for
D TWO-WAY COMPRESSION IN FED-EF
As discussed in the paper, our Fed-EF scheme can also be combined with two-way compression, for both uploading (clients-to-server) and downloading (server-to-client)) channel. This can lead to even more communication reduction in practice. The steps can be found in Algorithm 3. Next, we briefly discuss its impact on the convergence analysis. For simplicity, we will focus on two-way compressed Fed-EF EF-SGD here, while same arguments hold for FeM-EF-AMS. The general approach is: 1) the clients transmit Á, to the server which compressed; 2) the server again compresses the aggregated update Â and broadcast the compressed H, the clients, also using the central node. Note that this approach requires the clients to additionally store the model at the beginning of each round.
feedback
To study the convergence of Algorithm 3, we consider a series of virtual iterates as
0 01-1 1/1++1
0, n + dr+1)
0,
Σ À +2
1=1
0 A
45

---

Under review as a conference paper at ICLR 2023
where we again use the fact of EF that P++1 + H, = o, + Á. Then we can construct a similar sequence 24 as (13) associated with 0g by
T++1 = s.+1 7 n/,,-
Then we can apply same analysis to derive the convergence bound as in Section C.2. The only difference is in (15), where the second becomes
L²2 Ell + ++1 S 1 1 LB ||
(19)
The first term can be bounded in the same way in (15). Regarding the second term, we can use similar trick as Lemma C.4 that
11 |1 A. C(oi A0)
S <ēllor + -1112
+ 2
24
< 2
|
|
oz
Then, by recursion and the geometric sum, || 1| can be bounded by the second term in above up constant. We can write
E
< E A, + & - [|-]
- 3 A [ E [1l + + + [12 I1]).
As result, it holds that [[1 < OE || since E ||||e||]] O [|]))]] by Lemma C.2 and Lemma C.4 under our assumptions. Therefore, (19) has same order as (15). Since other parts of the proof are the same, we know that two- way compression does not change the convergence rate asymptotically Fed-EF.
46


Reviews:
[{"review_id": "u_hCck9ZRyF", "reviewer": "Reviewer_FJCK", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In the paper, the authors consider the federated learning problem. The authors provide an algorithm that compresses the gradient before sending it from client to server (to combat communication cost), accounting for error of compression from previous iteration. Two versions of the algorithm is presented: Fed-EF-SGD and a momentum based FED-EF-AMS.  Theoretical convergence analysis on the convergence is provided (under reasonable conditions) and performance is shown to be on par with uncompressed full Federated Learning algorithm. An analysis on convergence rate under partial participation from the clients is also provided. Some numerical experiments are also provided and validate their theory.", "summary_of_the_review": "I believe the paper address an open problem in the setting of Federated Learning and provides compelling theorical and numerical evidence to support their claims.", "strength_and_weaknesses": "- The paper provides the first convergence analysis of compressed adaptive. The paper itself is well-organized.\n    \n - The is limited to an analysis for convergence to a neighborhood around a stationary point and not a global minimizer (or local). \n\n- In page 2: \"we present the general compressed FL framework named Fed-EF\" seems to suggest the algorithm does not use Error Feedback. Please consider modifying the phrase appropriately. Also, it is not clear what MLP stand for in page 2?\n - How is the stochastic gradient term $g_{i,i}^{(k)}$ introduced in Assumption 2 used? It unclear from Assumptions 1-3 and Algorithm 1.\n - From Figure 2, its not clear if methods with Error Feedback performs better than methods without. In most case (the figure is not big enough to be able to make a good comparison), method with EF and without EF seems to perform on par and the claim in page 7 \"test accuracy of Stoc is slightly lower than Fed-EF with hv-Sign\" seems selective to that instance of the experiment. It is not clear from the figures shown if the behaviour shown holds on average or is from one instance of the experiment.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mgScNqWzHk9", "reviewer": "Reviewer_GNNs", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper analyzes the FL setup with error feedback for non convex objective. It analyzes two variants of the FED-EF algorithm, one with SGD and the other one with AMS. Theoretical analysis is done in both setting, in particular it is shown that a linear speedup is possible, i.e., the error rate goes down with $1/\\sqrt{n}$ when $T\\geq K n$, where $K$ is the number of local steps and $n$ is the number of machines. The partial participation setting is also analyzed. Experiments are done on MNIST, CIFAR and FMNIST.", "summary_of_the_review": "Please see the Strengths/Weaknesses section. The paper misses comparison with several existing works and I also have some technical novelty concerns.", "strength_and_weaknesses": "Strength: The paper shows linear speedup (a $n$ dependent term in the statistical rate) with the number of participating clients.\n\nWeaknesses:\n\n**Missing Comparison and Prior work:** The paper does not compare with several existing related works. The problem of Error Feedback in FL is studied extensively contrary to the claim of the authors. For example, the following papers\n\n (a)  `EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback' by Richtarik et. al;\n (b) `EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback' by Richtarik et. al; \n(c) `Communication-Efficient and Byzantine-Robust Distributed Learning With Error Feedback  ' by Ghosh et.al;\n\naddress similar distributed/Federated aspects with error feedback. These papers should be discussed and the results should be compared with the ones in these papers. I believe  `EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback' is the closest one, and a thorough comparison is required.\n\n**Overclaim:** The paper seems to overclaim on certain sections. Ex: `partial-participation has never been considered'--this is not correct.  `EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback' considers partial client participation. Moreover, the paper claims ` One of the very few, if not only, FL algorithms that uses biased compression with EF is QSparse-local-SGD'--the paper   `Communication-Efficient and Byzantine-Robust Distributed Learning With Error Feedback  ' considers the biased compression setting with error feedback as well.\n\n**Novelty:** The technical analysis, setup has a lot of overlap with `Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning' by Yang et. al, including the choice of step sizes. The proofs use the same arguments as the above mentioned paper, with the additional error feedback term. Please comment on this aspect and address the technical novelty of the work.\n\n**Choice of Step Sizes:** The choice of step size is quite non-standard (they are the same as in  `Achieving Linear Speedup with Partial Worker Participation in Non-IID Federated Learning' by Yang et. al). The local step sizes are very very small (overall with $K$ local iterations, the local iterates do not seem to move/drift enough it seems. On the other hand the global step size is very very big ($\\sqrt{K n}$). Please provide some intuitive explanations, on this choice.\n\n**Typo:** I believe the first term in the right hand side of Theorem 1 has a $1/T$ missing; otherwise, the algorithm would diverge given the step size choices.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "jJRfOoKcgH", "reviewer": "Reviewer_Xm1Y", "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": "## Update\nI have read the authors' feedback and I remain confident this paper is not ready for publication for these reasons:\n1. The authors argued that their work is different from that of Fatkhulin et al. in that it uses the standard EF. I do not see, however, why standard EF would be better than EF21, I don't think that this difference justifies novelty.\n2. The authors also argued that they consider Adam stepsizes on top of that. The theory for Adam stepsizes is, however, underwhelming due to dependence on the dimension, which is caused by the fact that even for Adam itself we do not have a good analysis.\n3. The authors argue that $\\eta\\eta_l$ has to approach 0 as we target higher accuracy, which I agree with. However, once we set the value of $\\eta\\eta_l$, it is always beneficial to decrease $\\eta_l$ and increase $\\eta$ while preserving the value of $\\eta\\eta_l$. This implies that the local steps are not shown to be useful, even if the authors show that local steps are helpful under other (suboptimal) choices of $\\eta$ and $\\eta_l$.\n4. Please note that I **was not** \"raising the concern regarding the general research direction of communication compression in FL.\". In contrast, I was arguing that the compression used in the experiments might not work well with the communication primitives such as all-reduce. In other words, my comments were toward the experiments and not the research direction.\n\n#######  \nThis paper studies the combination of error feedback for compressed optimization with local method for federated learning. On top of that, the authors consider two potential ways of updating the global model based on local updates: with standard averaging and with Adam-based model update. The main contribution of the paper is to propose Algorithm 1 that combines all these features and to study its convergence with full and partial participation. The theory is supported by numerical experiments that show how different variants of Algorithm 1 based on different compressions and stepsizes perform on training neural networks.", "summary_of_the_review": "The considered setting might not be very meaningful due to the need for clients to maintain a state, while partial participation is usually employed when the number of clients is large and it is uncommon for them to keep a state. The theory has some small issues (no benefit from local steps). The experiments show only one side of the method's performance–number of communicated bits, which is not the only aspect of time efficiency–and do not illustrate if there might be an actual saving of time.  \n\nAll in all, this paper will probably have some audience, but the results are not impressive.", "strength_and_weaknesses": "## Strengths\n1. The work addresses practical issues arising in federated learning: communication efficiency and partial participation of clients, and the authors make an advance in the considered direction.\n2. The rates are good in terms of the asymptotic dependence on the number of iterations.\n3. The theory is supported by experiments.\n\n## Weaknesses\n1. The paper makes some misleading claims about the novelty of the method. In particular, the claim that \"Partial participation (PP) has never been considered for error feedback in distributed learning.\" is not correct, see (Fatkhulin et al., 2021).\n2. The authors list as one of their contributions proposing \"a unified compressed FL framework\". As far as I can see, the unified framework has just two options (SGD and AMS) and calling it \"unified\" seems to be an overstatement.\n3. As far as I can see, Theorem 1 suggests that there is no benefit from the local steps. In particular, if $\\eta\\eta_l=\\mathrm{const}$, then the bound improves as $\\eta_l\\to 0$, which means that the local steps help only due to sampling more gradients. The same can be said about Theorem 2.\n4. All experiments seem to use a single random seed and no confidence intervals are reported. \n5. The experiments only present the number of communicated bits as the efficiency metric, which ignores the computation overhead of compressing the updates as well as it does not take into account if it is actually easier to perform communication of the compressed vectors. For instance, TopK does not support synchronization primitives (over batches of clients) such as all-reduce. Moreover, it is not clear if compressing the updates make so much sense since we already ask the clients to perform a lot of local updates, which reduces the communication bottleneck.\n6. Clients are required to maintain a state. When partial participation is considered, it is reported by Kairouz et al. \"Advances and Open Problems in Federated Learning\" that one might not see the same client twice, so stateful methods make less sense with PP.\n\nIlyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, Peter Richtárik, 2021, \"EF21 with Bells & Whistles: Practical Algorithmic Extensions of Modern Error Feedback\"", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "349PV-cNRS", "reviewer": "Reviewer_SCXf", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "### Background\n\nIn the distributed optimization paradigm, it is common for the client nodes to communicate only compressed version of the computed local gradients (or parameters) with the server node to reduce communication latency. However, since compression schemes are often lossy (in expectation) and biased (ex Top K) , working with the compressed gradients might result in slower overall convergence. To alleviate this, it is common practice to use error compensation where the error by propagating compressed gradient ||g - C(g)|| is accumulated and used as feedback in subsequent iterations. Error Feedback ensures that the SGD converges at the same rate as the non-compressed counterpart. \n\n\n### Contribution:\n\nIn this paper, EF is applied and analyzed in the federated setting as follows: The server broadcasts the global model; each client (each client maintains an error vector e initialized to 0 ) does k local SGD steps; computes the error compensated gradient g = (gradient + e); computes the C(g); computes the error from compression; updates e by accumulating this additional error.  For the analysis, the authors also considered potentially heterogenous data distribution across clients ; partial client participation, adaptive gradient method at the global server.  ", "summary_of_the_review": "Overall, The contribution is quite incremental I feel. Firstly, the proposed algorithm is straightforward extension of distributed SGD with communication compression and error feedback [1,2]. Secondly, The main contribution is the analysis - which also I think is somewhat incremental overall given the tools to analyze already exist and the proof technique is also similar.  Thirdly, empirical evaluation is small scale overall. Fourthly, Assumption 1 is not clear - and seems unrealistic. \n", "strength_and_weaknesses": "### Strengths:\n1. The paper is well motivated and written. \n\n2. The main contribution of the paper is the analysis of SGD and AMSGrad in the Heterogenous Federated setting ( heterogenous client data distribution +  local SGD, partial client participation ) + ( communication compression + EF ). \n\n3. The proofs are clear and rigorous and easy to follow. \n\n\n### Weaknesses / Clarifications : \n1. Definition 1. (qC - deviate compressor) It simply says the compression operator yields a contraction mapping. This is a standard assumption used in most theoretical works in communication compression and error feedback literature: ex see [1-2].  Mentioning this connection with proper citation around Def 1 in the main paper (as opposed to making this connection in Appendix. A.1) will improve clarity, \n\n2. Algorithm 1. is a straightforward ( almost trivial ) extension of distributed SGD with EF to Federated Learning setting;  so overall I feel algorithmic novelty is quite limited. \n\n3. In Fig 18-Title missing bracket inside the expectation - i guess it should be $ E \\|\\| C(x) - x \\|\\|^2 \\leq q_c^2\\|\\|x\\|\\|^2 $ where $ x = \\frac{1}{n}\\sum_{i=1}^n(\\Delta_{t, i} +e_{t,i}) $. What do the subfigures correspond to - not clearly specified : I am *assuming* left one is for normal and right for laplacian data. \n\n4. Let $\\epsilon^2 = || C(x) - x ||^2$ Then I believe the points on Fig 18 denote $\\frac{\\epsilon^2}{||x||^2}$ - However, it is not clear from the fig or B.1 on how C was used : e.g. Top-k what is k values ? In theory the bound trivially holds for $q_c = (1 - \\frac{k}{d})$ but empirically how does it correlate on the simulated data. In other words, additional analysis wrt k vs q_c over different heterogeneity (scale) would be more insightful.\n\n5. What is the significant of the offset between Definition 1 and assumption 1 -- as seen in Fig 18. \n\n6. Definition 1 has clear motivation , I am not clear on what is the intuition / how to interpret Assumption 1.  I in fact think that Assumption 1 is unrealistic and Fig 18 shows how in non-iid scenarios it is completely off from bounds derived from Definition 1 ( i.e. from reality ) - Could you please justify this ?  \n\n7.  Empirical Evaluation: We know in non-fed EF-SGD error feedback improves the results tremendously - and can give nearly same rate of convergence as full-SGD while using only ~10 % communication. The results in the fed setting should have identical trends - as confirmed by the experiments (not surprising - right ? )\n\n8. How was the communicated bits calculated in Fig 2, 3 etc ? Let's say for Top k one would use different k values to compute log comm bits -- it is not clearly mentioned how these plots are generated. Also, are these plots using EF ? It is not clearly mentioned and hard to read the figures - please update the captions to be self contained. \n\n9. What is the exact mechanism to simulate non-iid clients ? How did you control amount of heterogeneity in experiments ? \n\n10.  Further, how does heterogeneity impact the results especially since we see in Fig 18 with high heterogeneity Assumption 1 has larger offset than Definition 1 ( i.e. from reality ) ? \n\n11. Exp are small scale : done on MNIST, FMNIST. One slightly more challenging task (at least CIFAR 10 / CIFAR 100 /mini-imageNet ) might help with validating the claims - ex.  \n\n### References:\n1. https://papers.nips.cc/paper/2018/file/b440509a0106086a67bc2ea9df0a1dab-Paper.pdf\n2. https://proceedings.mlr.press/v97/karimireddy19a/karimireddy19a.pdf", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject