Stochastic Controlled Averaging for Federated Learning with Communication Compression
Authors: Xinmeng Huang
Ping Li
Xiaoyun Li
Venue: ICLR 2024 spotlight (2024)
Keywords: federated learning
communication compression
data heterogeneity
controlled averaging
Primary area: optimization
TL;DR: We propose SCALLION and SCAFCOM that are built on a new formulation of stochastic controlled averaging and reach the SOTA performance among compressed FL algorithms.

Abstract: Communication compression has been an important topic in Federated Learning (FL) for alleviating the communication overhead. However, communication compression brings forth new challenges in FL due to the interplay of compression-incurred information distortion and inherent characteristics of FL such as partial participation and data heterogeneity. Despite the recent development, the existing approaches either cannot accommodate arbitrary data heterogeneity or partial participation, or require stringent conditions on compression. In this paper, we revisit the seminal stochastic controlled averaging method by proposing an equivalent but more efficient/simplified formulation with halved uplink communication costs, building upon which we propose two compressed FL algorithms, SCALLION and  SCAFCOM, to support unbiased and biased compression, respectively. Both the proposed methods outperform the existing compressed FL methods in terms of communication and computation complexities. Moreover,SCALLION and SCAFCOM attain fast convergence rates under arbitrary data heterogeneity without any additional assumptions on compression errors. Experiments show that \scallion and  \scafcom outperform recent compressed FL methods under the same communication budget.

Published as a conference paper at ICLR 2024
STOCHASTIC CONTROLLED AVERAGING FOR FEDER- ATED LEARNING WITH COMMUNICATION COMPRESSION
Xinmeng Huang
Ping Li
Xiaoyun Li
ABSTRACT
Communication compression has been important topic in Federated Learning (FL) for alleviating the communication overhead. However, communication com- pression brings forth new challenges in FL due to the interplay of compression- incurred information distortion and inherent characteristics of FL such as partial participation and data heterogeneity. Despite the recent development, the exist- ing approaches either cannot accommodate arbitrary data heterogeneity or par- tial participation, or require stringent conditions on compression. In this paper. we revisit the seminal stochastic controlled averaging method by proposing an equivalent but more efficient/impliiied formulation with halved uplink commu- nication costs, building upon which propose two compressed FL algorithms, SCALLION and SCAFCOM, to support unbiased and biased compression, re- spectively. Both the proposed methods outperform the existing compressed FL methods in terms communication and computation complexities. Moreover, SCALLION and SCAFCOM attain fast convergence rates under arbitrary data heterogeneity without any additional assumptions on compression errors. Exper- iments show that SCALLION and SCAFCOM outperform recent compressed FL methods under the same communication budget.
INTRODUCTION
Federated learning (FI.) is powerful paradigm for large-scale machine learning (Konečný et al., 2016; McMahan al., 2017; Yang et al., 2020) in situations where data and computational resources are dispersed among diverse clients such as phones, tablets, sensors, banks, hospitals (Kairouz et al., 2021). FL enjoys the advantage of distributed optimization the efficiency of computational sources as the local clients conduct computations simultaneously. Moreover, FL provides the first layer of protection for data privacy the local data never leaves the local device during training. Here, we first summarize the significant challenges in algorithmic development and theory of FL::
Severe data heterogeneity. Unlike in classic distributed training, the local data distribution in FL can vary significantly (i.e., non-iid clients), reflecting practical scenarios where local data held by clients is highly personalized (Zhao et al., 2018; Kairouz et al., 2021; Yuan et al., 2023; Li et al., 2022a). When multiple local training steps are taken, the local models become "bi- ased" toward minimizing the local losses instead of the global loss, hindering the convergence quality the global model (Mohri et al., 2019; Li et al., 2020c;a).
Partial client participation. Not all clients can always join the training, e.g., due to unstable connections or active selection (Li et al., 2020a). Consequently, only a fraction of clients are involved in each FL training round to interact with the central server. This slows down the convergence of the global model due to less accessible data/information per round (Charles al., 2021; Chen et al., 2022; Li & Li, 2023).
Heavy communication workload. The cost of model transmission can major challenge in FL systems with limited bandwidth (e.g., portable wireless devices), especially for models with millions or billions of parameters. Therefore, communication compression, a technique that aims reduce the volume of information transmitted, has gained growing research interests in FL (Basu et al., 2019; Reisizadeh et al., 2020; Haddadpour et al., 2021; Li & Li, 2023).
The classic FL approach, FEDAVG (Konečný et al., 2016; McMahan et al., 2017: Stich, 2019), performs multiple gradient-descent steps within each accessible client before communicating with the central server. FEDAVG is notably hampered by data heterogeneity and partial client participa- tion (Karimireddy et al., 2020b; Li et al., 2020c; Yang al., 2021) due to the "client drift" effect.
"The work is conducted at LinkedIn - Bellevue, 98004 WA, USA. Xinmeng Huang is a Ph.D. student in the Graduate Group of Applied Mathematics and Computational Science the University of Pennsylvania.

---

Published as a conference paper at ICLR 2024
Furthermore, when communication compression is employed, the adverse effect of data heterogene- ity can be amplified due to the interplay of client drift and inaccrrtee message aggregation caused by compression (Basu et al., 2019; Reisizadeh et al., 2020; Haddadpour al., 2021; Mitra et al., 2021; Malekijoo et al., 2021; Li & Li, 2023); see Figure in Appendix A for illustration. This naturally raises the question regarding the theory and utility of compressed FL approaches:
Can we design FL approaches that accommodate arbitrary data heterogeneity, local updates, and partial participation, as well as support communication compression?
None of the existing algorithms have successfully achieved this goal in non-convex FL. despite few studies in the strongly-conver and deterministic scenarios (Grudzień et al., 2023; Youn al., 2022: Condat et al., 2023; Sadiev et al., 2022). For instance, FEDPAQ (Reisizadeh et al., 2020), FEDCOM (Haddadpour et al., 2021), QSPARSE-SGD (Basu et al., 2019), LOCAL-SGI-CC (Gao et al., 2021) consider compressed FI. algorithms under iid clients. FEDCOMGATE (Haddadpour ct al., 2021), designed for unbiased compressors, does not support biased compressors, and their analysis does not consider partial client participation. FED-EF (Li & Li, 2023) focuses biased compression with error feedback (EF) (Seide et al., 2014; Karimireddy et al., 2019) and partial client participation. However, the convergence analysis requires the assumption of bounded gradient dis- similarity on the data heterogeneity and shows an extra slow-down factor under partial participation. suggesting a theoretical limitation of EF in FL. Moreover, both Haddadpour et al. (2021) and Li & Li (2023) require assumptions on compression errors (see Appendix C.4 for more details).
1.1 MAIN RESULTS AND CONTRIBUTIONS
We develop SCALLION and SCAFCOM, two compressed FL algorithms for unbiased and bi- ased compressors, respectively, that are practical to implement, robust to data heterogeneity and partial participation, and exhibit superior theoretical convergence. Table presents the comparison of convergence rates of our results with prior works. Specifically, the main contributions are:
We revisit SCAFFOLD (Karimireddy et al., 2020b) and propose a simplified formulation. The new implementation reduces the uplink communication cost by half, requiring each client to transmit only one increment variable (of the same size as the model), instead of two variables.
Builing on the new formulation, we propose SCALLION method employs unbiased com- pressors for the communication of increment variables. We establish its convergence result for non-convex objectives. SCALLION obtains the state-of-the -h-tt---rtttttttte communication and computa- tion complexities for FL under unbiased compressors and supports partial client participation.
We further develop SCAFCOM which enables biased compressors for broader applications. Local momentum is applied to guarantee fast convergence and improve empirical performance. The communication and computation complexities of SCAFCOM improve prior results by significant margins, particularly when compression is aggressive.
We conduct experiments to illustrate the effectiveness SCALLION and SCAFCOM. Our empirical results show that the proposed methods achieve comparable performance to full- precision FL methods with substantially reduced communication costs, and outperform recent compressed FL methods under the same communication budget.
Notably, our analysis only requires the smoothness of objectives and bounded variance of stochastic gradients, without additional assumptions data heterngeneity or compression errors, unlike prior works (Appendix C.4). To our best knowledge. SCALLION and SCAFCOM are the first stochas- tic FL methods that exhibit robustness arbitrary data heterogeneity, partial participation, local up- dates, and accommodate communication compression relying solely on standard compressibilities
2 RELATED WORK
Communication compression & error feedback. Two popular approaches are commonly em- ployed to compress communication in distributed systems: quantization and sparsification, which are often modeled
unbiased or biased operators. Notable quantization examples include Sign (Seide et al., 2014; Bernstein et al., 2018), low-bit fixed rounding (Dettmers, 2016), random dithering (Alistarh et al., 2017), TemGrad (Wen et al., 2017), and natural compression (Horvóth et al., 2022). Sparsification compressors work by transmitting a small subset of entries from the input vector (Wangni et al., 2018; Stich et al., 2018). In distributed training, unbiased compressors
2

---

Published as a conference paper at ICLR 2024
Table I: The comparison of compressed FL algorithms under full participation. The upper half the table is for unbiased compression, and the bottom half is for biased compression. N is the number of clients; e is a target for the stationarity B[I[V [*)]l S and g compression-refated parameters (see Definitions & 2). #A. Comm. is the total number of communication rounds when a -> asymptoticalyy while #A. Comp. denotes the total number of gradient evaluations required per client when e -> asymptotically (see Section 4.3 for details); P.P. denotes allowing partial client participation; D.H. denotes allowing arbitrary data heterogeneity; S.C. denotes only requiring standard compresstbilittes (i.e. Definitions 1 & 2). Constants like objectives" smoothness L and stochastic gradients' variance o² omitted for clarity.
Algorithm
#A. Comm.
#A. Comp.
P.P.
D.H.
S.C.
FEDPAQ (Reisizadeh et al., 2020)
1ts Ne
X
V
FEDCOM (Haddadpour et al., 2021)
1+w/Ng
1
X
X
V
N
FEDCOMGATE (Haddadpour et al., 2021)
Tre
X
J
X
SCALLION (Theorem 1)
1 1f
V
J
N
SCAFCOM (Corollary 2)
1+w
V
V
6
N
QSPARSE-SGD (Basu et al., 2019)
X
x
V
NZ
LOCAL-SGD-C (Gao et al., 2021)
X
x
[1-g]e
NE
FED-EF (Li & Li, 2023)
x
x
[-g]
N(1 PM
SCAFCOM (Theorem 2)
(1-9)6
N
The communication complexity requires homogeneous (iid) clients, though slightly better than ours. The results are obtained by transforming unbiased compressors into biased compressors through scaling.
usually can be applied in place of the full precision gradients to get reasonable convergence and em- pirical performance. However, directly using biased compressors may slow down convergence or lead to divergence (Beznosikov et al., 2020; Li & Li, 2023). To mitigate this, the technique of error feedback (EF) is first proposed in Seide et al. (2014), which has proven effective in addressing biased compressors (Stich et al., 2018; Karimireddy al., 2019) and has inspired many subsequent works (Wu et al., 2018; Alistarh et al., 2018; Li et al., 2022b). Moreover, a variant scheme of EF called EF21 is introduced recently (Richtárik al., 2021). EF21 compresses increments of deter- ministic gradients and offers superior theoretical guarantees compared to vanilla error feedback.
Heterogeneity and compression in FL. Federated learning has gained great prominence since the introduction of FEDAVG, proposed by McMahan al. (2017) to improve the communication eff- ciency of classic distributed training. Subsequent studies reveal its susceptibility to data heterogene- ity (i.e., non-iid clients) due to the "client-drift" effect, particularly when not all clients participate in training (Stich, 2019; Yu et al., 2019b; Wang & Joshi, 2021; Lin et al., 2020; Wang et al., 2020b; Li et al., 2020c; Yang et al., 2021), Substantial efforts have been made to address client heterogeneity in FL (Liang al., 2019; Li et al., 2020b;a; Wang al., 2020a; Zhang et al., 2021; Haddadpour al., 2021; Guo et al., 2023; Karimi et al., 2023; Cheng et al., 2024) and develop FL protocols involv- ing variance reduction techniques or adaptive optimizers (Karinireddy et al., 2020b; Reddi al., 2021; Chen et al., 2020). Notably, SCAFFOLD introduced by Karimireddy et al. (2020b) leverages control variables to mitigate the impact of data heterogeneity and partial client participation.
To further reduce communication costs, communication compression has been integrated into FL, leading to methods such as FEDPAQ (Reisizadeh et al., 2020), FEDCOMGATE (Haddadpour et al., 2021), FED-EF (Li & Li, 2023). Due to information distortion incurred by compression, those com- pressed FL methods either lack the robustness to data heterogeneity and partial participation, or rely on stringent conditions of compressors, surpassing standard unbiased/comtractive compressibility.
Federated learning with momentum. The momentum mechanism in optimization traces back to Nesterov's ' acceleration (Yurri, 2004) and the heavy-ball method (Polyak, 1964), which have been extended to stochastic optimization (Yan et al., 2018; Yu et al., 2019a; Liu et al., 2020) and other domains (Yuan et al., 2021; He et al., 2023b;a; Chen et al., 2023; Fatkhullin et al., 2023). In the context of Fl., momentum has been widely incorporated and shown to enhance performance (Wang al., 2020b; Karimireddy al., 2020a; Khanduri al., 2021; Das al., 2022; Cheng al., 2024).
PROBLEM SETUP
Formally, in federated learning, we aim to minimize the following objective:
1 N N 1=1
min ZER
where f((x) := Eg,DD, [F(x;.)). f(x) = Σ f(())
3

---

Published as a conference paper at ICLR 2024
where &, represents local data sample of client i following data distribution D,, F(x; represents the loss function evaluated at model x and sample &,. and fi()) is the local objective w.r.t D, In practice, the data distributions Dj across clients may vary significantly (referred to data hetero- geneity), resulting in the inequality f((r) * [z) for different clients i and j. Consequently, a globally stationary model x² with Vf(=*) O may not be stationary point of the local objectives. In contrast, if the clients are homogeneous (i.e. following a common data distribution D), we would have fi(x) =
fN (x) and a globally stationary model would also be stationary for each client. Throughout the paper, we use || -ll to denote the &g vector norm and use [N] to denote {1..... .......T NN for N N4. The notation S denotes inequalities that hold up to numeric numbers; 2 and x are utilized similarly. We state the following standard assumptions required for our convergence analysis.
Assumption 1. Each local objective Js has L-Lipschitz gradient, i.e., for any x, y IRd and 1 S i < N, it holds that [[V[())) - f((ii)l S L||= - yll-
Assumption 2. There exists 2 0 such that for any x E IRd and 1 si N. R., (():; =
V f(()) and Eg, (x; - V { o², where &, ~ DD are iid local samples at client i.
4 SCALLION: UNBIASED COMPRESSED COMMUNICATION
In this section, we first revisit the seminal SCAFFOLD algorithm (Karimireddy et al., 2020b), which requires communicating two variables (of the same size as the model) from client server per communication round. We present a new formulation with only single variable for uplink com- munication for each client. We then propose SCALLION, which employs unbiased compressors to reduce the communication workload of SCAFFOLD and provide the convergence analysis.
4.1 BACKGROUND OF SCAFFOLD
The SCAFFOLD algorithm (Karimireddy et al., 2020b) maintains local control variables {c]) on clients and global control variable cf the server. Let S S [N] (with |S*] = S) be the set of accessible (active) clients to interact with the server in the t-th round. In each training round, SCAFFOLD conducts K local updates within each active client i E S by
(I) where i is the local model in client i initialized with the server model y; : x² and m is the local learning rate. Here, the subscript represents the client index, while the superscripts and denote the outer and inner loop indexes corresponding to communication rounds and local-update steps, respectively. Upon the end of local training steps. clients update local control variables as;
y 1 = v. no FVF(), L,k, : ) of + c'), for k O,..,,
cf c¹
if St. otherwise.
(2)
c
The increments of local model y/ i St, then sent to the central server and aggregated update the global model parameters:
K x' and control variable oi - cf. of each participating client
ng
Σ
(vl A.K
-'),,
++ =
Σ C (ct1-cc))
S
N
$ES
FES!
where Mg is the global learning rate. The detailed description of SCAFFOLD can be found in Appendix B. Notably, the control variables of SCAFFOLD track local gradients such that of so Vf((z") and ct se vf(x'), thereby mimicking the ideal update through VF l.k, <t. - of + ct so fs(x') given VF(y L.k.
Vielsl"")) and y/ I.A x'. Consequently, the local updates nearly synchronized in the presence of data heterogeneity without w suffering from client drift.
While the introduction of control variables enables SCAFFOLD to converge robustly with arbi- trarily heterogeneous clients and partial client participation, the original implementation of SCAF- FOLD described above requires clients to communicate both updates of local models y, f.K xf and control variables c &e (also see Karimireddy et al. (2020b, Alg. 1, line 13)). This results doubled client-to siient-to-server communication cost and more obstacles to employing communication compression, compared to its counterparts without control variables such FEDAVG.
4.2 DEVELOPMENT OF SCALLION
We present an equivalent implementation of SCAFFOLD which only requires a single variable for uplink communication and is readily employable for communication compression. Expanding the
4

---

Published as a conference paper at ICLR 2024
local updates vi K.K
x² and control variables e+ cf by exploiting (1) and (2), we have
++
x²
Vi
t.
c¹
K K-1
VF
R ;
(3)
1p
K
K
k=
K
t.K 1/
VF(y
(4)
In (3) and (4), the updates local models and control variables share a common component, the increment variables A. Since the global control variable is inherently maintained by the server, updates c ej and thus v/ x' can be recovered by the server upon receiving Ai Hence, the global model and control variable can be equivalently updated as
x++1 x²
7g K
Esi+ and = N
1
ΣAJ. A.
(5)
VES*
iES
We only need to communicate A,. In the above formulation, by communicating the increment variables A and applying (5) at the server accordingly, SCAFFOLD can be implemented equiva- lently with a halved uplink communication cost, compared to the original one (Karimireddy al., 2020b). Notably, our new implementation only modifies the communication procedure, and main- tain the same local updates as in Karimireddy et al. (2020b); see Algorithm 4 in Appendix B.
Benefits of compressing A, Importantly, the new implementation provides simpler backbone for communication compression as only the transmission of A is be compressed. Moreover, unlike compressing local gradients as adopted in prior literature, compressing A asymptotically eliminates compression errors even the presence of data heterogeneity. Consider the case of deterministic gradients for simplicity. Based on the update rules of SCAFFOLD, if hypothetically the training approached steady stage where x' is close to a stationary point x², we expect to have of ~ fx(")) and cf = Σi of z Vf(x") = 0. Thus, the directions in local updates satisfy V ff ct + x so that x No x" ae zf 2 ... = y The definition of A in (3) implies A Ek- (v of = O. Namely, the increment variable A gradually vanishes the algorithm iterates. Therefore, taking an w-unbiased compressor as an example (see Definition 1), compressing A results in vanishing compression error (AI) A w|| 0, regardless of data heterogeneity. In contrast, if one considers compressing local gradients directly, constantly large compression error is introduced in each communication round (V
ff(a"))] < fi + w||V (2*)|l * 0. The constant | f. (x*) )|l can be extremely large under severe data heterogeneity, resulting in algorithmic susceptibility to data heterogeneity.
Algorithm SCALLION: SCAFFOLD with single compressed uplink communication
Input: initial model _ and control variables [ v= cº: local learning rate mi global learning rate 7g: local steps K; number of sampled clients S; scaling factor a E [0, 1]
2: for 0....... ,T do
3: Uniformly sample clients S S [N] with |S =
4: for client E S¹ in parallel do
5: Receive x' and c²: initialize y x²
6: for t = O,... K 1 do
7:
Compute mini-batch gradient 9f = VF(,, ( t.k
8: Locally update y. A = yi
n ng k
of + ct)
9:
end for
Compute 5% -v- ct) nk
10:
11:
Compress and send o = (,(5)) to the server
D a 1 and C. = recovers SCAFFOLD
12:
Update e/+1 of + 34 (for i & St, ". = c!)
13:
end for
14:
Update 1+11 I² S S
JalKK K
Eiesi (0) + cc
15:
Update d1+1 c¹ + N Eies:
16:
end for
5

---

Published as a conference paper at ICLR 2024
Following the above argument regarding compression, now propose to transmit the compressed proxy C,(oA)) of the increment variable A. leading to the SCALLION method as presented in Algorithm 1. Here C, is the compressor utilized by client while the scaling factor E [0, 1] is introduced to stabilize the updates of control variables {c]]== and can be viewed as the learning rate of control variables. When a = and { are the identity mappings (i.e., no compression), SCALLION will reduce to SCAFFOLD with new implementation, ie., Algorithm 4. The algorithmic comparison of SCALLION with other existing approaches is in Appendix C.2.
4.3 CONVERGENCE OF SCALLION
To study the convergence of SCALLION under communication compression, we first consider compressors satisfying the following standard unbiased compressibility.
Definition (w-UNBIASED COMPRESSOR). There exists w 2 such that for any input x E R and each client-associated compressor C; TRd ~ RRd, [[],(=))] and B[IIC, -x)= S w||=||?
where the expectation is taken over the randonness of the compressor C,.
Examples that satisfy Definition include random sparsification and dithering; see Appendix C.1 for details. When communication compression with w-unbiased compressors is employed, the con- vergence of the proposed SCALLION (Algorithm 1) justified as follows.
Theorem (SCALLION WITH UNBIASED COMPRESSION). Under Assumptions 1, 2, and mulu- ally independent w-unbiased compressors, we initialize cf fx(xx)) and c f(=)), and set T, Tl. and a as in (29), then SCALLION converges as
W)
(1 (
1/3 (
(1+W)NIA ST
EEVI
S
(6)
SKT
where A &
min, f(x). A detailed version and the proof are in Appendix E.
Asymptotic complexities of SCALLION. When using full- gradients (i.e., a - 0), all terms involving in (6) vanish. Consequently, the bottleneck of FL algorithms boils down to the rounds of client-to-server communication. On the other hand, when gradients are very noisy (ie. a is extremely large), the a deeedddeee term dominates others in which a are with lower orders. In this case, the performance is mainly hampered by the number of gradient evaluations. Fol- lowing (Fatkhullin et al., 2023), we refer to the total number of communication rounds in the and gradient evaluations in the regime regime < é as the asymptotic communication complexity and computation complexity'. [+
0 required by per client attain
Theorem shows N(1+=) asymptotic communication complexity and 32T asymptotic computation complexity of SCALLION. Here, we focus on presenting the impact of stationarity e, compression w, client participation S and N, and local steps K in asymptotic complexities.
Se
Comparison with prior compressed FL methods. Table provides a summary of non-convex FL. methods employing unbiased compressors under full client participation. We observe that SCAL- LION matches the state-of-the-art asymptotic communication and computation complexities un- der non-iid clients. In particular, while having the same asymptotic complexities as FEDCOM- GATE (Haddadpour et al., 2021), SCALLION does not depend on large uniform bound of com- pression errors (see Appendix C.4) in convergence and thus has a superior convergence rate.
To sum up, based on the above discussion, we demonstrate that SCALLION theoretically improves existing FL methods with unbiased compression.
SCAFCOM: BIASED COMPRESSION WITH MOMENTUM
While SCALLION achieves superior convergence speed under unbiased compression, its analysis cannot be adapted to biased compressors (also known as contractive compressors) to attain fast convergence rates. In this section, we propose an algorithm called SCAFCOM complement of SCALLION to accommodate biased communication compression in FL..
'The complexities justify convergence rates in terms of the a -l--epeedent and 1/T- terms. For instance, for the rate in (6), the asymptotic communication complexity T x N(1+w) is derived from Se
NLA while the asymptotic computation complexity SKT 1+s follows from v LLo?

---

Published as a conference paper at ICLR 2024
Algorithm 2 SCAFCOM: SCAFFOLD with momentum-enhanced compression
1: Input: initial model x² and control variables {c] c:; local learning rate mi global learning
rate 77: local steps K; number of sampled clients S: momentum [0,
2: for t===0,,, 0, ... T - do
3: Uniformly sample clients S S [N] with |S S
4: for client E St in parallel do
5: Receive x' and c²; initialize 4.0 = x²
6: for k = O,...,
1 do
7:
Compute a mini-batch gradient 9; :yf Locally update v, j.k+1 t.k mi t.k
8:
c tc)
9:
end for
10:
Update uft = (1 B)ot + B
+ c - -c) (for & St, 1.41 = =o s' ['' mk
11:
Compute of = oit1
12:
Compress and send 0 ( to the server
B and C, recovers SCAFFOLD
13:
Update cf ci + 5 (for & St, oft1 = cf)
14:
end for
Update r.1+1 x² BancK Eigsi +c)
15:
16:
Update cd+1 + N Eies: 8
end for
5.1 DEVELOPMENT OF SCAFCOM
In the literature, biased compressors are commonly modeled by contractive compressibility.
Definition 2 CONTRACIIVVVV COMPRESSOR). There exists g [0, 1) such that for any input E Rdd and each client-associated compressor C, Rdd + R&, E[[[C,( - x ==(²]] s x² [>]2, where the expectation is taken over the randomness of the compressor C..
Notably, compared to unbiased compressors satisfying Definition 1, contractive compressors, though potentially having smaller squared compression errors, no longer enjoy the unbiasedness; see com- mon contractive compressors in Appendix C. Compared to their counterparts with unbiased com- pressors, approaches employing biased compressors typically (i) require stringent assumptions, e,g. bounded gradients (Seide et al., 2014; Koloskova et al., 2019; Basu et al., 2019) bounded gradi- ent dissimilarity (Huang et al., 2022; Li & Li, 2023), (ii) rely on impractical algorithmic structure, e.g., large amount of gradient computation (Fatkhullin et al., 2021), (iii) have weak convergence guarantees, e.g., worse dependence on compression parameter q (Zhao et al., 2022).
Recently, Fatkhullin et al. (2023) shows that tactfully incorporating momentum into communica- tion compression can effectively mitigate the influence of biased compression and thus presents the linear speedup in terms of the number of clients. Inspired by their findings, we introduce extra momentum variable of on each client to overcome the adverse effect of biased compression. This leads to the FCOM method, presented in Algorithm 2. When client participates in the I-th round, an additional momentum variable of is updated as
x
K.K V,
B
(1 B) + where {v.""}
+ -c- (1-
3)
V
Fu L.k
π
K
R==
} are the intermediate local models and (3 is the momentum factor. We then set of+1 -K- VF ( </*²)
) ca -cc to (compressively) communicated, as opposed K-1 VF(u + c)) in SCALLION. Compared to the gradient - K F L.kk : yielded by single local loop.
of = (1-33of +
+ 3K
to K Ek- VF(u
in SCAFFOLD and a(K- Ek=
momentum variable 4++1 has smaller variance due to its accumulation nature, thereby refining the convergence behavior under biased compression. Finally, note that similar to SCALLION, SCAFCOM only transmits one compressed variable in the uplink communication, and recovers SCAFFOLD when 3 = 1 and [C.)." are the identity mapping (f.e., compression).
Connection with SCALLION. Notably, the difference between SCAFCOM and SCALLION lies in the utilization of momentum; the colored highlights in Algorithm and Algorithm 2.

---

Published as a conference paper at ICLR 2024
Specifically, if we replace line 10 of SCAFCOM with the following formula:
x² vi TIKK
K- Σ FF :6 :
+ -d--d) =
== = a ta
a
then SCAFCOM recovers SCALLION (Algorithm 1) with a. Note that in this case, the memorization of of is no longer needed to be retained, which is consistent with the design of SCALLION. We also remark that the roles of the scaling factor a and momentum / vary in SCAL- LION and SCAFCOM. In SCALLION, stabilizes the updates of control variables {c) (iii while SCAFCOM sets 3 to mainly address the biasedness issue of contractive compressors.
5.2 CONVERGENCE OF SCAFCOM
The convergence of SCAFCOM under qi-cottractive compression is established follows.
Theorem 2 (SCAFCOM WITH BIASED COMPRESSION). Under Assumption 1, 2, and q²- contractive compressors {C.) if we initialize of = of ff((=") and e vf(x²), and
set mh, Mg and B as in (55), then SCAFCOM converges as
ΣEN T EIN (1)))
LAo2
1/3 2
NLA
SKT
(1-9)5PKT)
(1
STT
(1-
Furthermore, it is known that one convert any w-unbiased compressor C, into q -ooottraceive compressors with g2 = s
1+w through scaling 1+- C, : x ++ C(() (Safaryan et al., 2022, Lemma
1). Thus, SCAFCOM can also employ unbiased compressors through this scaling::
Corollary (SCAFCOM WITH UNBIASED COMPRESSION), When employing unbiased compres-
sors (after scaling) in communication, the convergence of SCAFCOM is upper bounded by
L.Q22
(1
(1 (1++))2333900
+ )
1/3
-3 (11+
1/4
(1 W1+W)NTA
+
(7)
SKT
ST
Remark 1. Corollary I is obtained by directly plugging in the relation q² w into Theorem without exploiting the unbiasedness of compressors. However, it is feasible to refine the 1/12/3 and 1/T8/4 terms in (7) by taking advantage of unbiasedness. We omit the proof here for conciseness.
Asymptotic complexities of SCAFCOM. Following the result of Theorem 2, SCAFCOM with biased compression has an asymptotic communication complexity
N S(1-g)c and an asymptotic computation complexity of Ser to attain [ S e. On the other hand, when adopting unbiased compressors with scaling, Corollary 1 reveals that SCAFCOM has an asymptotic com- munication complexity of N(1+w) and an asymptotic computation complexity of 527
Comparison with prior compressed FL methods. In Table 1, we compare SCAFCOM with exist- ing FL algorithms with biased compression under full client participation. We see that SCAFCOM outperforms prior results with biased compression in the asymptotic communication complexity by least factor 1/(1 q). Moreover, inferior to SCAFCOM, the existing FL methods with bi- ased compression cannot tolerate unbounded data heterogeneity or even require homogeneous data. (Basu al., 2019) and LOCAL-SGD-C (Gao et al., 2021) only con- verge under full client participation. Notably, when employing unbiased compression, SCAFCOM enhances the asymptotic computation complexity by a factor of + w compared to SCALLION, surpassing all prior FL methods with unbiased compression. Furthermore, under partial client par- ticipation, rate is better than that of FED-EF (Li & Li, 2023) by factor of /N/S, overcoming the drawback of the standard error feedback under partial participation in federated learning.
Moreover, QSPARSE-SC
Based on discussions in Section 5, demonstrate that SCAFCOM, unified approach, outper- forms existing compressed FL methods under both unbiased and biased compression.
6 EXPERIMENTS
We present experiments to demonstrate the efficacy of our proposed methods. Since the saving in communication costs of various compressors has been well justified in the literature (see, e.g., Had- dadpour et al. (2021); Li & Li (2023)), we focus on (i) validating that SCALLION and SCAF- COM can empirically match SCAFFOLD (full-precision) with substantially reduced communica- tion costs, and (ii) showing that SCALLION and SCAFCOM outperform prior methods with the same communication budget. We defer more experimental details and results to Appendix G.
8

---

Published as a conference paper at ICLR 2024
100
90
BOAPROO
Fad dGD LA
DGAFFCLOLE
Test Teot. Accurayy (%)
1.5
8
Train Losa
Accuracy
Train Loss
1.5
Feeh EP 30-4001
8
SCAPRO PAR
OCAFRO DAR
SCAFO 2e kç00
0.5
MNIST
85
MNIST
FMNIST
FMNIST
Fee oi FFiyeddd
Fec o7 (00001
10
90
40
10
30
40
50
10
20
40
50
10
30
40
Commurication Rounds
Communication Rounds
Communication Rounds
Communication Rounds
Figure I: Train loss and test accuracy of SCAFCOM (Algorithm 2) and FED-EF (Li & Li, 2023) with biased
TOP-r compressors on MNIST (left half) and FMNIST (right half).
100
00
BCARTOLDILI
SCATPOLO
Feeidan
Test Accur Bay 1%)
Ceo SAR
Trein Loss
Train Less
FAOCOMAATE TE AI
Tes NO S00
S0ALLION-4 DE
SONLUONN4 be
8
8
MNIST
SCAL LO
5044
FMNIST
FMINIST
PescCrasITT DO
SCALL LON-R
0.5
10
20
30
40
50
10
20
30
40
10
20
30
40
10
20
30
40
50
Communication Rounds
Communication Rounds
communicatio Rounds
Communication Rounds
Figure 2: Train loss and test accuracy of SCALLION (Algorithm 1) and FEDCOMGATE (Haddadpour et al., 2021) with unbiased random dithering on MNIST (left half) and FMNIST (right half).
We compared the proposed algorithms with baselines including FED-EF (Li & Li, 2023), FED- COMGATE (Haddadpour al., 2021), FED-SGD (also known as FEDAVG (Yang et al., 2021 )), and SCAFFOLD (Karimireddy et al., 2020b) on two standard FL datasets: MNIST (LeCun, 1998), FMNIST (Xiao et al., 2017)). Note that FED-SGD and SCAFFOLD employ full-precision (i.e., uncompressed) communication and we implement SCAFFOLD with our new formulation (Algo- rithm 4) for a fair comparison. We simulate biased compression with ToP-r operators (see Example 3). Specifically, we adopt TOP-0.01 and ToP-0.05, where only the largest 1% and 5% entries in absolute values are transmitted in communication. For unbiased compression, we utilize random dithering (see Example 2), with 2 bits and 4 bits per entry, respectively.
Since all the compressed FL methods in our experiments transmit one variable in the uplink commu- nication, their communication costs essentially the same when the same compressor is applied. Therefore, for clarity of comparisons, we will plot the metrics versus the number of training rounds.
SCAFCOM with biased compression. In Figure 1, we present the train loss and test accuracy of our proposed SCAFCOM (3- = 0.2) and FED-EF (Li & Li, 2023), both using biased TOP-r compressors. We observe on both datasets: (i) under the same degree of compression (i.e., the value of r here). SCAFCOM outperforms FED-EF in terms of both training loss and test accuracy. thanks to controlled variables and the local momentum in SCAFCOM; (ii) SCAFCOM with TOP- 0.01 can achieve very close test accuracy as SCAFFOLD (full- frel--prcissoo), and SCAFCOM with TOP-0.05 match those of SCAFFOLD, leading to the same performance while saving 20 100x uplink communication costs; (iii) the performance of SCAFCOM and FED-EF approaches that of the full- full-precision counterparts (i.e. SCAFFOLD and FED-SGD) as compression assuages.
SCALLION with unbiased compression. In Figure 2. we plot the same set of experimental results and compare SCALLION (a- = 0.1) with FedCOMGATE (Haddadpour et al., 2021), both applying unbiased random dithering (Alistarh et al., 2017) with 2 and 4 bits per entry. Similarly, we see that SCALLION outperforms FedCOMGATE under the same compressors. The SCALLION curves of both 2-bit and 4-bit compression basically overlap those of SCAFFOLD, and 4-bit compression slightly performs better than bt compression in later training rounds. Since random dithering also introduces sparsity in compressed output, the 4-bit compressor already provides around 100x communication compression, and the 2-bit compressor saves even more communication costs.
7 CONCLUSION
This paper proposes two compressed federated learning (FL) algorithms, SCALLION and SCAF- COM, to support unbiased and biased compression in FL. The proposed methods are built upon our new implementation of stochastic controlled averaging. along with local momentum, and commu- nication compression. Theoretically, under minimal assumptions, SCALLION and SCAFCOM match improve the state-of-the-art convergence of compressed FL methods. Moreover, SCAL- LION and SCAFCOM are first stochastic FL methods, to the best of our knowledge, that exhibit robustness to arbitrary data heterogeneity, partial participation, local updates, and also accommodate communication compression relying solely on standard compressibilities. Empirically, experiments show that SCALLION and SCAFCOM outperform prior compressed FL methods and perform comparably to full-precision FL approaches at substantially reduced communication cost.

---

Published as a conference paper at ICLR 2024
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: communication-effcceent SGD via gradient quantization and encoding. In Advances in Neural Information Processing Systems (NIPS), pp. 1709-1720, Long Beach, CA, 2017.
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), pp. 5973-5983, Montréal, Canada, 2018.
Debraj Basu, Deepesh Data, Can Karakus, and Suhas N. Diggavi. Qsparse-local-SGie Distributed SGD with quantization, sparsification and local computations. In Advances Neural Information Processing Systems (NeurIPS), pp. 16668-16679, Vancouver, Canada, 2019.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Azizzadenesheli, and Animashree Anandkumar. SIGNSGD: compressed optimisation for non-convex problems. In Proceedings of the 35th Inter- national Conference on Machine Learning (ICML), pp. 559-568, Stockholmsmässan. Stockholm, Sweden, 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Safaryan. On biased compres- sion for distributed learning. arXiv preprint arXiv:2002.12410, 2020.
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 (NeurIPS), pp. 20461-20475, virtual, 2021.
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning- Trans. Mach. Learn. Res., 2022.
Xiangyi Chen, Xiaoyun Li, and Ping Li. Toward communication efficient adaptive gradient method. In Proceedings of the ACM-IMS Foundations of Data Science Conference (FODS), pp. 119-128, Virtual Event, USA, 2020.
Xuxing Chen, Tesi Xiao, and Krishnakumar Balasubramanian. Optimal algorithms for stochas- tic bilevel optimization under relaxed smoothness conditions. arXiv preprint arXiv:2306. TrXV:22306.12067, 2023.
Ziheng Cheng. Xinmeng Huang, Pengfei Wu, and Kun Yuan. Momentum benefits non-iid federated learning simply and provably. In The Twelfth International Conference Learning Representa- tions, 2024.
Laurent Condat, Grigory Malinovsky, and Peter Richtárik. Tamuna: Accelerated federated learning with local training and partial participation. arXiv preprint arXiv:2302.09832. 2023.
Rudrajit Das, Anish Acharya, Abolfazl Hashemi. Sujay Sanghavi, Inderjit Dhillon, and Ufuk Topcu. Faster non-convex federated learning via global and local momentum. In Proceedings of the Eindhoven, Netherlands, 2022.
Conference on Uncertainty in Artificial Intelligence (UAI), pp. 496-506,
Tim Dettmers. 8-bit approximations for parallelism deep learning. In Proceedings of the 4th International Conference Learning Representations (ICLR), San Juan, Puerto Rico, 2016.
Ilyas Fatkhullin, Igor Sokolov, Eduard Gorbunov, Zhize Li, and Peter Richtárik. EF21 with bells & whistles: Practical algorithmic extensions of modern error feedback. arXiv preprint 1r.02:211..03294, 2021.
llyas Fatkhullin, Alexander Tyurin, and Peter Richtárik. Momentum provably improves error feed- back! arXiv preprint arXiv:2305. 2023.
Hongchang Gao, An Xu, and Heng Huang. On the convergence of communication-efficnn local SGD for federated learning. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI), pp. 7510-7518, Virtual Event, 2021.
10

---

Published as a conference paper at ICLR 2024
Michat Grudzieñ, Grigory Malinovsky, and Peter Richtárik. Improving accelerated federated learn- ing with compression and importance sampling. arXiv preprint (rXiv:2306.032-00 2023.
Luyao Guo, Sulaiman A Alghunaim, Kun Yuan, Laurent Condat, and Jinde Cao. Randcom: Ran- dom communication skipping method for decentralized stochastic optimization. arXiv preprint arXiv:2310.07983, 2023.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Feder- ated learning with compression: Unified analysis and sharp guarantees. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 2350-2358, Virtual Event, 2021.
Yutong He, Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and accel- erated algorithms in distributed stochastic optimization with communication compression. arXiv preprint M.Xiv:2305.07612 2023a.
Yutong He, Xinmeng Huang, and Kun Yuan. Unbiased compression saves communication in dis- tributed optimization: When and how much? arXiv preprint arXiv:2305.1629) 2023b.
Samuel Horvóth, Chen- Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. Natural compression for distributed deep learning. In Mathematical and Scientific Machine Learning, pp. 121,141,70 2022.
Xinmeng Huang, Yiming Chen, Wotao Yin, and Kun Yuan. Lower bounds and nearly optimal algorithms in distributed learning with communication compression. In Advances Neural In- formation Processing Systems (NeurIPS), New Orleans, LA, 2022.
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), pp. 2530-2200000 2541, Montréal, Canada, 2018.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Olieiira, Hubert Eichner, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Gar- rett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, 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, Prateck 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, Praneeth 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-2) 2021.
Belhal Karimi, Ping Li, and Xiaoyun Li. Fed-LAMB: Layer-wise and dimension wise locally adap- tive federated learning. In Proceedings of the Thirty-iitth Conference Uncertainty in Artificial Intelligence (UAI), Pittsburg, Kansus, 2023.
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), pp. 3252-3261, Long Beach, CA, 2019.
Sai Praneeth Karimireddy, Martin Jaggi, Satyen Kale, Mchryar Mohri, Sashank J Reddi, Sebas- tian U Stich, and Ananda Theertha Suresh. Mime: Mimicking centralized stochastic algorithms in federated learning. arXiv preprint arXiv:2008. 03606, 2020a.
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 (ICMI), pp. 5132-5143, Virtual Event, 2020b.
Prashant Khanduri, Pranay Sharma, Haibo Yang, Mingyi Hong, Jia Liu, Ketan Rajawat, and Pramod K. Varshney. STEM: A stochastic two-sided momentum algorithm achieving near- optimal sample and communication complexities for federated learning. In Advances in Neural Information Processing Systems (NeurIPS), pp. 6050-6061, virtual, 2021.
11

---

Published as a conference paper at ICLR 2024
Anastasia Koloskova, Sebastian U. Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3478-34883 3487, Long Beach, CA, 2019.
Jakub Konečný, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprint arXiv:1610.05499 2016.
Yann LeCun. The mnist database of handwritten digits. http://yann. lecun. com/exdb/mmist/, 1998.
Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. Federated learning on non-iid data si- los: An experimental study. In Proceedings of the 38th IEEE International Conference on Data Engineering (ICDE), pp. 965-978, Kuala Lumpur, Malaysia, 2022a.
Tian Li. Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Process. Mag. 37(3):50 60, 2020a.
Tian Li, Anit Kumar Sahu, Manzil Zaheer, Maziar Sanjabi, Ameet Talwalkar, and Virginia Smith. Federated optimization in heterogeneous networks. In Proceedings of Machine Learning and Systems (MLSys), Austin, TX, 2020b.
Xiang Li, Kaixuan Huang, Wenhao Yang. Shusen Wang, and Zhihua Zhang. On the convergence of FedAvg on non-IlI data. In Proceedings of the 8th International Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020c.
Xiaoyun Li and Ping Li. Analysis of error feedback in federated non-convex optimization with biased compression: Fast convergence and partial participation. In Proceedings of the 40th Inter- national Conference on Machine Learning (ICML), pp. 19638-19688, Honolulu, HI, 2023.
Xiaoyun Li, Belhal Karimi, and Ping Li. On distributed adaptive optimization with gradient com- pression. In Proceedings of the Tenth International Conference on Learning Representations (ICLR), Virtual Event, 2022b.
Zhize Li, Hongyan Bao, Xiangliang Zhang. and Peter Richtárik. PAGE: A simple and optimal prob- abilistic gradient estimator for nonconvex optimization. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 6286-6295, Virtual Event, 2021.
Xianfeng Liang, Shuheng Shen, Jingchang Liu, Zhen Pan, Enhong Chen, and Yifei Cheng. Variance reduced local SGD with lower communication complexity. arXiv preprint arXiv: /912. 12844, 2019.
Tao Lin, Sebastian U. Stich, Kumar Kshitij Patel, and Martin Jaggi. Don't use large mini- batches, use local SGD. In Proceedings of the 8th International Conference Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020.
Yanli Liu, Yuan Gao, and Wotao Yin. An improved analysis of stochastic gradient descent with momentum. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020.
Amirhossein Malekijoo, Mohammad Javad Fadacieslam, Hanich Malekijou. Morteza Homayounfar, Farshid Sizzadh--Shabdis and Reza Rawassizadeh. FEDZIP: A compression framework for communication-efficiee federated learning. arXiv preprint
2021.
Brendan McMahan, Eider Moore, Daniel Ramage. Seth Hampson, and Blaise Agüera y Arcas. Communication-effciieee learning of deep networks from decentralized data. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pp. 1273- 1282, Fort Lauderdale, FL, 2017.
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 (NeurIPS), pp. 14606-14619, virtual, 2021.
Mehryar Mohri, Gary Sivek, and Ananda Theertha Suresh. Agnostic federated learning. In Proceed- ings of the 36th International Conference on Machine Learning (ICML), pp. 6615-4625, Long Beach, CA, 2019.
12

---

Published as a conference paper at ICLR 2024
Boris T Polyak. Some methods of speeding up the convergence of iteration methods. Ussr compu- tational mathematics and mathematical physics, 4(5):1-17, 1964.
Sashank J. 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 on Learning Representations (ICLR), Virtual Event, Austria, 2021.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. FedPAQ: A communication--ffiiii tization. In Proceedings of the 23rd International Conference on Artificial Intelligence and Statis- fics (AISTATS), pp. 2021-2031 Online [Palermo, Sicily, Italy], 2020.
federated learning method with periodic averaging and quan-
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), pp. 4386-4396, virtual, 2021.
Abdurakhmon Sadiev, Grigory Malinovsky, Eduard Gorbunov, Igor Sokolov, Ahmed Khaled, Kon- stantin Burlachenko, and Peter Richtárik. Federated optimization algorithms with random reshuf- fling and gradient compression. arXiv preprini arXiv:2206.070211 2022.
Mher Safaryan, Egor Shulgin, and Peter Richtárik. Uncertainty principle for communication com- pression distributed and federated learning and the search for an optimal compressor. Informa- lion and Inference: A Journal of the IMA, 112)5557-580, 2022.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs. In Proceedings of the 15th Annual Conference of the International Speech Communication Association (INTERSPEECI), Singapore, 2014.
pp.
Sebastian U. Stich. Local SGD converges fast and communicates littl. In Proceedings of the 7th International Conference on Learning Representations (ICLR), New Orleans, LA, 2019.
Sebastian U. Stich, Jean-Baptiste Cordonnier, and Martin Jaggi. Sparsified SGD with memory. In Advances Neural Information Processing Systems (NeurIPS), pp. 4452-4463, Montréal, Canada, 2018
Jianyu Wang and Gauri Joshi. Cooperative SGD: A unified framework for the design and analysis of local-update SGD algorithms. J. Mach. Learn. Res., 22:213:1-211:50, 2021.
Jianyu Wang, Qinghua Liu, Hao Liang, Gauri Joshi, and H. Vincent Poor. Tackling the objective in- consistency problem in heterogeneous federated optimization. In Advances in Neural Information Processing Systems (NeurIPS), virtual, 2020a.
Jianyu Wang. Vinayak Tantia, Nicolas Ballas, and Michael G. Rabbat. SlowMo: Improving communication-efficintt distributed SGD with slow momentum. In Proceedings of the 8th In- ternational Conference on Learning Representations (ICLR), Addis Ababa, Ethiopia, 2020b.
Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. Gradient sparsification for communication- efficient distributed optimization. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1316, Montréal, Canada, 2018
Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. In Advances in neural information processing systems (NIPS), pp. 1509-1519, Long Beach, CA, 2017.
Jaxxiag 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 Interna- tional Conference on Machine Learning (ICMI., pp. 5321 5321-5329, Stockholmsmässan, Stockholm, Sweden, 2018
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST. a novel image dataset for bench- marking machine learning algorithms. arXiv preprint 1708:::7000077700 2017.
13

---

Published as a conference paper at ICLR 2024
Yan Yan, Tianbao Yang. Zhe Li, Qihang Lin, and Yi Yang. A unified analysis of stochastic mentum methods for deep learning. In Proceedings of the Twenty-Sevenie International Joint Conference Artificial Intelligence (IJCAI), pp. 2955-2961, Stockholm, Sweden, 2018.
Haibo Yang, Minghong Fang, and Jia Liu. Achieving linear speedup with partial worker participa- tion in non-iid federated learning. In Proceedings of the 9th International Conference on Learning Representations (ICLR), Virtual Event, Austria, 2021.
Kai Yang. Tao Jiang, Yuanming Shi, and Zhi Ding. Federated learning via over-the-air computation. IEEE Trans. Wirel. Commun., 19(3):2022-2055, 2020.
Yeojoon Youn, Bhuvesh Kumar, and Jacob Abemethy. Accelerated federated optimization with quantization. In Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurlPS 2022), 2022.
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 on Machine Learning (ICML), pp. 7184-7193, Long Beach, CA, 2019a.
Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted SGD with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI), pp. 5693-5700, Honolulu, HI, 2019b.
Kun Yuan, Yiming Chen, Xinmeng Huang. Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. DecentLaM: Decentralized momentum SGD for large-batch deep training. In Proceedings of the 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pp. 3009-3019, Montreal, Canada, 2021.
Kun Yuan, Sulaiman A Alghunaim, and Xinmeng Huang. Removing data heterogeneity influence enhances network topology dependence of decentralized sgd. Journal of Machine Learning Re- search, 24(280):1-53, 2023.
Nesterov Yurri. Introductory Lectures Convex Optimization: A Basic Course. Kluwer Academic Publishers, Norwell, 2004.
Xinwei Zhang, Mingyi Hong, Sairaj V. Dhople, Wotao Yin, and Yang Liu. FedPD: A federated learning framework with adaptivity to non-iid data. IEEE Trans. Signal Process., 69:6055-6070, 2021.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. BEER: fast O(1/T) rate for decentralized nonconvex optimization with communication compression. In Advances in Neural Information Processing Systems (NeurIPS), New Orleans. LA, 2022.
Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated 2018.
learning with non-IID data, arXiv preprint
14

---

Published as a conference paper at ICLR 2024
A INTERPLAY OF CLIENT-DRIFT AND COMMUNICATION COMPRESSION
We depict the evolution of local and global models in a client-server communication round of com- pressed FEDAVG with 2 clients with 3 local steps as Figure 3.
yiew
client
xi
client update
server update
X
neww
Y/1
client drift
compress. error
neew
idcal SGD
full precision
x²
client model
server model
client
Y2
X2
client opt.
server opt.
Y22
new
Figure 3: Interplay of client-drift and inaccurate message aggregation incurred by communication compression in FEDAVG is illustrated for clients with local steps (f.e. S = N 2, K 3). The client updates y:
(blue circle) move towards the individual client optima æ; (blue square). The server updates (black cirele)
move towards a distorted praxy, depending on degree compression, the full-precision averaged model DE zi (grey circle), instead of the true optimum x² (white square).
B DETAILED IMPLEMENTATIONS OF SCAFFOLD
Algorithm 3 SCAFFOLD: Stochastic controlled averaging for FL (Karimireddy et al., 2020b)
1: Input: initial model x. and control variables [ [== e0; local learning rate mi global learning rate Ty: local steps K; number of sampled clients S
2: for t = 0, ... T do
3: Uniformly sample clients St S [N] with |S
4: for client E St in parallel do
5: Receive x'' and c²; initialize y, 1.0 = x
6: for à: = O,...,
do Compute a mini-batch gradient 9; FF 1.k. : t.k m mi
7:
Locally update v, f.k+1 end for
t.k ci + ce)
8:
9:
10:
Update cf+ of - -c" + x' z'
mk (for i $ st, d++ = c))
11:
Send yf x. and of41 of to the server
12:
end for
13:
Update re+1 x² + 26
Eies: (vi __K x²))
14:
Update ++1 c¹ + N Edess cf)
15:
end for
The original implementation of SCAFFOLD (Karimireddy et al., 2020b) stated in Algorithm where no compression is employed in communication. In this implementation, cach participating client needs to transmit the increments of both local model y² -y² and control variable cf f+ to the server at the end of local updates, resulting to rounds of uplink communication for per training iteration.
By communicating the increment variable Af. can implement SCAFFOLD equivalently with only a single round of uplink communication for each participating client, as described Algo- rithm 4.
15

---

Published as a conference paper at ICLR 2024
Algorithm 4 A simplified formulation of SCAFFOLD with single-variable uplink communication
1: Input: initial model x² and control variables {c c local learning rate mi global learning
rate 7y: local steps K; number of sampled clients
2: for -===0,, 0, ... - do
3: Uniformly sample clients S S [N] with |S*|
4: for client E St in parallel do
5: Receive x' and c²; initialize 4.0 x²
6: for k = .,,
do
7:
Compute a mini-batch gradient 9; Fy : Locally update uft = t.k end for
8:
mi mi c + c¹)
t.k
9:
Compute A = ='-p, e' and send A to the server
10:
mih
Update g+1 of + A (for & S', o
2+1 dt) 3 Eiesr (A + dt)
12:
end for
13: Update I=+1 x² 20nK
14:
Update c++1 + N EiEs:
end for
C MORE DETAILS, DISCUSSIONS, AND COMPARISONS
C.I UNBIASED AND BIASED COMPRESSORS
Examples of popular unbiased compressors include:
Example (RANDOM SPARSIFICATION (WANGNI ET AL., 2018)). For any 8 E [d], the rundom-s sparsification is defined as x - ( @ x) where denotes the entry-wise product and & d is a uniformly random binary vector with s non-zero entries. This random-s sparsification
{0, 1 is an w--ubbaased compressor with w d/s -
Example (RANDOM DITHERING (ALISTARH ET AL., 2017)). For any b E N+. the random dithering with b-bits per entry is defined as C + |||||| x sign(x) @ ((x) where Ha are independent random variables such that
12 xx|1/<=1||||] /2", with probability [2*[ /|]] 20|=1|/|<=]|,
(c(x)) = 2 xx//==|| /2",
otherwise.
where L.] and [-1 are the floor and ceiling functions, respectively. This random dithering with b-bits per entry is an w-unbiased compressor with w = min(d/4", vd/2²).
Common biased compressors include (Li & Li, 2023):
Example (TOP-r OPERATOR). For any E [0, 11. the Top-r operator is defined C (1 (x()))&){ where S,(x) is the set of the largest r x d entries of x in absolute values. Top-r operator is conttrcctvv compressor with q² =
Example 4 (GroUPED SIGN), Given partition of [d] with M groups (e.g.. layers of neu- ral networks) {Im ) the grouped sign with partition {Im } is defined as C x + MM Σ m=1 II 1a @ (ign(x)z../I.mm) This grouped sign operator is q² -contractvve compressor with = -1 1/ m Imm]
C.2 COMPARISON OF SCALLION WITH PRIOR METHODS
Comparison with FEDPAQ (Reisizadeh et al., 2020), FEDCOM (Haddadpour et al., 2021), FED- EF (Li & Li, 2023). All of them boil down to the FEDAVG algorithm (McMahan et al., 2017) when no compression is conducted. As such, their convergence is significantly hampered by data heterogeneity across clients due to client drift. The former two works do not consider partial partic- ipation, and FED-EF suffers from extra slow-down factor in the convergence rate under partial participation. In opposition, SCALLION roots from SCAFFOLD, and robust to arbitrary data heterogeneity and partial participation.
16

---

Published as a conference paper at ICLR 2024
Comparison with FEDCOMGATE (Haddadpour et al., 2021). FEDCOMGATE applies com- pression over the uplink communication of the VRL-SGD algorithm (Liang et al., 2019), a gradient-tracking -aased FL method which is different from SCAFFOLD. FEDCOMGATE sug- (N))(N)) local steps, demanding solving local problems to an extremely
gests conducting accurate resolution. Moreover, it additionally requires uniformly bounded compression errors E [iE[N] 2 | EiE(N] 2; [| S G2 which are invalid for practical compressors such as random sparsification (Wangni et al., 2018) and random dithering (Alistarh et al., 2017). In addi- tion. both the convergence for FEDCOMGATE and VRL-SGD is only established when all clients participate in training. It is unclear if their convergence can be adapted to partial client participation. In contrast, SCAL.LION converges at a state-of-the-art rate that admits flexible number of local steps and client sampling and employs standard unbiased compressors (i.e., Definition I).
C.3 CONNECTION BETWEEN SCAFCOM AND ERROR FEEDBACK
SCAFCOM does not directly pertain to the vanilla error feedback (Seide et al., 2014; Stich, 2019), technique widely used to tackle biased compression, but relates to the newly proposed EF21 mechanism (Richtárik et al., 2021). If one sets 3 = in SCAFCOM, then the message of would be compressed and the control variable would be updated Ek=0 FV c 5 c)). Under the simplification where o 0 (i.e, full-batch gradients), K = (i.e., no local updates), S = N (i.e., full-client participation), it be- comes C; 1+I of + C. <t) and the global model is updated as x'+1 x² ngghc ++ with
k= VF L.k ct K K-1 DD K-1
188
as c c C,(K Σ
Li= recovering the recursion of EF21
C.4 WEAK ASSUMPTIONS OF SCALLION AND SCAFCOM
Due to comprehensive challenges in compressed FL, to facilitate convergence analysis, most existing approaches require additional stringent conditions or assumptions that are not necessarily valid in practice, including but not restricted to:
max ISKN [V SG
(Bounded Gradient Norm (Basu et al., 2019))
V)(+) - <
(Bounded Gradient Dissimilarity (Jiang & Agrawal, 2018; Li & Li, 2023; Gao et al., 2021))
1 z4
E
(ax))
C
N
A
1=1
(Bounded Compression Error (Haddadpour et al., 2021))
N
N
N S A
E
Cl(x))
1
Σ
34
1
N
N
==1
(Averaged Contraction (Alistarh et al., 2018; Li & Li, 2023))
As a result, their convergence rates inevitably depend on the large constants G, C. G (1 - gA) In contrast, the convergence results of SCALLION and SCAFCOM presented do not rely any such condition.
17

---

Published as a conference paper at ICLR 2024
D PRELIMINARIES OF PROOFS
Letting - Ng K the recursion of SCALLION and SCAFCOM can be formulated as x²+11 x² ----0 nd where d' 1/2 Eies: of + and o C,)) For clarity, we let gft
E K- K Zk= 9i 1ik
>E as Di g¹ A N E== si. d'+1 A = Eies' 0f cc'. We will abbreviate Ei Σx Σ
ΣxS Li,k respectively, when there no confusion. We also define the auxiliary variable U =
Ei= Ex=1 Ellly 1.k x' Ill to facilitate the analyses. is worth noting that c' N Σx= of for for a 2 0in both SCALLION and SCAFCOM. Besides, the exclusive recursions are as follows.
NK
For SCALLION. Due to client sampling, it holds that
c + Cia(gg - <)) i St
q
x+1
(8)
c
otherwise
and d² = Eies alg c) +c
For SCAFCOM. We additionally let us that
- ot + t v/).
Then, due to client sampling, holds
(uf d++)+) "fftlcct1 (utt),c , C -)) i St otherwise
(9)
(vf
and d=+1 $ (u ct) + dt. Similarly, let of A D of and u²+1 A
N Em ii utt1 = (1 -)r* + Bg'
Let F- and Jt-K == ouUEE JosseR U FF-1) and F (f (8')) for all t > 0 where (-)) means the o-algebra. We use E[[] to indicate the expectation taking all sources of randomness into account. We will frequently use the following fundamental lemmas.
Lemma ((Cheng et al., 2024)). Given any a1, ... aNN E Rd and a = + Eie(n] as and uniform sampling S c [M] without replacement such that [S] = S. it holds that
Es
Σ ÉES
03
a
Σ |a, all2 |all + SN
Σ
|a; - b112.
SN
Lemma 2 ((Karimireddy et al., 2020b)). Suppose {Xi,-.. ;,,] S Rdd be random variables that are potentially dependent. their marginal means and variances satisfy E[X.] = psi and B[[]X; malla] < o², then it holds that
Σ
X
14
+ 2
If they are correlated in the Markov sense with conditional means and variances satisfying μ4 and B|I[X; - pilla] < a² (XH: check here B[||X; pill? mil S 0²I.
-X]] X-x,|X
Then tighter bound holds
27
E
Σ
X
S 2E
Σ 14
+ 2To2.
Lemma 3. Under Assumption for any E [o, 1] and ",,...,. UN E Ft-1, it holds that
[|][ - 8)v + 0(g - fx()))]
282
S min [1 - [ 30 130, (1
0] +
(10)
NK
and
B||[(1 0)0; + 0 -
N
min
ElI[( 0).,1111 + 30 30 L2Ut
1 -
Σ Ellls11 20L /
202
K (11)
N
N
18

---

Published as a conference paper at ICLR 2024
Proof. have
We mainly focus proving (10) (11) can be established similarly. Using Lemma 2,
B|l(( 8)u + 0(g' vf(x')))
=B]I[(1 0)vl +1 I { (1 (1-0)e, 0), NK
Σ FFul - VOLOT))
+ F
Σ VF( : Vii(a')
NK
(1-0)e, Σ V.(l(t )
<BIII(1 - 0)000 1 + IE
NK
i,
20202
+ 2
- -
+
NK
NK
i.k
27
0
<B
B)u +
Σ Vf(u.* Vf((a')
NK
+ E
1 NK
E
V V<i(tt)
208
NK
By further applying Sedrakyan's inequality [1 - 0)e + 00' S (1 00]lul11 + 0110' 12 and As-
sumption 1, we have
[| 0)v + O(g' {z(
20
<(1 - []-0)\[]lu|1> 0(1 + O)E
Σ V(((t/t)) -V
+
NK
NK
i.
282
<(1 | +
NK
The other upper bound of (10) follows from
[|(1 11-0) 0)v 00' s 211(1 0)u112 + 20 1012.
19

---

Published as a conference paper at ICLR 2024
E PROOF OF SCALLION
In this section, we prove the convergence result of SCALLION with unbiased compression, where
we additionally define x := zº. We thus have E||| - x'~ - = for = 0. Note that x x-1 is
defined for the purpose of notation and is not utilized in our algorithms.
Lemma (DESCENT LEMMA). Under Assumptions and it holds for all 2 0 aand y > 0 that
B]f(x(+)]
<BIS(x0)]
2
V [(('))
2
1
L
E|||z' (+ - -2'112 4n (1+ (1+
L L'EeIIa' - 11
27
2
s
87(1
+ w)
+4y 1+ (1 + w)a²
+
12
SK
s
4(1 + w)
+7 4B|l|c
\|(
s N Σ
Blllet V (12)
Proof. By Lemma 2 of Li et al. (2021); we have
f(x 1 f(x²) V vf ||
1
|1 - -2/12+ -
27
2
where d++ = 1 Eiesi 5% + c². Letting d=+1
1
&Eiest 0%
cc, we further have
1x**11 Ss(x')
2 |
1
L
| - 1011
2
27
2
+ -
112 + r|ldtt1
ff(x))11
(13)
For || (1())) using Lemma 2 and the fact that r¹
= N E, of and d++1= = 1/3 Eiesi a(g)
<) + c², we have
E|lldt+ (1()))
algi - -c) - -V/(e) |
=E
c¹ + Σ
iES
+ a² Σ Bilgo ct119). (14)
< a) ff(x)) + alg' vf(x
SN
Using (10) and Assumption 1, we further have
Bi](11 a)(c' - v((x))) + alg' - \
2a²0²
<2Ellle - (f
+ NK
2a2002
<AEllle²
AL' +
(15)
NK
Similarly, using (1I) and Assumption 1, we have
a²
2a
20²
Elllg 21 -
Elllct Vf((2))111+
Σ Elllg Vii(+')11
SN
SN
SN
2a
4a²
4020²
Σ
Bllld v/(('))[++
L2 +
SN
5
SK
4a²
4a 22
- - Vf((0'
E 10" -----"--11" 1111
SN
S
4a² 2
Lt 4a20²
+
(16)
S
SK
20

---

Published as a conference paper at ICLR 2024
Plugging (15) and (16) into (14), obtain
E|||d++1 [
<4Ellle² ( || + 4
Σ
Ellle - //((0"-1113
S N
(1
a² g
1a²0²
+ 4 + 5 L² + 4
L2 "P +
(17)
K
For || + 1|2 1 using mutual independence and Definition have
1
Ellld+1 d 12]
=E
Cl((st c)) - -a(gi - ct) -ct)
S
VES!
wa?
wa? 1
E
Σ
llol - c!|1?
Elllo - c..1%.
S2
S N
LIES
Then applying the same relaxation in (16), we obtain
4wa?
4wa L
El||d++ dl 1131 -
Σ Bllld - (f((1-1))1
18
1121
SN
S
Awa?
U2 + 4wa2o²
(18)
SK
Plugging (17) and (18) into (13) and noting N < S-1, we complete the proof.
Given Lemma 4, the rest is bound ||c² -cc'-V (=(===1)11+ ||c
Vf((x="1)
Lemma 5. Under Assumptions I and 2, it holds for all t that
Ellle*+1
vf(x')
Sox
BBIle* [ 4(1 + ww) 1
1
Blllet - V/((''1))1
2N
N2
N
2N
4(1 + w)
T.² T.2B[IIa' - -3'-1113
Sa
N
25
4(1 + w)s
6(1 + 252
UL?U
(19)
N
N2
N2K
Proof. Using (8) and Lemma 1, we have
Ellle+11 V [2
S Clalss -c) +c Vs((')) -c)(+))
-E
N
(o) +c)+++ + -VS(o)) 17
So
+ 2
<B
Eillot cf
N
N
iE
Sa
|
(1 + w)aa
<B
(g' - d²) d - V
+
Elllot c
(20)
N
N2
N
21

---

Published as a conference paper at ICLR 2024
Using (10), Young's inequality, and Assumption 1, we further have
Sa
E
(g'
c²) + - V((x")
N
Sa
2aSL2
202
<
1
Bllle' - []((*)]
U¹ +
N
N
N
Sa
Bille* - V
2N
ElIl=' 1
Elll=*
x2
2aSL²
U
2025202
N3K (21)
2N
Sa
N
Using Young's 's inequality and Assumption 1, we can obtain
(1 + S 1
El|aa <41""]
N2
N
(1 + w 1
(2ElIIc) - V[[('') 21ll vii())))11)
N
N
(1 + w
(IB[IIc
+ - -1-2
2F - )/(()
N2
N
-
(22)
Using (11), we have
Blllg < 2 + 202
(23)
N
K
Plugging (23) into (22), we reach
(1 ++ 2 1
Elllo - <211
N2
N
(1 () 1
402
Σ
4B[lIc
44 x2-11111+ + + K (24)
N2
N
Combining (00), (21), (24) together and using
g² N
(1+w)n2se N
completes the proof.
Lemma 6. Under Assumptions I and 2, suppose 0 S a S a(++1)' then holds for all 2 0 that
Blllctt {1{
N
Sa 1
Σ Ellc - Vf((=~11)11 4NT.
<
E[[a=* - 112
4N
N i
Sa
3aI25
2(1 + w)
+
Ut +
(25)
N
NK
Proof. Using (8), we have
1
N Elllet
- (
ト Σ (1-3 5
S ETIIC -()) + v.(
El14 - vf((2'))1
N
N
N
N Σ
5
BliIc v)(()'))
S
Blllacol -c4) + (
N
N
Swax 2 N
Elllot cf(13]
(26)
22

---

Published as a conference paper at ICLR 2024
Note that
S
Bllla(d - -c) +
v+((''11 -
N
N
S
Bllla[g v.((z')) + (1 - a) Vf((z'))
N
N
S
1-
Elllc - vf(('')]1 2 20²02
(27)
N
N
K
and by applying (11),
w
Σ
Bllls
c|l
4wa? 5
Σ
E
2 - V[((+') - 1 ([((((=)) o3)
-
N N
N
N
4wa
5
1
(lIV - cf11 + L² + a²
(28)
N
2N
2K
Plugging (27) and (28) into (26), we obtain
Blllet+ f(('))111
Sa(11 - 2wa)
1
+ +wa))SS Bille - vf((='))1
2(1 + w)aa So²
Ut
N
N
N
NK
So
3aSL² U
2(1 + w
Billc
vf(('')]
+
2N
N
NK
where we a tion we obtain
Tw+1J in the last inequality. By further using Young's 's inequality and Assump-
Bille {f(()))
Sa 1
4NL2
Σ Ell c - \f((
EiIaa x1-1
4N N
Sa
3aL
2(1 + S0²
+ N
U +
NK
Lemma 7. Under Assumptions 1 and 2, it holds for any 1. ' O and 1p KT. S } that
Ut 9e K2n
Σ [Blllc} V L2 2'-1 Elll E[|[v((2')111) + è² knkoo²
N
Proof.
The proof is similar to that of Lemma 12.
Theorem 3. Under Assumptions I and 2, suppose clients are associated with mutually indepen-
dent w-unbiased compressors, if we initialize oi B DF (b)) d
E & with
B B 1b=1 D; and B 2 NLA (c) + Vf((x²) as B + 00), set
o²
KKL < 1400<2 no = 27aS
a(l+w)
N
(29)
a 4(1 [w (LL+W)TSO? 1/2
(LL+W)TO 1/3
("NKLAA
+ (-NKIA
NKLA
23

---

Published as a conference paper at ICLR 2024
then SCALLION converges as
T-1
WA+
(1+ 1/3
) +
NTA
T B||Vv((*)) V
SOKT2
SKT
ST
where A A f(x0) min f(x)
Proof. Adding (19) x 10yN
to (12), we have
as
B[ + 10
-
{5(x))
a.S
10N
<B[f(=') +2
(f(x"11)1 -1)B1lec- Bllle*
[B(IVf(('))1 2
as
(2 1
L
1Bll=' 1BIlat1- 2011
1 + 7L2 7
(44(1 <41(1+Wja +W) 24N2
BlIle x0' 113
2
S
a25²
8 +
60a) 0²
224+ 4(1 w))a
40(1 + w)a
+ 7(1 + ww)
+yL²
0r
N
K
S
N
40y(1 w)
Blll
(30)
Adding (25) x (1+m to (30), we have
10yN
El|l E1 {(()))] 1647(1 + w)
1
E Els(z
B
Blllctt e+1 - (
as
S
N
<B[s(z')] +
10N
-1)
Billc- vs(x"~1))1 1
as
1647 ww)
7(1 w)
1
Bllld
V ffa===1111
S
N
1
L
El||
E
2
2>
2
44(1 + w)a
2
656(1 + W)N
+ 772
B[Il - 119
0²5²
0152
18a2
60a
328(1
+ w)a² 02
+ 7111+ +w)
S
N
N
K
4(1
w)a²
522(1 w)a
+ 775² 24 +
U?.
(31)
S
N
Defining the Lyapunov function (a := x²)
10yN Φ' = E[f(+')] +
1647(1 + +w)
1
as Ellle* V fxx="1111 1111 +
Bllc v
S
N
24

---

Published as a conference paper at ICLR 2024
following (31), obtain
0'+1 of
211 w)
5 - - EI V -(""")1") - -
Σ Bllld - V.i(
N
N
-
22
2
44(1
w)a
24N
656(1 + W)N
a² +
E
B[|l0* - 11
5
as²
880
60c
328(1 + w)
0²
+ +1(1 +w)
+
+
S
N
N
K
4(1+w)a²
522(1 + w)a
+ 77, 24
U¹
(32)
S
N
Since N 2 1 and a & 11((411 + W)), we have
4(1 + w)a²
522 + w)a
12
24
S
N
1 +
261
a(1 + w)
24
1400c2 =
S
(33)
4 2
N
4
Combining (33) with Lemma 7, we have
? 24 + 4(1 + w)a?
522 + w)a
S
N
7(1 + w)
S-Bllle - v 1 || +
ElIe - (
N
N
2L
7a(1 + w)oz
+ 4
Bl1l
-2- +
(34)
4
NK
Plugging (34) into (32), we reach
r'+1 Φ'
Saa
60c
328(1 + w)a?
0²
s
+
N
K
L 4
E1l
x |/1
27 2
444(1
w)a 25
656(1 + W)N
+ T,2
Bl1l.* - 111
(35)
5
5²
5252
Due to the choice of 7 = M and a < Nw++y . it holds that
1 L
44(1 + w)a
25
656(1 + W)N
2 2
11
2
5
2²5²
a.52
Averaging (35) over It and noting
|,200
x 1-1
0, 0(11 + =1)) obtain
$0
a²
(1 + w) o²
B[|VS(+>)]
+ +w++w)
TT
5 N
K
Φ0_
TT
a²
o²
+ (1+
TT
5
25

---

Published as a conference paper at ICLR 2024
By the definition of Φb, it holds that
LA
N
+
Blll - vfi(2')11
YT
T
as
T
S
T
LA
N
o²
T as
aSBT
where the choice of 7, a, and the initialization of (cIVEIN) and c in the second inequality. Due to the choice of B, we have o² OSET
LA N and thus
T 03
N
( a²
a²
7 Σ
B
as + (1 (I+w)
[5]
(36)
N
K
Plugging the choice of a into (36) completes the proof.
26

---

Published as a conference paper at ICLR 2024
F PROOF OF SCAFCOM
In this section, we prove the convergence result of SCAFCOM with biased compression, where we
additionally define x- == 2². We thus have |f[||* -² = for t = 0. Note that x: x=1
defined for the purpose of notation and is not utilized in our algorithms.
Lemma (DESCENT LEMMA). Under Assumptions and 2, holds for all 2 0 and y > 0 that [[
<B[[(=")] - 2 -(]
1
L
ElI - x 113] + 16 -
11
27
+y
4Bll|o -f(=")))111
12,3
Σ
Billu
- vf((((
12 N
Σ
Bllld - c$1191
N
878800
+ K + 1,20
(37)
Proof. By Lemma 2 of Li et al. (2021), we have
( ?
1
1.
|1 -2'12 -
27
2
2
where dc+1 = 3 Eiesi 8 + ct Letting d=+1 A 1
Eiese 0f + c², we further have
1(x <f(x²)
2 |V
1
|| - 2212
2
2x
+ , 11 + > 7/1dtt1 vf(x1)]1
(38)
For (xxx)] using Lemma and the fact that c²
N E, ct and d= -/ (uft
cf) + c². we have
E d
v)(x')111
=B
c² + Σ
(u
c -V)))
iES!
<EIllte+ vf(x')|] |1 + SN
Elllyt 1-1 cc
=E]][(1 ()* - -f(x')) + B(g [[(+)))11
+ SN
1
Σ
E Ellly + B(gt - u/) - (3(1))))
Using (10) and Assumption 1, we have
[[][(1 () vf(x') + Blg' Vf(2'11
+ 23
<|E|||o -
NK
2,2
<4Blllo' - +| 4L - - 33 3
(40)
NK
27

---

Published as a conference paper at ICLR 2024
Similarly, using (11) and Assumption 1, we have
|f + B(g - -ff [
SN
1
- + B V(((z')) cf11
SN
2
B - + 3,
202
+
SN
SK
6
L
2
[Bllo c +
- +
SN
SK
(41)
Plugging (40) and (41) into (39), we obtain
Bl {
<4El||u² Vf(x'-1||1'
6.3
Σ
Elloo (f((
6
Σ Elllot c
S
SN
6,3
(N-1 + 5-1) 2.320 2
+ +311 + 5 L2
4+
||| L'
L
K (42)
s
For ||d+1 1 using Young's inequality and Definition 2, we have
Ell - d 12] =E
Σ iESt
Ci( ct) - (u, +1 ct)
q² E
q²
Σ ||u ++ &t|1
Σ
Blllu ++1 - c]113]
5
N
LiESt
q²
B[llut + B(ot - ut) - ct|111.
N
Then applying the same relaxation in (41), we obtain
E Billd+1
1121
6q 2
Σ [1llo - ct( 3 -
V.A L3 - 111)
N
+ +38 L2 + 233
(43)
K
Plugging (42) and (43) into (38) and noting N-155 < 1, < 1, we complete the proof.
Given Lemma 8, the rest is bound ||ot v[(x*-1)]] |oo v.f(=(=1))13 and ||o
Lemma 9. Under Assumptions I and 2, it holds for all t 0 that
E| El||o'+ +1
S3
4
E|||o* - -V(( ||3
Bllle - V
2N
N2 N
62
6BSL2 2
6.3 So²
E|ll0* -
T +
(44)
SB
N
N
28

---

Published as a conference paper at ICLR 2024
Proof.
Using (9) and Lemma we have
18 1
fx()))
1
SB (o! - uf) - -VS(ot)
E
S NE
8B (g) - + + -V((a)/
3 1
<I
+
Σ
E Bilbo 1/19
N2 N
(1- S3 (v' - vs((4)) + N (g' v(a'))
SB
B²S
Σ
B Billo - off (.(5))
N2
Using (10), Young's inequality, and Assumption 1, further have
(
53
(0t vf(x')) + S3
E
lg' vf(x'))
N
N
$B
2
52
<
Blllo' B V(('')
U +
N
N
N3K
SB
2
23SL?
282
<
Ellly* - ()(x
Bl|l -1
U +
(46)
2N
SB
N
N
Using Young's inequality and Assumption 1, we can obtain
S
1
Bl[lot =f[]²]
N N
8 1
(2 -
v)(()*))13)
N N
B
(4ElIluf - vf(a"' + 11 + [ - v/((o+))121) ((7)) (47)
N
N
Using Lemma 2 and Assumption 1, we have
Elllot V
202
20²
Σ E
-
+
S 2L +
(48)
K
K
Plugging (48) into (47), we reach
S
Elllot - 11
N2 N
BS N N
40
4BilIof [(((
11-1 4T.2U' +
(49)
K
Combining (45), (46), (49) together and using g² N
<
8 N
NL2
s² 2
<
BSS.
Nº
S
N
N
completes the proof.
Lemma 10. Under Assumptions and it holds for all 2 0 that
-
S3
1
2N
<
Σ
-
El
[
2N
N
SB
23L2S
2, 202 So²
Ut
(50)
N
NK
29

---

Published as a conference paper at ICLR 2024
Proof. Using (9), we have
N Blllet
- V[i(('))1
1
Σ
S
Elllu - VfA(2')
|| of) of - -V((a)))))
N
N
N
53
Blllo - v 2.I.2S S
2 So²
$ N
Σ
U +
N
N
NK
where the inequality due to
E ||3Cat - w/) + m -
|| - vf((z')) + (1 ( - vf((=')) [*]
E
N
Ell V/(CC))9)+ 2320²
Σ
N
K
by applying (11). By further using Young's inequality and Assumption 1, we obtain Blllot
1 N
Vf((1')111
S3
1 N
Σ
Blllf - Vfi(o'-)111++
2NL2
E 1/2 x'' 2'-1112 11]
2N
SB
28L2S S
232 So²
U*
N
NK
Lemma 11. Under Assumptions 1 and 2, it holds for all 2 0 that
1 N
Σ
Blllot
11
5(1 9)
1
Σ
Blllut - +2| -G11)
432 1 (1 2)N N
E B[llyt Vi((a' [19]]
N
N
48"L292S
SLL U 2 q² So²
+
11[1a* 11in====--1p 1--
(51)
(1 - N)N
(1 - 2)N
NK
Proof. Using (9) and Definition 2, we have
S
- ( -
1
Elllyf - - + Blllutt2 1+1 - -C((ut+ - -c) - -601
N
N
S
S q²
<
1
Blllyf - d +
-
N
N N
1
S
Billy c +
S q² N N
Σ
Blllu + B(ot -f) - -111 (52)
N
30

---

Published as a conference paper at ICLR 2024
where u1:+1 _ of + Bigl of). Using Lemma 2 and Assumption 1, we have
g²
B Bfllof + 3(91 - =f) -=(1]]
o² N
Σ Blllot + ((Vf of) B(of - V.((=)) - -117
N
BlIlo of + ((V - -
N
1/ + + 3(V - -,),, 1 E Viilet VR(GE))
+ 2
K h
VF( - Vsicott 188 1"1)
+
1
-
K K
of + ((V) - 19919
1/ - + ((V)(=))) - ,f), 1
V fiilet vi(cts)
+ 2
K
k
1 Vi(ui - -V/(0)) 17
2,382
+
K
K
& + (V - + 8
K - ((((')))
E
N
2/222202
+ I +
K
By further using Sedrakyan's 's inequality and Assumption 1, we obtain
q²
E of + 5(g) wt) 1
2²
2,32
Billof - +
BI - =
N
1-9
v1(l v (11) + L2 + 2329202
2,32
+ 1 9
K
K
2² N
4
4.2
Σ
10lloo - di11 + 1- q
BlIlet (0)(==1))111
1-9 B1ll=" - x-- 1121
2.32 L 1 +
Elllet 1.k - =191 + +02 232
1 1 K Σ
K
43 1 Σ
4.32L3
4 N
E||lot - 1 +
B [BIV of19]] +
Blll
E
x 1
1 1- N
4
1 +
1
2 ,..2,.55
282qq202
(53)
1-9
K
By combining (53) with (52) and using
S 1/(1 - q), we finish the proof.
31

---

Published as a conference paper at ICLR 2024
Lemma 12.
Under Assumptions 1 and 2, it holds for any t 2 0 and m,KL that
U²
96²
Mo2K2m m
(Billc 1 Blllc Vf((e"-))111 + B - 1| + B[IVf(()')
N
e² KnRo²
Proof. When K = 1, U 0 trivially for all t 2 0 consider K 2 below. Using Young's inequality, we have
Ellby 1.++ =²1 = Bill,, t.k n(o (.k - + - x²1
<Blll 1.6 m
MV 1 - c + df) xz 11/220002
K El Bllby A.k -
+ -1 1/00.
By further using Young's ' inequality and Assumption 1, we obtain / (1) - cf +c1l]]
K E
=K -K--E-)(1(00)VVV<<-<--<<- (c)
<3Kif I. 1.k - -01|3]- + B - -
V/[(=')
Using Young's inequality, have
kkm
2
BII v((x') - {
N
kk
2
N
9kn
[B[| -
B V 1.2 - 1111
N
By combining the above inequalities together, we have
E k+l 2²113]
+ +3 L2) 1 Σ E(lly -
1 + 1-1
x1| + 1f8²
9K c
Σ
(Billc+ - x/(]]] Bllbo v + - +|
N
1 K-1 + 3k ( (o
1
S... < Σ
-f + B1Ilo V/i(2' 111
1=
+ L - + + mioo
) )(2t)))))) (9Km2
1 +
K -1)
2
Σ [E[llc - - )
N
t=
+
-1
(54)
32

---

Published as a conference paper at ICLR 2024
where we use 77: KL so that 3K L2 S k-1 in the last inequality. Iterating and averaging (54)
over h: = o,..., K - 1, we obtain
1
+ 2 )
(2Kni 99Km
U¹
[E[ - of + B - vf(("""))1"
K k 8m
K - 1
N
11 + ni/0
2-2
2
K-1
9K m
1 + K --1
(B8ll 2 + -
N
t
11 + nnpot
96 K2ng
Ken + N
(Ellle - of + Elllut v
+ 11+
where we use the fact (1+
2 R-T )² S e² in the last incquality.
Theorem 4. Under Assumptions 1 and 2, supposing clients are associated with q² conttracctvve com-
pressors, if we initialize cl of = E VF(="; d - + Ei of with (g)) iid D; and
B Z
1191LL (c)- - (z(xx)) as B + 00), set
o²
3(1 1)²
Mg = 200N
28N
mKL S
V 36c2N(189(1 4)² 306,32)'
35
(1
9).
(55)
2
1/2
TSo²
1/3
TSO²
1/1 -1
8= 1+ N2KLA
+
NK(1 - L)
NK - 2)
then SCAFCOM converges as
LAG2
22
1/3
1/4
NLA
T ([]
+
+
SKT
9TT
(1 -
(1 - S)ST
where A L f(x0) - mmnn, f(x).
Proof. Adding (44) x
N
(51) x 1
(1-9)5 to (37), we have
DS
N
R [|||0211 ()(+))] + 14yNV
1
B }]
Billutt +1 - -ct+113
BS
(1 9).5 N
8yN
13N
1
<E[f(z')] +
Elllo* v +
1
Σ
Ellly +1
3S
(1 - 9
N
L
- [1
Bi[l B11l - 29139
2
27
2
48N²
52
+ 2724
16 +
E1||=' - -1-1
8252
(1
9)
483
20
0²
39
+7
8,82
+ +,?
9.32 + 48 +
N
1- 9
K
(1-9) /-
128² + 328
52
+7
+ (1 /)
E
Elllof - v
N
N
33

---

Published as a conference paper at ICLR 2024
Using 9 E [0, and 1 1 S S N to simplify coefficients, we obtain
[] + 8
13y.V 1
El|l V[((2)]
+ (1 18-g): q) N
Billet + - -
35
N
13N
<B[f(x')]+
Ei||²* (f((a-1))11
1
Σ
- -
BS
(1 - -
N
- 2
V
f (x
L
B1||
101
27
2
64N2
52,32
+
222
B1I|2' 11
8
(1
q)²
48,
26,22
o²
39,3²
+ +26²
48 +
U
N
K
(1 q)3
328
64,8
1
+
E[|b - ff
(56)
N
(1 q)²
N
Now adding (50) x 6 1/4 + (1 (1-4)²g)
28N
to (56) and defining the Lyapunov function (x-1 := x0)
N
T² =E]((())) +
Bllle* - 7
3S
13yNV 1
Σ Billyt - c11 + 66y
( 1 +
23N
1
Σ Ellluf - (
9) N
5
(1
9)25
N
obtain
vi+11 yr
S 7
N Σ
1
Ellly +11 +
B
+
2,82
1
Σ
Elllet - (f((==111P))
N
(1 (1- g]-
N
L
S (1) - 24
Bllla,t1 - x. x11
2
2
64N2
52,32
N
2N2
+ 7
+ (1 9)2
+ 132
+
BI BII| x - 11-
3252
1882
(1
5)252
3233
64,3²
B2
2,33
0²
+ 132
+
N
9
N
(1
4)2 K
39/2
B
2
+ +yL2
48 +
132
Ut.
(1 q)2
N
(1 9)2
Using 9 E 10, 1] and 1 S S < N to simplify coefficients, we obtain
w'+ y
3
2,32
N Σ Ell +1| +
Σ E Elll V)( 118]
S -- 7
+
N
(1- 9)3
N
L
f(x
119 -
Blll=0+1 - x 1
2
2n
2
196N2
52,82
264N2
22
+ (1 9)z
E1| - -
8252
(I
- 52
16488
64,²
264
0²
303,32
K + L2
180 +
Ut.
(57)
N
1 q
(1 - q)²
(1 (1-
34

---

Published as a conference paper at ICLR 2024
Using 96² 9 L (180 + (1 (1-9)²
303
9 IN
and Lemma 12, we have
180 + 303,32
11?
U
(1 - q)2
Σ
Blllc - 1²] + ( 18 + 2,32
1
Elllyt
V[((((-1)18)
1)19]
N
N
(1 - q)3
N
2L2
7B002
2 [ |||] +
B(Il=* - -x²- 1131 +
(58)
4
NK
Plugging (58) into (57), we reach y
n'+1
2 / (x)))
BIIV
4
(2/
L
197N2
316N2
-1la+t1-2'112 +
7
Bl|aa*
B1|a''-''11
27
2
32552
(1 (1-9)) -2
165,9
64,²
264
o²
+ 7
+
+
(59)
1-9 q
(1 -1-))²
K
Due to the choice of U1 K, it holds that
1
L
197N2
264,33
2
+ TT?
2
B²
(1-9)²
Averaging (59) over l and noting ||x:0
- 1|-
0, we obtain
B
83
o²
Σ
BIIVS(("))
[13)
+
+
TT
N
1- 9
(1
- 9)
K
1=0
Note that, by the definition of yf, it holds that
00
Vr
T
LA
N Bl|
V
TT
BS
T
N
-01121
1
3N
N Σ, B {2
+
N
+
(1
9)
T
8
(1
9)25) (1-9)28)
T
LA
N
N
0²
1
N
3N
+
+ (1 9
T
BS
(1 S)
BT
35
1)
where we use the choice of and the initialization of (u] heeNN, and dl in the second inequality. Due to the choice of B, we have
0²
1
N
BN
N
N
+ (1
LA
B
BS
9)
(1-9)
-
3S
(1
1)
and consequently
LA
N
N
3
82
33
0²
Σ
EIIVS(~
-
+
+
(60)
T
35
(1 - (1-g)5
N
9
(1
9)
K
Plugging the choice of 3 into (60) completes the proof.
35

---

Published as a conference paper at ICLR 2024
G IMPLEMENTATION DETAILS & MORE EXPERIMENTS
G.1 DATASETS, ALGORITHMS AND TRAINING SETUP
Datasets and model. We our algorithms on two standard FL datasets: MNIST dataset (LeCun, 1998) and Fashion MNIST dataset (Xiao et al., 2017). The MNIST dataset contains 60,000 training images and 10,000 test images. Each image a gray-scale handwritten digit from 0 to 9 (10 classes in total) with 784 pixels. The FMNIST dataset has the same dataset sizes and the number of pixels per image whereas each image falls into categories of fashion products (e.g., bag, dress), making the learning task more challenging. Following (Karimireddy et al., 2020b), fully-connected neural network with 2 hidden layers with 256 and 128 neurons, respectively. We use ReLU as the activation function and the cross-entropy loss as the training objective.
train (non-convex)
Algorithms. We implement our two proposed methods and two recent compressed FL algorithms, with biased and unbiased compression, respectively:
(Biased) FED-EF (Li & Li, 2023): Federated learning with biased compression and stan- dard error feedback. Since our proposed algorithms conduct SGD-type updates in the server, we compare them with its FED-EF-SGIT variant.
(Biased) SCAFCOM (our Algorithm 2): Biased compression for FL with stochastic con- trolled averaging and local momentum. The momentum /3 in Algorithm is tuned over a fine grid on [0.05, 1).
(Unbiased) FEDCOMGATE (Haddadpour et al., 2021): Federated learning with unbiased compression. It uses the gradient- gradient-tracking technique to alleviate data heterogeneity.
(Unbiased) SCALLION (our Algorithm 1): Unbiased compression for FI. with stochastic controlled averaging. The local scaling factor is tuned over fine grid on [0.05, 1].
Besides the compressed FL algorithms, we also test the corresponding full full-precision basclines: FED- SGD (also known as FEDAVG (Yang et al., 2021)) and SCAFFOLD (Karimireddy et al., 2020b), both with two-sided (global and local) learning rates. For fair comparison, execute SCAF- FOLD with our new implementation in experiments, corresponding to the special cases of SCAF- COM (C, I, 8 1) and of SCALLION (C; I, a 1). Notably, under fixed random seed, our implementation yields the same training trajectory as Karimireddy et al. (2020b) at a halved uplink communication cost (by only sending one variable per participating client).
In the experiments, biased compression is simulated with ToP-r operators (our Example 3). Specif- ically, we experiment with TOP-0.01 and TOP-0.05, where only the largest 1% and 5% en- tries in absolute values are transmitted in communication. For unbiased compression, we uti- lize random dithering (our Example 2), with 2 bits and 4 bits per entry, respectively. We tune the combination of the global learning rate ny and the local learning rate yi over the 2D grid (0.001, 0.003, 0.01, 0.03, 0.1, 0.3, 1,3, 10)2. The combination of learning rates with the highest choice (e.g.. B, a, and degree of
test accuracy is reported for each algorithm and compression).
Federated learning setting, In our experiments, the training data are distributed across N 200 clients, in a highly heterogeneous setting following (Li & Li, 2023). The training data samples are split into 400 shards each containing samples from only one class. Then, each client is randomly assigned two shards of data. Therefore, every client only possesses training samples from at most two classes. All the clients share the same initial model at = O. In each round of client-server interaction, uniformly randomly pick S = 20 clients to participate in FL training, i.e., the partial participation rate 10%. Each participating client performs K = 10 local training steps using the local data, with mini-batch size 32. All the presented results averaged over 5 independent runs with the same model initialization for all the algorithms.
36

---

Published as a conference paper at ICLR 2024
2
100
SCAFFOLD-fil
Ood-SGD-IE full
Test Accuracy (%)
1.5
SCAFCOM-topkO.0
80
Train Loss
Fed-EF-topkO.0
SCAFCOM-lopkO.or
1
Fed-EF-topk0.05
60
SCAFFOLD-Nil
Fed-SGD-full
SCAFCOM-
0.5
Fed-EF-topk0.01
MNIST
SCAFCOM-topkO.08
MNIST
Fed EF-topk0.05
0
20
10
20
30
40
50
0
10
20
30
40
50
Communication Rounds
Communication Rounds
2
80
SCAFFOLD-ful
Fed Ped-SGD-full full
Test Accuracy (%)
SCAFCOM-topkO.0t
Train Loss
1.5
Fed EF OF-toppk.01
60
SCAFCOM-IOpKO.00
Fed-EF-toppk.05
SCAFFOLD-ful
Fed- Ted-SGD-full
40
SCAFCOM+topkO.0
Bod-EF-topk..0 01
FMNIST
FMNIST
SCAFCOM-topOO.0
Fed-EF-topkO
0.5
20
10
30
40
50
10
20
30
40
Communication Rounds
Communication Rounds
Figure 4: Train loss and test accuracy of SCAFCOM (Algorithm 2) and FED-EF (Li & Li, 2023) with biased TOP-r compressors on MNIST (top row) and FMNIST (bottom row).
G.2 RESULTS
SCAFCOM with biased compression. In Figure 4, we first present the train loss and test accuracy of our proposed SCAFCOM (Algorithm 2) with momentum B 0.2 and FED-EF (Li & Li, 2023), both using biased ToP-r compressors. We observe:
In general, under the same degree of compression (ie., the value of in the case), SCAF- COM outperforms FED-EF in terms of both training loss and test accuracy, thanks to controlled variables and the local momentum in SCAFCOM.
On both datasets, SCAFCOM with ToP-0.01 full-precision SCAFFOLD, and SCAFCOM with ToP-0.05 essentially match those of full-precision SCAFFOLD. Hence, can reach the same performance while saving 20- 100x uplink communication costs.
achieve very close test accuracy the
For both SCAFCOM and FED-EF, as the degree of compression decreases (i.e., r in- creases), their performance approaches that of the corresponding FL methods under full- precision communication (i.e., SCAFFOLD and FED-SGD).
37

---

Published as a conference paper at ICLR 2024
2
100
SCAFFOLD-full
Ped-SGD-iA
Test Accuracy (%)
1.5
SCALLION-2 bit
80
Train Loss
FedCOMGATE-2 bit
SCALLION-4 bit
1
FedCOMGATE-4
60
SCAFFOLD-til
Fed-SGD-full
SCALLION bit
0.5
40
MNIST
FedCOMGATE-22 bit
MNIST
SCALLION-4 bit
FedCOMGATE-4 bit
0
20
10
20
30
40
50
0
10
20
30
40
50
Communication Rounds
Communication Rounds
2
80
SCAFFOLD-ulI
Fed-SGD-ful
Test Accuracy (%)
SCALLION-2
Train Loss
1.5
FedCOMGATE 2
60
SCALLION-4 bit
$...n.m.
FedCOMGATE-4 bit
SCAFFOLD-
Fod-SGD-HT full
40
SCALLION-2 bit
FedCOMGATE-2
FMNIST
FMNIST
SCALLION bit
FedCOMGATE-4
0.5
20
10
30
40
50
10
20
30
40
Communication Rounds
Communication Rounds
Figure 5: Train loss and accuracy of SCALLION (Algorithm 1) and FEDCOMGATE (Had- dadpour et al., 2021) with unbiased random dithering on MNIST (top row) and FMNIST (bottom row).
SCALLION with unbiased compression. In Figure we plot the same set of experimental sults and compare SCALLION (a = 0.1) with FedCOMGATE (Haddadpour et al., 2021), both applying unbiased random dithering (Alistarh et al., 2017) with and bits per entry. Similarly, we see that SCALLION outperforms FedCOMGATE under the same degree of compression (number of bits per entry). The SCALLION curves of both 2-bit and 4-bit compression basically overlap that of SCAFFOLD, and 4-bit compression slightly performs better than 2-bit compression in later training rounds. Since random dithering also introduces sparsity in compressed variables, the 4-bit compressor already provides around 100x communication compression, and the 2-bit compressor saves more communication costs.
38

---

Published as a conference paper at ICLR 2024
100
100
Test Accuracy (%)
Test Accuracy (%)
80
80
60
60
MNIST
SCAFCOM / 0.05
SCAFCOM 0.1
40
SCAFCOM 0.2
40
SCALLION a- 0.05
MNIST
SCAFCOM 0.5
SCALLION a 0.1
SCAFCOM 0.9
SCALLION 0.2
20
20
10
20
30
40
50
0
10
20
30
40
50
Communication Rounds
Communication Rounds
80
80
Test Accuracy (%)
FMNIST
Test Accuracy (%)
60
60
FMNIST
SCAFCOM A 0.05
40
SCAFCOM /
40
SCAFCOM 9-2.2
SCALLION 0.05
SCAFCOM 0.5
SCALLION
SCAFCOM 0-9.9
SCALLION
20
20
0
20
30
40
50
10
20
30
40
Communication Rounds
Communication Rounds
Figure 6: Test accuracy MNIST and FMNIST of SCAFCOM (biased ToP-0.01) and SCALLION (unbi- ased 2-bit random dithering), with different and values.
Impact of B and a. The momentum factor 3 in SCAFCOM and the scaling factor a in SCAL- LION are two important tuning parameters of our proposed methods. As an example, in Figure 6, report the test accuracy of SCAFCOM with ToP-0.01 (left column) and SCALLION (right column) 2-bit random dithering, for various 3 and values, respectively. From the results, we see that SCAFCOM can converge with a wide range of E [0.05, 1], and 3 0.2 performs the best on both datasets (so we presented the results with B = 0.2 in Figure 1). For SCALLION, we report three a-values, a 0.05, 0.1, 0.2. When a 0.5, the training of SCALLION becomes unstable for 2-bit quantization. As we use more bits, larger could be allowed. This is because, random dithering may hugely scale up the transmitted (compressed) entries, especially for low-bit quanti- zation. When the scaling factor is too large in this case, the updates of local control variables become unstable, which further incapacitates the proper dynamic the local/global training. Thus, for SCALLION with low-bit random dithering, typically need relatively small As presented in Figure 2, a = 0.1 yields the best overall performance. In general, we should tune parameters B and a in SCAFCOM and SCALLION practically reach the best performance.
39


Reviews:
[{"review_id": "KiefM1YqG9", "reviewer": "Reviewer_aALW", "summary": "The paper suggests a federated learning algorithm that finds a stationary point while handling arbitrary client heterogeneity, partial client participation, local updates, and gradient compression. This work introduces an algorithm based on SCAFFOLD which communicates to the server only a single compressed vector. The paper shows convergence to a stationary point under very weak communication and compression assumptions and provides results for both biased and unbiased compressors.", "questions": "How does your paper compare with MARINA?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "* The proof looks sound.\n* I believe that the results for biased compressors are a substantial contribution.", "weaknesses": "1) I believe the paper lacks comparison (both theoretical and experimental) with \"MARINA: Faster Non-Convex Distributed Learning with Compression\". Both papers pursue the same goals, namely handling the following FL issues:\n* arbitrary client heterogeneity,\n* partial client participation,\n* gradient compression.\n\nOverall, as far as I know, MARINA (one of itsvariations) is the closest result in terms of settings (and I think it achieves similar bounds), and I'm not sure whether the authors are aware of it.\n\n2) Theorems 1 and 2: \"set learning rates $\\eta_l$ and $\\eta_g$ as well as scaling factor $\\alpha$ properly\" - the parameters should be specified in the main body.\n\n3) The paper handles local updates (K local updates per round), but this is achieved by dividing the learning rate by a factor of K. In other words, local updates don't provide provable improvement compared to a single larger gradient step.", "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": "", "extra_scores": {}}, {"review_id": "1BB3q3tPkH", "reviewer": "Reviewer_17jD", "summary": "In this work, the authors propose two new algorithms SCALLION and SCAFCOM. Those new FL algorithms show robustness to data heterogeneity, partial participation, local updates and use communication compression. They are based on SCAFFOLD algorithm.\n\nThe authors provide convergence analysis for these two algorithms in non-convex case and show that the convergence rate is faster than rates of previous algorithms. The experiments support theoretical guarantees obtained by the authors.", "questions": "I do not have questions. Probably, I will ask some questions during the discussion period. \n\nTypos:\n1. In the third row of the chain of inequalities, $L^2$ is missed in the second term.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Interesting idea related broadcasting the compressed difference. This new view on the updates from SCAFFOLD help to design new proposed algorithms and to understand why the work.\n2. Only two assumptions are used for convergence analysis.\n3. Well written paper and good presentation of results. It is easy to follow.", "weaknesses": "1. For me there is no reasonable weaknesses. Possible, in camera ready version it would be better compare your methods with this work\nhttps://arxiv.org/pdf/2310.07983.pdf .", "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": "", "extra_scores": {}}, {"review_id": "0DR7MGLa06", "reviewer": "Reviewer_fdMe", "summary": "The paper delves into the challenge of minimizing the objective, which is defined as a finite sum of smooth, and potentially non-convex, functions within a Federated Learning setting. The primary focus is addressing the significant workers-to-server communication costs arising in a centralized distributed framework, which involves one main server and multiple nodes. The authors' contributions can be summarized as:\n\n- They present a novel formulation of the foundational SCAFFOLD algorithm, which effectively cuts uplink communication expenses by half. This lays a more straightforward foundation for integrating communication compression.\n- The SCALLION algorithm is introduced, leveraging the new SCAFFOLD formulation combined with unbiased compressors.\n- The SCAFCOM algorithm is developed to facilitate biased compressors in Federated Learning via local momentum. Convergence analysis for standard contractive compressors is provided.\n- It is demonstrated that both SCALLION and SCAFCOM either match or surpass the communication and computation complexities of current compressed FL baselines.\n- Through experiments, it's evident that SCALLION and SCAFCOM deliver performance akin to full-precision techniques, boasting compression savings exceeding 100x.", "questions": "There are several questions related to the prof of the Theorem 3:\n1) (Page 25) Could authors please clarify why this inequality holds?\n\n$$9 e^2 K^2 \\eta_l^2 L^2\\left(24+\\frac{4(1+\\omega) \\alpha^2}{S}+\\frac{522(1+\\omega) \\alpha}{N}\\right) \\leq \\frac{\\alpha(1+\\omega)}{N} \\leq \\frac{1}{4}$$\n\n2) Why does this property hold?\n$$\\| {x^0 - x^1}\\|=0$$\n\n## Conclusion\nI would happily give this paper a higher grade for its theoretical contributions and reliable experiments. However, at this moment, I can not do so since the paper still contains things that need to be clarified. I am ready to reconsider my current rate during rebuttals once you respond to me on Weaknesses and Questions.\n\n## Update after the author's rebuttal\nI increased the score.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "- The writing of the paper is clear, the main claims are outlined, and the text is easily read;\n- Literature review is solid and contains relevant papers on the topic;\n- Proposed novel FL algorithms, SCALLION and SCAFCOM, are provably shown to be robust to heterogeneous data and partial participation and require only standard assumptions to establish first-order stationary point guarantees;\n- SCALLION attains superior convergence guarantees compared to prior compressed FL methods with unbiased compression under minimal assumptions;\n- Local momentum in SCAFCOM overcomes the adverse effects of biased compression. SCAFCOM improves communication complexity by a factor of 1/(1-q) over the prior art;\n- Both SCALLION and SCAFCOM exhibit robustness to heterogeneous data and partial participation, unlike existing approaches;\n- The paper provides a principled way to integrate communication compression into federated learning through the new SCAFFOLD formulation;\n- Algorithms are simple to implement and empirically achieve significant compression savings.", "weaknesses": "1) Some potentially relevant papers are missing in the references. See \"Suggestions\" below. \n\n## Typos:\n1) In the RELATED WORK section, instead of \"TurnGrad\" it should be \"TernGrad\".\n\n## Suggestions:\nI would recommend authors to reconsider some of the phrases that they wrote, in particular\n\n>>Can we design FL approaches that accommodate arbitrary data heterogeneity, local updates, and partial participation, as well as support communication compression?\n>>\n>>In the literature, none of the existing algorithms have successfully achieved this goal, to the best of our knowledge.\n\nTo the best of my knowledge, this is true, but for the general class of non-convex loss functions. However, this is not true for strongly convex functions. There are already some works [1, 2, 3, 4] on that topic, providing a provably beneficial combination of compression, partial participation, and local updates.\n\n[1] Grudzień, M., Malinovsky, G., & Richtárik, P. (2023). Improving Accelerated Federated Learning with Compression and Importance Sampling. _arXiv preprint arXiv:2306.03240_.\n\n[2] Youn, Y., Kumar, B., & Abernethy, J. (2022, October). Accelerated Federated Optimization with Quantization. In _Workshop on Federated Learning: Recent Advances and New Challenges (in Conjunction with NeurIPS 2022)_.\n\n[3] Condat, L., Malinovsky, G., & Richtárik, P. (2023). TAMUNA: Accelerated federated learning with local training and partial participation. _arXiv preprint arXiv:2302.09832_.\n\n[4] Sadiev, A., Malinovsky, G., Gorbunov, E.A., Sokolov, I., Khaled, A., Burlachenko, K., & Richt'arik, P. (2022). Federated Optimization Algorithms with Random Reshuffling and Gradient Compression. _ArXiv, abs/2206.07021_.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)