QuAFL: Federated Averaging Made Asynchronous and Communication-Efficient
Authors: Hossein Zakerinia
Shayan Talaei
Giorgi Nadiradze
Dan Alistarh
Venue: Submitted to ICLR 2023 (2023)
Keywords: Federated Learning
Distributed optimization
Load Balancing

Abstract: Federated Learning (FL) is an emerging paradigm to enable the large-scale distributed training of machine learning models, while still providing privacy guarantees. 
  In this work, we address two of the main practical challenges when scaling federated optimization to large node counts: the need for tight synchronization between the central authority and individual computing nodes, and the large communication cost of transmissions between the central server and clients. 
  Specifically, we present a new variant of the classic federated averaging (FedAvg) algorithm, which supports both asynchronous communication and communication compression. We provide a new analysis technique showing that, in spite of these system relaxations, our algorithm can provide similar convergence to FedAvg in some parameter regimes.
  On the experimental side, we show that our algorithm ensures fast  convergence for standard federated tasks. 

QUAFL: FEDERATED AVERAGING MADE ASYNCHRONOUS AND COMMUNICATION-EFFICINNT
Anonymous authors
Paper under double-bling review
ABSTRACT
Federated Learning (FL) is an emerging paradigm to enable the large-scale dis- tributed training of machine learning models, while still allowing individual nodes to maintain local data. In this work, we take steps towards addressing two of the main practical challenges when scaling federated optimization to large node counts: the need for tight synchronization between the central authority and individual computing nodes, and the large communication cost of transmissions between the central server and clients. Specifically, we present a new variant of the classic federated averaging (FedAvg) algorithm, which supports both asynchronous com- munication and communication compression. We provide a new analysis technique showing that, in spite of these system relaxations, our algorithm can provide similar convergence to FedAvg in some parameter regimes. On the experimental side, we show that our algorithm ensures fast convergence for standard federated tasks.
INTRODUCTION
Federated learning (FL) (Konečný et al., 2016; McMahan et al., 2017) is paradigm for large-scale distributed learning, which multiple clients, orchestrated by a central authority, cooperate to jointly optimize machine learning model given their local data. The key promise is to enable joint training over distributed client data, often located on end devices which are computationally- and communication-liminn without the data leaving the client device.
The basic optimization algorithm underlying the learning process is known as federated averaging (FedAvg) (McMahan et al., 2017), and works roughly by having central authority periodically communicate a shared model to all clients; then, the clients optimize this model locally based on their data, and communicate the resulting models to a central authority, which incorporates these models, often via some form of averaging, after which it initiates the next iteration. This algorithmic blueprint has been shown to be effective in practice (Li et al., 2020), and has also motivated a rich line of research analyzing its convergence properties (Stich, 2018; Haddadpour & Mahdavi, 2019), as well as proposing improved variants (Reddi et al., 2020; Karimireddy et al., 2020; Li & Richtárik, 2021).
Scaling federated learning runs into a number of practical challenges (Kairouz et al., 2021). One natural bottleneck is synchronization between the server and the clients: as practical deployments may contain thousands of nodes, it is infeasible for the central server to orchestrate synchronous rounds among all participants. A simple mitigating approach is node sampling, e.g. (Smith et al., 2017; Bonawitz et al., 2019); another, more general one is asynchronous communication, e-g. (Wu et al., 2020; Nguyen et al., 2022b), by which the server and the nodes may work with inconsistent versions of the shared model. An orthogonal scalability barrier is the high communication cost of transmitting parameter updates (Kairouz et al., 2021), which may overwhelm communication-lina clients. Several communication-compe comppeesioonnooooooeiiioooooo approaches have been proposed to address this (Jin et al., 2020; Jhunjhunwala et al., 2021; Li & Richtárik, 2021; Wang et al., 2022).
reasonable to assume that both these bottlenecks would need to be mitigated in practice: for may not be as effective if the server has to wait for each of
instance, communication-reducce the clients to complete their local steps on version of the model; yet, synchrony is assumed by most references with compressed communication. Yet, removing synchrony completely may lead to divergence, given that local data is usually heterogenous. Thus, it is interesting to ask if asynchrony and communication compression, and heterogenous local data, can be jointly supported.
Contribution. In this paper, we address this by proposing an algorithm for Quantized Asynchronous Federated Learning called QuAFL. which is an extension of FedAvg, specifically-adapte to support both asynchronous communication and communication compression. We provide theoretical analysis of the algorithm's 's convergence under compressed and asynchronous communication, and experimental results up 300 nodes showing that it can also lead practical performance gains.

---

Overview. The main idea behind QuAFL is that we allow clients to perform their local steps independently of the round structure implemented by the server, and on local, inconsistent version of the parameters, assuming a probabilistic scheduling model. Specifically, all clients receive a copy of the model when joining the computation, and start performing at most K 2 1 optimization steps on it based on their local data. Independently, in each "logical round," the server samples set of clients uniformly at random, and sends them a compressed copy of its current model.
Whenever receiving the server's message, clients immediately respond with compressed version of their current model, which may still be in the middle of the local optimization process, and therefore may not include recent server updates, nor the totality of the K local optimization steps. In fact, we even allow that, with some probability, some contacted clients do not take any steps at all. Clients carefully integrate the received server model into their next local iteration, while the server does the same with the client models it receives.
The key missing piece regards quantization. Directly applying standard compressors transmitted updates (Alistarh et al., 7b; Karimireddy et al., 2019) runs into the issue that the quantization error may be too large, as it is proportional to the norm of the (updated) model at the client. Resolving this analytically would require either an unrealistic recond-moment bound on the maximum gradient update, e.g. (Chen et al., 2021), or variance-reduction techniques (Gorbunov et al., 2021), which may be complex in practice. We circumvent this issue differently, by leveraging a lattice-based quantizer (Davies et al., 2021), which has the property that the quantization error only depends on the difference between the quantized model and a carefully-chosen "reference point." " We instantiate this technique for the first time in the federated setting.
Our analysis technique relies on new potential argument, which shows that the discrepancy between the client and server models is always bounded. This bound serves to control the "noise" at different steps due to model inconsistency, but also to ensure that the local models are consistent enough to allow correct encoding and decoding via lattice quantization. The technique is complex yet modular, and should allow further analysis of more complex algorithmic variants.
We validate our algorithm experimentally in the rigorous LEAF (Caldas et al., 2018) environment, on series of standard tasks. Specifically, in practice, QuAFL can compress updates by more than 3x without significant loss of convergence, and can withstand a large constant fraction of "slow" clients submitting infrequent updates. Moreover, setting where client computation speeds are heterogenous, QuAFL provides end-to-end speedup, since the server can progress without waiting for all clients complete their local computation.
2 RELATED WORK
The federated averaging (FedAvg) algorithm was introduced by McMahan et al. (2017), and Stich (2018) was among the first to consider its convergence rate in the homogeneous data setting. Here, we investigate whether one can can jointly eliminate two of the main scalability bottlenecks of this algorithm, the synchrony between the server and client iterations, as well as the necessity of full-precision communication, with heterogeneous data distributions. Due to space constraints, we focus on prior work which seeks to mitigate these two constraints in the context of FI..
There significant research into communication commuuiccationncmmpesiiion for FedAvg (Philippenko & Dieuleveut, 2020; Reisizadeh et al., 2020: Jin et al., 2020: Haddadpour et al., 2021). However, virtually all of this work considers synchronous iterations. Reisizadeh et al. (2020) introduced FedPAQ, a variant of FedAvg which supports quantized communication via standard compressors, and provides strong convergence bounds, under the strong assumption of i.i.d. client data. Jin al. (2020) examines the viability of a variant of the signSGD quantizer (Seide et al., 2014; Karimireddy et al., 2019) in the context of FedAvg, providing convergence guarantees; however, the rate guarantees have a polynomial dependence in the model dimension d, rendering them less practically meaningful. Haddadpour al. (2021) proposed FedCOM, family of federated optimization algorithms with communication- compression and convergence rates; yet, we note that, in order to prove convergence in the challenging heterogeneous-data setting, this reference requires non-trivial technical assumptions on the quantized gradients (Haddadpour et al., 2021, Assumption 5). Chen et al. (2021) also considered update compression, but under convex losses, coupled with rather strong recond-moment bound assumption on the gradients. Finally, Jhunjhunwala et al. (2021) examine adapting the degree of compression during the execution, proving convergence bounds for their scheme, under the non-standard i.i.d. data sampling assumption.
2

---

We observe that each of these references requires at least non-standard assumption for the convergence FedAvg with compression. By contrast, our analysis works for general (non-convex) losses, under standard non-i.id. data distribution, without relying on second-moment bounds on the gradients.
A complementary approach reducing communication cost in FL has been to investigate optimizers with faster convergence, e.g. (Mishchenko et al., 2019; Karimireddy et al., 2020), or adaptive optimizers (Reddi et al., 2020; Tong et al., 2020). Tecent work has shown that these approaches can be compatible with communication-compesses et al., 2022). Specifically, for non-convex losses, MARINA Gorbunov et al. (2021) offers theoretical guarantees both in terms of convergence and bits transmitted. However, MARINA is structured in synchronous rounds; moreover, it periodically (with some probability) has clients compute full gradients and transmit uncompressed model updates, and requires complex synchronization and variance-reduction to compensate for the extra noise due to quantization. Tyurin & Richtárik (2022) proposed family of theoretical methods called DASHA, which combines the general structure of MARINA with Momentum Variance Reduction (MVR) methods (Cutkosky & Orabona, 2019), partially relaxing the coupling between the server and the workers and allowing compressed updates.
(Gorbunov et al., 2021; Li & Richtárik, 2021; Wang
In contrast to these works, we focus on obtaining a practical algorithm with good convergence bounds: we always transmit compressed, low-precision messages, and consider a notion of asynchronous communication which allows the server and nodes to make progress independently, in non-blocking fashion. We focus on the classic, practical FedAvg algorithm, although our general algorithmic and analytic approach should generalize to more complex notions of local optimization.
Our approach extends ideas from the analysis of decentralized variants of SGD (Lian et al., 2017; Tang et al., 2018; Nadiradze et al., 2021; Koloskova et al., 2019; Lu & De Sa, 2020), bringing them into the context of federated optimization. Significant differences exist: notably, we introduce a novel potential argument, adapted to FL, and cannot rely on stronger assumptions available in the decentralized setting, e.g. a gradient second-moment bound (Lu & De Sa, 2020).
The concurrent work of Koloskova et al. (2022) provided sharper convergence bounds for asyn- chronous SGD in model that is related to ours. Specifically, this reference considers a setting with worst-case and average delay bounds on asynchrony, and proves convergence rates that are similar to ours in the case of a single sampled client time s. By contrast, our work considers different probabilistic model on the delays, related to that of Cannelli et al. (2020) in which the worst-case delay may be unbounded. In addition, we allow the clients be interrupted by the server during their local computation, which may lead to practical improvements in terms of waiting times and load-balancing. At the technical level, the two analysis techniques are different: in particular, their technique does not require a lower bound on the number of SGD steps w.r.t. the number of nodes n.
THE ALGORITHM
3.1
SYSTEM OVERVIEW
System Model. We assume distributed system with one coordinator and n workers, jointly minimizing a d-dimensional, differentiable function f Rd + RR We consider the empirical risk minimization (ERM) setting, in which data samples are located at the n nodes. Each agent has a local function fa associated to its own local fraction of the data, i.e Vr E Rdd f(x) Σ fi fz The goal is to converge on model x" which minimizes the empirical loss. Clients run a distributed variant of SGD, coordinated by the central node. We will assume that each client i is able to obtain unbiased stochastic gradients 9: of its own local function ft, i.e. (lg:()) = V (zx) These stochastic gradients can be computed by each agent by sampling i.i.d. from its own local distribution. Our analysis will consider the case where each client distribution is distinct, but there is a bound on the maximum gradient discrepancy.
We model client asynchrony as follows: between two consecutive interactions with the server, each client should perform number of gradient steps on its local model. We treat the number of local steps at client as a random variable H4, taking values in (0. 1, ...... K}, where K is bound on how many steps client can take in isolation. We emphasize the fact that H, can take the value 0. meaning that the client may take no steps since last contacted. Our only assumption regarding asynchrony is that the expected value of H. denoted by H, exists and is >> O. That is, we assume that, on average, each client makes non-zero progress, and clients progress at similar rates, although the individual step distributions Hi can be completely different.
3

---

3.2 ALGORITHM DESCRIPTION
Overview. Our algorithm starts from the standard pattern used by federated averaging (FedAvg): computation and communication are organized in logical "rounds," where in each round the server transmits its current version of the model to either all, or subset of clients. The clients should then take some number of local optimization steps the received model, which is at most K 2 and transmit the result to the server, which integrates these updates. Our algorithm will relax this pattern in two orthogonal ways, allowing for both quantized and asynchronous communication.
Quantized Communication. The first relaxation is to only allow for compressed communication of the server model and of the client updates, via quantization. For this, we employ carefully- parametrized version of the lattice-based quantization technique of Davies et al. (2021), whose analytical properties describe in the analysis section. For practical purposes, this quantization technique presents an encoding function Enc( A), which encodes an arbitrary input A to its quantized representation. (We always communicate vectors via their quantized representations.) To "read" an encoded message Enc(A), a node must call the symmetric Dec( B, Enc(A)) function, which allows for the "decoding" of the input Enc(.A) (A)) with respect to reference point B, returning quantized output ((A). We formally specify the properties the compression process in Section 4.
Algorithm 1 Pseudocode for QuAFL Algorithm.
% Initial models Xo = X X2 = X = 04, number of local steps K
Encoding (Enc(AA) and decoding (Dec(B, Enc(A))) functions, with common parametrization.
% At the Server:
for = 0 to do
2: Server chooses s clients uniformly at random, let S be the resulting set.
3:
for all clients E S do
4:
Server sends Enc(Xe) to the client é.
5:
Server receives Eno(Y") from client i
6:
% Y = X 1phh the client's progress since last contacted Q(Y') t- Dec(X1; Ene(Y")) % Decodes client messages relative to X
7:
8: end for
9: Xx41 X + #+I Eies Q(Y")
end for
At Client
% Upon (asynchronous) contact from the server run INTERACTWITIISERN
Local variables:
% X stores the base client model, following the last server interaction. Initially 0d.
% h2 accumulates local gradient steps since last server interaction, initially 0d.
1: function INTERACTWITISSEER
2: MSG. +- X'c(X' X 1ph.) % Client compresses its local progress since last contacted.
3: Client sends M SG, the server.
4:
Client receives Emc{X X.) from the server, where the current server time.
5: Q(X,) t- Dec(X*, Frn((x)) % Client decodes the message using its old model reference point.
6:
% The client then updates its local model
7:
X = + -4T (X' -nphs)
8: &Finally, it performs K new local steps on the updated X unless interrupted again.
9: LOCALUPDATES(X! WAIT() )
11: end function
1: function LOCAL UPDATESPAAT,SXX K)
2:
h, 0 %% local gradient accumulator
3: for to K
do
4: h. ÿ (X'
-i=1i k()) % compute the ęth local gradient
5:
h; h4 + ng % add it to the accumulator
6:
end for end function
7:
Asynchronous Communication. A key practical limitation of the FedAvg pattern is that the server and its workers have communicate in synchronous, lock-step fashion: thus, the server must wait for the results of computation at a round before it can move to the next round. In particular, this means that the server has to wait for the slowest client to complete its local steps before it can proceed. 4

---

QuAFL relaxes this requirement by essentially allowing any contacted node to immediately return (a quantized version of) its current version of the model to the server upon being contacted, even though the client might still not have completed all its K local optimization steps for the round. More precisely, the client always records "base" model at the end of the last interaction with the server into parameter X and sums up its gradient updates since the last interaction into the buffer h;. Upon being contacted, the client simply sends its current progress Y = X .//; to the server (excluding the local step for which computation was not finished due to interruption from the server). where rj is the learning rate, in quantized form. It is possible that this progress is zero. The client then decodes the quantized server model Xr, using its old local model X' as the decoding key. Finally, the client updates X to include the server's 's new information via weighted averaging. is then ready to restart its local update loop, upon this new model.
It is important to notice that the server interaction occurs asynchronously, and that it might occur either while the client still performing local steps, or after the client has completed its K local steps, and is idle, waiting for server contact. In the former case, upon being contacted, immediately calls the server interaction function, without performing additional steps. (In particular, we allow the number of completed local steps to be 0.) Globally, the server contacts s random agents in each logical round, sends them quantized version of the global model X,, then receives quantized versions of their progress, and then incorporates this into the global model which will be sent at the next round.
Discussion. The practical advantage of QuAFL is that the server does not have wait for each of the contacted clients to complete their local optimization on the global model X,. In addition, an important departure from FedAvg is the averaging between the server and client models. Our formulation is important for fast convergence: as we show in Figure 4, other forms, such as just adopting the client average, lead to worse convergence.
CONVERGENCE ANALYSIS
4.1 ANALYTICAL ASSUMPTIONS
We begin by stating the assumptions make in the theoretical analysis of our algorithm. Specifically, we assume the following for the global loss function f. the individual client losses fi, and the stochastic gradients Dj
1. Uniform Lower Bound: There exists f. E R such that f(x) 2 f. for all a E Rd.
2. Smooth Gradients: For any client i, the gradient V fx) is L-Lipschitz continuous for some L > 0, i.e. for all v, y E RRd:
[V f((ill s L|| - -/|-
(1)
3. Bounded Variance: For any client i, the variance of the stochastic gradients is bounded by some o² > i.c. for all x E Rdd
o (z) (x) 0²
(2)
4. Bounded Dissimilarity: There exist constants G2 2 and B² 2 1, s.t. Vo E Rd:
S B² (F
7
The first three conditions are universal in distributed non-convex stochastic optimization, whereas the fourth encodes the fact that there must be bound the amount of divergence between the local distributions at the nodes in order to allow for joint optimization (Karimireddy et al., 2020; Jin et al., 2020; Gorbunov al., 2021).
In addition, we make the following assumption on the local progress performed by each node:
5. Probabilistic Progress: The expected number local steps taken by a client when contacted by the server is H > 0.
Quantization Procedure. Please recall the semantics of our quantization procedure from Section 3.2. In this context, the quantizer has the following guarantees (Davies al., 2021) (Lemma 23):
Lemma 4.1. (Lattice Quantization) Fix parameters R and > 0. There exists a quantization procedure defined by an encoding function EncR, Id {0, 1), and decoding function DecR, Rdd {0, 13" -> Rdd such that, for any vector E IRd which are trying quantize, and 5

---

any vector y which is used by decoding, which we call the decoding key, if 1| yl1 S RR², then with probability at least 1 - log log( ||= J0 4), the function QR (x) = DECR, (v, EneR, (x)) has the following properties:
1. (Unbiased decoding) EIQRR (x)) EEDDCRR EncR, x;
2. (Error bound) [[Q - x S (R² 777;
3. (Communication bound) O (dlox( R wll) bits are needed to send EncR, (t).
4.2 MAIN RESULTS
Roughly, our aim is to show that our algorithm, local models of the clients stay close to the local model of the server, so that models are consistent, and we can successfully apply the quantizer. Let
H4 = (X, + Ei= X + 1) be the mean over all the node models in the system at given Our main result shows the following:
Theorem 4.2. Assume the total number of server steps T 2 [2(n2)). ,. the learning rate rj = n+l and x quantization parameters R 2 + T and -2 (र' (0² (0² + 2KG =(mm)) Let H 0 be the expected number of local steps already performed by a client when interacting with the server. Then, with probability at least ( we have that Algorithm I converges at the following rate
sH TT
BIV)())) & 5(((m)) - f.) + SKL(02 + +2KG -0 1=0
TE (o'' 22
VT
H2VT
sH3T
and uses O (d + log T)) expected communication bits in total.
Discussion. The result provides a trade-off between the convergence speed of the algorithm, the variance of the local distributions (given by and G), the sampling set size and the average number of local steps H performed by a node when contacted by the server.
For constant 8, H and K, this bound appears to be term contains similar "nuisance factors" as the second term, with the addition of the n factor, and also bounds the extra variance. Crucially, this larger term is divided by T, as opposed to vT; since T our asymptotic parameter, it common to assume that this extra term becomes negligible as T is large, e.g. (Lu & De Sa, 2020).
Specifically, the third
However, for super-constant s = wn)), there is no tangible benefit due to sampling over s clients. Intuitively, this is because of asynchrony: each client gets sampled on average every n/s steps, and therefore will work on "stale" copy of the model that is n/s rounds old, which affects convergence speed. While this is a limitation of the analysis, from the practical perspective, this can be addressed by observing that, due to asynchrony, in terms of wall-clock time, we can think of the s interaction steps between the server and the clients as happening in parallel. Thus, again, in terms of wall-clock- time, it is reasonable to perform the substitution T - sT in the above rate calculation, which indeed suggests that our algorithm is able to obtain speedup with respect to the number of sampled clients 8.
In practice, it should be reasonable assume that = + ()), that is, that on average each client i will have completed its local steps on the old version of the model X' when being contacted:
otherwise, the sampling frequency of the server too high, and prevents clients from making progress on their local optimization, and the server should simply decrease it.
Convergence at the Server. Finally, we show that not only convergence at the server, as opposed to the convergence of the mean of the local models as in Theorem 4.2. We get that:
Corollary 4.3. Assume the total number of steps T 2 2(( the learning rate 1j = n+1 /T
and
quantization parameters R = 2 à and 72 = सहेंगर (o² 2KG2 + flma)=t)) Let H 0 be the expected number of local steps already performed by client when interacting with the server. Then, with probability at least O(+) we have that Algorithm converges at the following rate
BI 5(f(m)) VT
-.)) f.) + 8KL(02 + 2KG
72" KI? +
* 2KG2)
+0
HVVT
sH2T
This corollary yields a very similar bound to our main result, except for the larger dependency between T and n, which is intuitively required due to the additional time required for the server to converge

---

to similar bound to the mean f4M The third term may be significant for large number of nodes n; however, since it is divided by I (as opposed to vT) it can be seen negligible for moderate and large T. The fact that QuAFL can match some of the best known rates for FedAvg under some parameter settings may seem surprising, since our algorithm is asynchronous (in particular, nodes take steps on local, delayed versions of the server model) and also supports
4.3 OVERVIEW OF THE ANALYSIS
The complete analysis is fairly complex, and is provided in full in the Appendix. Due to space constraints, we only provide an overview of the proofs, outlining the main intermediate results. The first step in the proof bounding the deviation between the local models and their mean. For this, we ue 112 and we use a load-balancing approach to show that this potential has the following supermartingale-yy property:
introduce the potential function & | 14 1ell" - ||
Lemma 4.4. For any time step t we have:
[[ S (1 (1-11
E E| + 887)
E Eliha 16m( R2 + 7)
4n
The intuition behind this result is that potential D will stay well-concentrated around its mean, except for influences from the variance due local steps (second term) or quantization (third term). With this in place, the next lemma allows us to track the evolution of the average of the local models, with respect to local step and quantization variance:
Lemma 4.5. For any step
21 2 n(n + 1)3
2
B Bllp++1 Mell S
Σ
h4
(n + 1)3 (R² + +7)272.
In both cases, the upper bound depends on the second moment of the nodes' local progress E, (This is due to the fact that the server contacts s clients, which are chosen uniformly at random.) Then. our main technical lemma uses properties (1), (2) and (3), to concentrate Σ, T (x;) around the true gradient E// (wu) where the expectation is taken over the algorithm's 's randomness.
IE hg
Lemma 4.6. For any step I, we have that
Σ EBITU < 2n + +
+ 4nk Vf(p))
We can then combine Lemmas 4.4 and 4.6 to get an upper bound on the potential with respect to E|| ((u)) Summing over steps, we obtain the following:
Lemma 4.7.
E[0,] < 80 -0 (20 SK2
E V (2.))
Next, using the I-ssmoothness of the function f. implied by (1), we can show that
T.
B[f(μ++1) B[f())) + (VV
me) E BBlleet mell
Final argument. Using the above inequality, and given that E[pc+1 - mc] = - Eies (x;)).
we observe that the sum Σn= E(V [ #4+1 - pe) can be concentrated around E similar fashion as in Lemma 4.6. Together with Lemma 4.5, this results in the following bound:
f in
B[f()++)) - B[f(u)] < [T
2T
)02 2KG2
n(n + 1)
n+1
(n 1)2
(R² + 2
-3sll
8B2
3B²
(n + 112
4(n +
n n+1
(n+
7

---

08
2 1a CEUaii
4.3
04
Figure 1: Peers & E [10, 20, 30, 40) on convergence, 100 clients, 14-bit quantization, on ColebA.
Figure 2: Impact of the number bits b 10, 12, 32) convergence, T 10 clicnts, e 5 poors on MNIST.
Figure 3: Convergence compurison rela- tive simulated time between QuAFI. and FodAvg, for ResNo20CCIPARI0
Ten buch (11,1 Segp 10 1:0 de
230
320
214
Nowe aaceely Delt aed Meri
380
26
0302
(100
18613
Figure Impact of aavernging variants
Figure Using QSGD vs quanti-
Figure Convergence QuAFL SOTA asynchronous Fl. algorihhm FedBuff.
validation accuracy on ColebA, ve. munds.
zation in QuAFI, on MNIST.
For v = (n + 1)/VT, as stated in the Theorem, we can use Lemma 4.7 to cancel out the terms containing the potential 4 (after summing up the inequality over 7 steps). Replacing these terms, and modulo some additional term wrangling, we obtain the claimed convergence bound.
Quantization Impact. Finally, we address the correctness of the quantization technique. We show that the quantization fails with negligible probability:
Lemma 4.8. Let 2 (2(m²), then for quantization parameters R = 2 T and mn2 = (R2247y2 (a² 2KG + -- we have that the probability of quantization never failing during the entire run of the Algorithm 1 is at least -
Per Lemma 4.1, in order for the communication to fail with negligible probability, we need to show that whenever the server communicates with a client, the two norm of their local models is at most R 7. Hence, we need to use bound [t]. The only similar use of this technique was in Nadiradze et al. (2021): I): however, the authors of this reference could benefit from assuming that of the gradients was bounded. Since we make no such assumption here, we need to find a way to bound o E V (l, Fortunately, our main result shows that the gradients are vanishing,
the second-momen
can take the advantage of the convergence rate and plug it back into Lemma 4.7.
Similarly, due to the Property 3, Lemma 1. the number of the bits used by our algorithm, in one communication between the server and client, depends on the two norm of the distance between their local models. Thus, we can use the bound on Ei- B f (1+) to show the following.
Lemma 4.9, Let 2 Si(n)), then for quantization parameters 2 - T and -R² (o²
2KG² + f(mo)=I=) ) we have that the expected number of bits used by Algorithm 1 in total is (ss((dlog(m) + log(T)).
We note that the communication cost per step is also asymptotically optimal, modulo the multiplicative log n and additive log T terms, required to ensure error probability 1 O(1/T).
EXPERIMENTAL RESULTS
Experimental Setup and Goals. We implemented our algorithm in Pytorch in order to train neural networks for image classification tasks. specifically residual CNNS (He et al., 2016) on the MNIST (LeCun & Cortes, 2010), Fashion MNIST (Xiao et al., 2017), CIFAR-10 (Krizhevsky & Hinton, 2009) and CelebA (Liu et al., 2015) datasets, the rigorous FL. setup of LEAF (Caldas et al., 2018). Details presented in the Appendix. We aim validate our analysis relative to the impact of various parameters. We omit error bars, as we observed that the variance is very low.
Specifically,, the parameters we examine n, 8, and K, which have the same meaning in our theoretical analysis. Our experiments are described by (ni, 8, K. b), where is the number of bits for quantization. In addition, we define swet the server waiting time between consecutive
8

---

calls, and the server interaction time, sit, as the amount of time that server needs to send and receive necessary data, We assume a server and n clients. The training dataset is distributed among clients so that each has access to fixed 1/n partition of the training data. We track the accuracy of the server's s model on an unseen validation dataset. We measure loss and accuracy of the model with respect to simulation time and total gradient steps performed by clients. In each round, the server chooses clients uniformly at random. then sends its model to those clients and receives their current local models. Each client will have taken maximum of K local steps by the time it is contacted by the server. We update the both client and server models following QuAFL, and then increase the server time by sit. The server then waits for another interval of server waiting time (swt) to make its next call. Unless otherwise stated, communication is compressed.
We differentiate between two types of timing experiments: uniform timing experiments assume all clients take the same amount of time for a gradient step; non-uniform timing experiments differentiate clients to be fast or slow. Specifically, the length of each client step is taken to be a random variable X exp(A), where À is 1/2 for fast clients and 1/8 for slow clients; the expected runtime E(X) would be 2 and 8, respectively. In each experiment, we assumed 30% of clients to be slow.
Figure 1 examines the impact of the number of sampled peers 8 when training ResNet18 on the CelebA dataset, where 30% of clients are slow. We first observe that convergence speed clearly follows the ordering of the number of peers 8, confirming our analysis. Interestingly, timings in this experiment are set up so that there is a 27% probability that slow client will not have taken any steps when interacting with the server. (This probability decreases as s increases.). Thus, this experiment also shows that QuAFL is indeed robust to such slow clients, although their proportion can impact convergence. Figure examines the impact of the number of quantization bits b, showing that increasing b from 8 to 10 improves convergence; however, there is clear staturation after 10 bits.
In Figure 3 we examine the loss convergence of FedAvg and QuAFL versus simulated execution time, in a system with 20 clients, out of which 25% are slow. (The Baseline is a single slow node that performs an optimization step per round.) Here, it is evident that QuAFL asynchrony allows it to provide a faster convergence in terms of wall-clock time, than its synchronous counterparts.
In Figure 4, we examine the impact of different types of averaging on the convergence of the basic QuAFL pattern, on the CelebA dataset, with n = 100 clients. All variants execute in the same setup, with individually-tuner is applied both at the server and at the client performs the best, which validates our choices. In Figure 5, we compare the convergence of QuAFL with the lattice quantizer, relative to QuAFL using the standard QSGD quantizer (Alistarh et al., 2017a), We note that using QSGD is not theoretically- justified, and in fact we had perform careful tuning in order to obtain stable convergence for this variant. It is interesting that QuAFL. appears to support this, albeit at the cost of slower convergence.
We clearly observe that the variant where averaging
Finally, in Figure 6, we compare QuAFL convergence relative FedBuff. a tfate-of-the-art asyn- chronous FL protocol (Nguyen et al., 2022a), which performs buffering of client messages at the server, updating the server model as soon as s messages, with K local updates each, are in the server buffer. Since the timing model of FedBuff is different, we compare convergence in terms of total number of gradient steps taken by clients, without quantization. We observe that QuAFL. converges faster: our analysis suggests that this is because QuAFL. takes into account partial progress by slow clients, whereas in FedBuff slow clients constantly contribute less significantly to the server updates. We present additional experimental results in the Appendix, specifically on higher node counts (up to 300), full-convergence experiments, as well as across all other tasks.
CONCLUSIONS AND LIMITATIONS
We have provided the first variant of FedAvg which incorporates both asynchronous and compressed communication, and have shown that this algorithm can still provide good convergence guarantees. Our analysis should be extensible to more complex federated optimizers, such as gradient tracking, e.g. (Haddadpour et al., 2021), controlled averaging (Karimireddy et al., 2020), or variance-reduced variants (Gorbunov et al., 2021). Our work has the following limitations. First, our algorithm has an optimal convergence rate when H- = @(K), which we believe is natural due to asynchrony. Second, this version of the analysis requires the expected number of local steps H to be the same across all devices. We believe that this can be addressed either by modifying the objective, or by de- de-biasing via sampling, and plan to investigate it in future work, together with validation on real-world deployments.
9

---

7 REPRODUCIBILITY STATEMENT
All the code required to reproduce our experimental setup and our experiments is available at https:/ /aap:s////ommmuss..mmm 4open. sci /
REFERENCES
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. QSGD: Randomized quantization for communication-cffiiiii stochastic gradient descent. In Proceedings of NIPS 20/7, 201
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. QSGD: Communication- efficient sgd via gradient quantization and encoding. In NIPS, pp. 1709-1720, 2017b.
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi, Brendan McMahan, et al. Towards federated learning at scale: System design. Proceedings of Machine Leurning and Systems, 1: 374-388, 2019.
Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, H Brendan McMa- han, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv:/812.01097, 2018.
Loris Cannelli, Francisco Facchinei, Vyacheslav Kungurtsev, and Gesualdo Scutari. Asynchronous parallel algorithms for nonconvex optimization. Mathematical Programming, 184(1):121-154, 2020.
Mingzhe Chen, Nir Shlezinger, H Vincent Poor, Yonina C Eldar, and Shuguang Cui. Communication- efficient federated learning. Proceedings of the National Academy of Sciences, 118(17), 2021.
Ashok Cutkosky and Francesco Orabona. Momentum- variance reduction in non-convex sgd. Advances in neural information processing systems, 32, 2019.
Peter Davies, Vijaykrishna Gurunanthan, Niusha Moshrefi, Saleh Ashkboos, and Dan Alistarh. New bounds for distributed mean estimation and variance reduction. In International Conference on Learning Representations, 2021.
Eduard Gorbunov, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. MARINA: Faster non- convex distributed learning with compression. In International Conference on Machine Learning. pp. 3788-3798, PMLR, 2021.
Farzin Haddadpour and Mehrdad Mahdavi. On the convergence of local descent methods federated learning. arXiv preprint arXiv: 14425, 2019.
Farzin Haddadpour, Mohammad Mahdi Kamani, Aryan Mokhtari, and Mehrdad Mahdavi. Federated learning with compression: Unified analysis and sharp guarantees. In International Conference on Artificial Intelligence and Statistics, pp. 2350 2350-2358. PMLR, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Divyansh Jhunjhunwala, Advait Gadhikar, Gauri Joshi, and Yonina C Eldar. Adaptive quantization of model updates for communicaioon-eficien federated learning. In ICASSP 2020-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3110-3114, IEEE, 2021.
Richeng Jin, Yufan Huang, Xiaofan He, Huaiyu Dai, and Tianfu Wu. Stochastic-sign SGD for federated learning with theoretical guarantees. arXiv preprint arXiv:2002.10944 2020.
Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Ad- vances and open problems federated learning. Foundations and Trends in Machine Learning, 14(1-2):1-100, 2021.
10

---

Sai Praneeth Karimireddy, Quentin Rebjock, Sebastian Stich, and Martin Jaggi. Error feedback fixes signSGD and other gradient compression schemes, In International Conference on Machine Learning, pp. 3252-3261. PMLR, 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning. In International Conference Machine Learning, pp. 5132-5143, PMLR, 2020.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pp. 3478-3487, PMLR, 2019.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asynchronous sgd for distributed and federated learning. arXiv preprint MKKiv:2206.083007 2022.
Jakub Konečný, Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. Federated learning: Strategies for improving communication efficiency. arXiv preprini wrXvv:/61000549. 2016.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010. URL http://///anm
lecun. com/ exdb /mmist//.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020.
Zhize Li and Peter Richtárik. CANITA: Faster rates for distributed convex optimization with communication compression. Advances in Neural Information Processing Systems, 34, 2021.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jio Hsieh, Wei Zhang, and Ji Liu, Can decentralized algorithms outperform centralized algorithms? gradient descent. arXiv preprint arXiv: 0700009055055 2017.
study for decentralized parallel stochastic
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference Computer Vision (ICCV), December 2015.
Yucheng Lu and Christopher De Sa. Moniqua: Modulo quantized communication in decentralized sgd. In International Conference on Machine Learning, pp. 6415-6425, PMLR, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas communication-eeficceee learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 1273-1282, PMLR, 2017.
Konstantin Mishchenko, Eduard Gorbunov, Martin Takáč, and Peter Richtárik. Distributed learning with compressed gradient differences. arXiv preprint arXiv: 1 1901199999999 2019.
Giorgi Nadiradze, Amirmojtaba Sabour, Peter Davies, Shigang Li, and Dan Alistarh. Asynchronous decentralized sgd with quantized and local updates. Advances in Neural Information Processing
Systems, 34, 2021.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. International Conference on Artificial Intelligence and Statistics, pp. 3301- PMLR, 2022a.
John Nguyen, Kshitiz Malik, Hongyuan Zhan, Ashkan Yousefpour, Mike Rabbat, Mani Malek, and Dzmitry Huba. Federated learning with buffered asynchronous aggregation. In Gustau Camps- Valls, Francisco J. R. Ruiz, and Isabel Valera (cds.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3581-3607. PMLR, 28-30 Mar 2022b. URL https: / /ptpppeieeeeggseeeeeeepeppe mlr. ppwss/vv5. nguyen22b. html.
Constantin Philippenko and Aymeric Dieuleveut, Bidirectional compression in heterogeneous settings for distributed or federated learning with partial participation: tight convergence guarantees. arXiv preprint ar arXiv:2006. 14591, 2020.
11

---

Sashank Reddi, Zachary Charles, Manzil Zaheer. Zachary Garrett, Keith Rush, Jakub Konečný, Sanjiv Kumar, and Brendan McMahan. Adaptive federated optimization. arXiv preprini arXiv:2003.00295, 2020.
Amirhossein Reisizadeh, Aryan Mokhtari, Hamed Hassani, Ali Jadbabaie, and Ramtin Pedarsani. Fedpaq: A communicationn-fficcett federated learning method with periodic averaging and quanti- zation. In International Conference Artificial Intelligence and Statistics, pp. 2021-2031. PMLR, 2020.
Seide, H. Fu, L. G. Jasha, and D. Yu. 1-bit stochastic gradient descent and application to data- parallel distributed training of speech dnns. Interspeech, 2014.
Virginia Smith, Chao-Kai Chiang, Maziar Sanjabi, and Ameet S Talwalkar. Federated multi-task learning. Advances neural information processing systems, 30, 2017.
Sebastian U Stich. Local SGD converges fast and communicates little. arXiv preprint arXiv:1805.09677, 2018.
Hanlin Tang, Ce Zhang, Shaoduo Gan, Tong Zhang, and Ji Liu. Decentralization meets quantization. CoRR, abs/1803.06-443. 2018.
Qianqian Tong, Guannan Liang, and Jinbo Bi. Effective federated adaptive gradient methods with non-iid decentralized data. arXiv preprint arXiv:2009.06557, 2020.
Alexander Tyurin and Peter Richtárik. DASHA: Distributed nonconvex optimization with commu- nication compression, optimal oracle complexity, and no client synchronization. arXiv preprint arXiv:2202.01268, 2022.
Yujia Wang, Lu Lin, and Jinghui Chen. Commuicaaioon-fficiieen adaptive federated learning, arXiv preprint arXiv:2205. 02719, 2022.
Wentai Wu, Ligang Hc, Weiwei Lin, Rui Mao, Carsten Maple, and Stephen Jarvis. Safa: a semi- asynchronous protocol for fast federated learning with low overhead. IEEE Transactions Computers, 7055):655-668, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXin:1008.07747, 2017.
12

---

CONTENTS
1
Introduction
2 Related Work
3
The Algorithm
3.1
System Overview
3.2
Algorithm Description
4
Convergence Analysis
4.1
Analytical Assumptions
4.2
Main Results
4.3
Overview the Analysis
Experimental Results
6
Conclusions and Limitations
7
Reproducibility Statement
10
A Experimental setup
14
A.1
Hyper-parameters
14
A.2 Simulation
14
A.3 Datasets and Models
15
A.4 Results on Fashion MNIST (FMNIST)
15
A.5 Results CIFAR-10
17
B The Complete Analysis
18
B.1
Overview and Notation
18
B.2 Properties of Local Steps
18
B.3 Upper Bounding Potential Functions
20
B.4 Convergence
25
13

---

A EXPERIMENTAL SETUP
In this section, we describe our experimental setup in detail. We begin by defining the hyper- parameters which control the behavior of QuAFL and FedAvg. Then, we proceed by carefully describing the way in which we simulated each the algorithms. Finally, we detail the datasets, tasks, and models used for our experiments.
A. PPPER-PARAMETERS
We first define our hyper-pppaaee parameters; in the later sections, we will examine their impact on algorithm behavior through ablation studies.
n: Number of the clients.
8t Number of clients interacting with the server at each step.
K: In QuAFL, this is the maximum number of allowed local steps by each client between two server calls. In FedAvg, this is the number of local steps performed by each client upon each server call.
b: Number of bits used to send coordinate after quantization.
swl: Server waiting time, i.e. the amount of time that server waits between two consecutive calls.
sit: Server interaction time, i.e. the amount of time that server needs to send and receive necessary data (excluding computation time).
A.2 SIMULATION
We attempt to simulate a realistic FL. deployment scenario, as follows. We assume server and n clients, each of which initially has model copy. The training dataset distributed among the clients so that each of them has access to 1/n of the training data. We track the performance of each algorithm by evaluating the server's model, on an unseen validation dataset. We measure loss and accuracy of the model with respect to simulation time, server steps, and total local steps performed by clients. These setups so far were common between QuAFL and FedAvg. In the following, we are going to describe their specifications and differences.
QuAFL:
Upon each server call, the server chooses s clients uniformly at random. It then sends its model to those clients and asks for their current local models. (Recall that clients send their model immediately to the server.) Each of the clients will have taken a maximum of K local steps by the time it is contacted by the server. The server then replaces its model with carefully-computed average over the received models and its current model. This process increases time on the server by the server interaction time (sit). The server then waits for another interval of server waiting time (swr) to make its next call. The receiving clients replace their model with the weighted average between their current model and the received server's model. Since each client performs local steps from its last interaction time until the current server time, nodes are effectively executing asynchronously. Moreover, note that communication compressed, as all the models get encoded in their source and decoded in their destination.
Quantization: To have a lightweight but efficient communication between clients and the server, we use the well-known lattice quantization (Davies et al., 2021). Using this method, we send instead of 32 bits for each scalar dimension. Informally, each 32-bit number maps to one of the 2 quantized levels and can be sent using b bits only. The encoded number can then be decoded to sufficiently close number at the destination, following the quantization protocol.
FedAvg:
In the beginning of each round, server chooses clients randomly, and sends its current model to them. Each of those clients receives the model, uncompressed, and performs exactly K local steps using this model as the starting point, and then sends back the resulting model to the server. The server then computes the average of the received models and adopts it as its model. By this synchronous structure, in each round, the server must wait for the slowest client to complete its local steps plus an extra sit for the communication time. After completing each round, the server starts the next call immediately, that means swr in FedAvg.
Timing Experiments. We differentiate between two types of timing experiments. Uniform timing experiments, presented in the paper body, assume all clients take the same amount of time for
14

---

2.25
160105 121 DE 10
225
QuArI
(6G46.0,aecce 121 sat 12
QuARL
160,00
intice wet 10
OUIALL (85AA:00,eece s2t
QuAR:
192.10 lotice
O.ARIL
140.30 10..00.
1.75
175
1.52
1.50
1.00
0.75
0.50
Scrver stozt
Vigure 7: Impact of the maximum number of local steps K
Figure 8: Impact of the number of interacting peers
{5, 10, 20} the QuAFL algorithm Fashion MNIST.
{4, 8, } the convergence the algorithm.
30:
2.25
CUAYL (60.0010)atiic 120 ant 1st: 1
2.05
OudEl 16010
2.00
Baoe Ine
1.75
OLARL (62.0 /utiic aet
175
1.50
125
1.30
0.50
0.25
22
50
75
200
122
-20
175
200
407
Figure 9: Impact server contact lrequency (controlled via server timexut swr) on the convergence of the algorithm.
Scrver 3i0ca
Figure 10: Convergence comparisen relative to total number rounds. between QuAFL, FedAvg, and the sequential base- line.
gradient step. However, in real-world setups, different devices may require different amounts of time perform single local step. This is one of the main disadvantages of synchronous federated optimization algorithms. To demonstrate how this fact affects the experiments, in our Non-uniform timing experiments differentiate clients be either fast slow. The length of each local step can be characterized as a memoryless time event. Therefore, the length of each local step can be defined by random variable X ~ ezponential(X); The parameter À is 1/2 for fast clients and 1/8 for slow clients; the expected runtime B(X) would be 2 and 8, respectively, In each timing experiment, we assumed only one fourth of clients to be slow.
A.3 DATASETS AND MODELS
We used Pytorch to manage the training process in our algorithm. We have trained neural networks for image classification tasks on three well-known datasets, MNIST, Fashion MNIST, and CIFAR-10. For all the datasets, we used the default train/test split of the dataset for our training/validation In the following, we describe the model architecture and the training syper-parametess used train on each of these datasets.
validation dataset.
MNIST:
We used SGD optimizer with constant Ir 0.5 in all the training process. We used two-layer MLP architecture with (784,3,,10) nodes in its layers respectively. We used batch size 128 in each client's 's SGD step.
Fashion MNIST: Although this dataset has the same sample size and number of classes as MNIST, obtaining competitive performance on requires more complicated architecture. Therefore. we used a CNN model to train on this model and demonstrated the performance of our algorithm in a non-convex task. To optimize the models, we used Adam optimizer with constant Ir = 0.001 and batch size 100.
CIFAR-10:
To load this dataset, we used data augmentation and normalization. For this task, we trained ResNet20 models. Moreover, the SGD optimizer with constant Ir = 0.03 is used to in the training process. The batch size 64/200 used for training/validation.
A.4 RESULTS ON FASHION MNIST (FMNIST)
We begin by validating our carlier results, presented in the paper body, for the slightly more complex FMNIST dataset, and convolutional model.
In Figures 7 and 8 we examine the impact of the parameters K and 8, respectively, on the total number of interaction rounds the server, to reach certain training loss. As expected, notice
15

---

225
Fec-Ang (60, 30
DuNi: (60, (60.0R,15/atiie 321 SAt 1 125
Base the
2.6
155
1.25
1.00
5.2
0.5
Quelt 190, Metteee 1.125
Bescing
Time
Time
Figure 11: Time vs. accuracy for various algorithm variants. Fashion MNIST
Figure 12: Timing vs. loss for various algorithm variants, Fashion MNIST.
0.5
225
2.00
57
2.8
1.50
125
2.3
0.2
Quint (200, Eojttiic
Fed-tug (100,
0.0
1250
Time
Vigure
accuracy n=300 3=30 peers
Figure
Timing vs. loss n=300 clients, 5=30 peers Fashion MNIST.
on Fashion MNIST
3.82
0.6
135
3.3
(2E. 2.2
02
Podball G20 Saspd 4.3/5
2002
Figure 15: Full convergence result for 20 clients and on F-MNIST. methods oventually reach the soquen- tial ~ 91% top-1 accuracy on this task, but QuAFL is the fastest do temms of wall-clock time.
ads
1500
3200
Figure 16: Validation accuracy for QuAFL with Lattice vs FedBull with QSGD quantization. the bit width. QuAFI. shows significantly hetter convergence.
that higher K and improve the convergence behavior of the algorithm. In Figures 9 we examine the impact of the server waiting time on the convergence of the algorithm relative to the number of server rounds. Again, we notice that higher server waiting time improves convergence, as it allows the server take advantage additional local steps performed at the clients, as predicted by our analysis. (Higher swt means higher average number of steps completed H.)
Next, we examine the convergence, again terms of number of optimization "rounds" the server, between the sequential Baseline, FedAvg, and QuAFL. As expected, the Baseline is faster to converge than FedAvg, which in turn faster than QuAFL in this measure. Specifically, the difference between QuAFL and the other algorithms comes because of the fact that, in our algorithm, nodes operate on old variants of the model at every step. which slows down convergence. Next, we examine convergence in terms of actual time, in the heterogeneous setting in which 25% of the clients are slow.
In Figure 11, we observe the validation accuracy ensured by various algorithms relative to the simulated execution time, whereas in Figure 12 we observe the training loss versus the same metric. (We assume that, in Baseline, a single node acts as both the client and the server, and that this node is slow, i.e. has higher per-step times.) To further support the robustness of our algorithm in regimes with large number of clients, we conducted an experiment with n 300 clients and s = 30 peers interacting with the server each step. The validation accuracy and loss versus time regarding the mentioned experiment plotted in Figure 13 and Figure 14 respectively. We observe that, importantly, if time is taken into account rather than the number of server rounds, QuAFL. can provide notable
16

---

2.5
CUATL (23.3 5.3 intic:: 14: ovt
CUATI 120.11: ladto 12) Bnt S
DuMiL 023.5 iatice avt
17-
220 200.,16,0077 boti set S
QUAYL (22.2.33
wotoon 240 5
OJARL
120.00:0.aetee 121
1.8
120
1.4
1.2
11
Figure 17: Impact of maximum local steps K (3, 9, 15) QuAFL algorithm, on ResNec2uCIF.R-10.
Figure 18: Impact of the number of interacting peers E
{3. 6, 10) the convergence the algorithm.
Oudfi
126,5, 121
19
Outii 1255 F...,5,,mmm 10 rat des
2.5
3.6
QuiFi
OUAPL
220.50/ 281 1
124,5,66ns suanitation 120 eat
17-
18
+
OUAFL 120.5.1, lathon 24) ant Bat:
Guedi 1205,15 antiin 140 eat 12
CuArL 220 20000000 katioo 240 18
2.4
16
8-
3.0
502
230
Figure 19: Impact of the number of bits for quantization
Figure 20: Impact of the server contact frequency (controlled via server timeout rwt) on the convergence of the algorithm.
b E {12, 16, 32] on the convergence of the algorithan.
speedups in these metries. This is specifically because of its asynchronous communication patters, which allow it to complete rounds faster, without having to always wait for the slow nodes to complete their local computation. While this behaviour is simulated, we believe that this reflects the algorithm's 's practical potential. Finally, Figure 15 shows that all methods can reach the maximum accuracy for this dataset/model combination (for the SGD baseline, this occurs later), although QuAFL is the fastest to do so in terms of wall-clock time.
Our last experiment in Figure 16 examines whether naive QSGD quantization of the transmitted updates in FedBuff (Nguyen et al., 2022a) can converge at good rate, relative to QuAFL. at the same quantization ratio. We find that this is not the case: first, we remark that, with careful tuning of the learning rate, FodBuff can indeed converge. We believe that this is because of the specific application: the norm of the model and updates in DNNs tends to be small, and therefore the quantization error induced by direct QSGD stochastic quantization is also manageable. However, we observe a clear loss of convergence for the FedBuff + QSGD algorithm in this case, relative to QuAFL, which we ascribe to the fact that we are essentially running a heuristic.
A.5 RESULTS ON CIFAR-10 10
We now present results for standard image classification task on the CIFAR-10 dataset, using a ResNe120 model (He et al., 2016).
Figures 17 and 18 show the decrease in training loss versus the number of server steps (or rounds) for different values of K and respectively. As our theory suggests, increasing K and s leads to an improvement in the convergence rate of the system. Figure 19 demonstrates the impact of the number of quantization bits b, on the convergence behaviour of the algorithm. According to the definition of b, increasing the number of quantization bits improves the communication accuracy. Thus, as can be seen in the graph, higher values of b enhance the convergence relative to the number of server steps. Finally, Figure 20 shows the impact of the server interaction frequency, again controlled via the timeout parameter swi, on the algorithm's 's convergence. It is apparent that a very high interaction frequency can slow the algorithm down, by not allowing it to take advantage of the clients' local steps.
In Figures 21 and 22, we examine the validation accuracy and loss, respectively, ensured by various algorithms versus the simulated execution time. (As in the F-MNIST experiments, we assumed the Baseline to be single slow node that performs an optimization step per round.) Again, the asynchronous nature of QuAFL. provides a faster convergence rate than its synchronous counterparts; which can be clearly seen in the mentioned figures.
17

---

step I, and X is the local model of client after its last interaction with the server. Also, h2 is the sum of local gradient steps for model X since its last interaction with the server. Fec Ang (20 3.
Oudii 28.,.15/atiie 1415E 1312 Daacline
1.2
5.0
(205, S.Ateic
63
Suaciine
Time
Time
Vigure 21: Time vs, validation accuracy for various algorithm
Figure 22: Timing versus validation loss for various algorithm variants.
B THE COMPLETE ANALYSIS
B. OVERVIEW AND NOTATION
Recall that X, denotes the model of the
For the convergence analysis, local steps of the clients that any effect on the server or other clients. Therefore we do not need to assume that clients are doing their local steps asynchronous, and we can assume that all clients run their local gradient steps after the server contacts them. The only thing that we should consider is the randomness of the server selecting the clients, and the fact that the server contact nodes before they have finished their K steps. For this purpose, we assume that their number of steps is a random number H; with mean H. To show the analysis in this setting,
selected by the server don't have
introduce new notations that consider the server round. To this end, we use X as the value of X when the server is running tth iteration, And h for the sum of local steps at this time, We show each local step with superscript. Formally, we have
To. 0.
and for 5 S H; let:
T9 = -
Σ mhee))
and
H
h
g=0
Further, for 1 1595 S Hi, let
h = (X
Σ
=
Σ nh
==0
be the expected value of Ny taken over the randomness of the stochastic gradient Di Also, we have:
H 1
q=0
B.2 PROPERTIES OF LOCAL STEPS
Lemma B.1. For any agent i and step
o2
B 12 < K2
+ BL - mell
4E (
Proof.
EII4 (v
- - + v.((u))
==0
18

---

2
22E i Enhi
Vi((e)
+ 2B| V ((()))
<AL - 14.1 + 1,2 9-1
Bli 112 + 2 {+()))
SALiB|IXi - 1111 + L
(Bl 11 + + 2
==0
the of the proof is done by induction, and assuming 1) ALK" Lemma 4.6. For any step 1, we have that
Σ BI S 2n 2KG +8L + B=K
Proof. Using lemma B.1
K Pr[H; = M||
E ha Σ
h0,11 11?
i=1 h=0
q=1
h Pr[lIt h44
11116,111 11
q=1
S <nKo² +
Pr[H h1/
E11
i=1 h=1
0²
SnKo² +
K2
+8T, X3 mell 4TE V 1((
K
i=1
n
2nKoo
Σ
k2
81,22|| X; - -ell? + (
1=1
s 2nKo² + 81.2 E
+ 4= + (x
Lemma B.2. For any local step S q. and agent 1 S i and step
Vl - h1,.11 < g² A 1 y
Proof.
9-1
(((e)) - - - -[V VA(X;
Σ D2WWI
<1.731 x; + Σ n
==0
<2L2E|IX 1111 + 2n E
h
#=0
q-1
<21 - 11 + 2 +2L2n72
EI Blih 11
Lemma (B.1)
S 21 X - 11 2
20 + +8L -mel?
+ 4
19

---

=L''1/9'02 + +212 + Mell
(
<4L'n/''' + + pell? 8L''''
and the last inequality comes from < 4LK
Lemma B.3. For any time step
(- 3Hn
B(VS(u)), -hua) S 4KL
4 + +8 (2)_>>(KK)))///M
+ 1n - 2
Proof.
Σ B (p()) -haa)= =
Pr!mt -]E() Σ 1EW +
Prim - (
i=1 h=1
n
K
Pr|f h] Σ
[VV (7,)) ((+), v((lm)))
q=1
Using Young's inequality we upper bound E ff()). Vf((m)) -h(,) by
B [[4))|1 E Vi((u)) - nn,el²" -hg.)
4
Plugging this in the above inequality we get:
n
E f (m)),
-h,.)
K
h
( 1g,11²+ E -VV
Pr[Hi h] Σ
4
h=1
Lemma B.2 n
K
Hr h] Σ
4L' 4 - + {((
q=1
E V
E(V)(M). vf((m))))
4
K
Pr[H h|h 4123, +L 1 +
E [(
+
E(V f(x)), vf((m))))
4
K3 + Hn
S <4KL + K3 + 2G + 1L 2
4 Hn)EI
Where in the last step we used that E[H;] H, and Σ f((z) = f(x), for any vector x.
B.3 UPPER BOUNDING POTENTIAL FUNCTIONS
We proceed by proving the lemma 4.4 which upper bounds the expected change in potential: Lemma 4.4. For any time step I we have;
(1
B[P++]]
E + 8sT2
E E 11 16n(R² +
4m
Proof. First bound change in potential A, Q1+1 T for some fixed time step / 0.
20

---

For this, let A be the change in potential when set S of agents wake up. for i E S define St and St as follows:
S 8
nhis + Q(X,) - Xt
8 3+1
S
ha *+1 1
[(q(x -ntet) - (Xi - -)/,,.))
iE
EES
We have that:
sX; + X X
+ S
8 + 1
X1+1 Eies X3 + Xt
+ St
$ s+1
1441 = + Ljes St + St.
+ 1
This gives us that for i E S:
sXi Xx
Ejes St + Se
X Ma-1
+ +S.
14
$ ++1
n a+1 1
Eies X + Xx
Ejes S + St
X441 M1-1
+ S:
14
s+1
n +
For & we get that
EjEs S S n n+
x -4+11 = Xx
u4.
Hence:
A Σ iES
sXi Xx
+ St
Ejes St + St
- -M4 12 - x2 - mell
8 +1 1
n 11
Eies
Xi Xt SS Enes St + Sec
11 1| - Xx 115 1|
+
++1 1
n n+1
Ejes St + SS
Σ kgS
X7-
146 ?
-
| nell)
n+1
Σ ES
sx, + X₁
1e/ 1|
+ st + Σ JjEs St + Se S
8 +
n +1
sx + Xx
Ejes S + n n+1
| - mell)
+ +2
S4
8 +1
Σ ieg X + X,
1e 122 + *|||s, Ejes S + St 1p
8 s+1 1
++ 1
Eies X; + Xt
Σ jjes St + Sb
X, Ms 11)
+ 2
Mr, St
++1
n ++ 1
Ejes St S
Σ Ejes+ S + St 122
Σ 2 X pt:
+
n n+1
n + 1
Ags
kgs
Observe that:
n Σ
E S + St
x Pt:
= -0.
+1 1
A=
21

---

After combining the above two equations, we get that:
A = Σ
sXx: me) + (X+ m4) 2
Xi
|
1
Xx mell))
8 8+1
8
8+1
8 8+1
YES
(1)
-m) Σ Exis(x; - m4)) + (Xx - mo)
1²
Σ
Xi -
14
2
X - mell rell')
$ s+1
++1 1
1
iES
Σ JES St
+ +.
8x2; +
X
Mc: (M::8i) )i))
+2
n n+1
8 +
IES
Σ EEeS&
JES S +Sc 2
Lies X; + +Xt
5,
+ +
144, S1)
n ++ 1
8 8+1 1
Ejes St + S:
++ 1
kgs
By simplifying the above, we get:
A 8
|x
X,I12
1
|| - X1I12
1
Σ
|| - x3113) -x|1)
(8
1)²
(s + 1)²
11+ 112
8E8
iES
i.j
+
S
LjES
St St
+ s+1 1
28
Σ
x - Me, (i: + s 1 iES
2
Σ
X1 - -4, St
n+1
iES
EES
+ 8/
Ees St +Sp +
+ +
2
Σ
x 14, s.) +
2 / Xx, 14. Si)
n ++ 1
++1
iES
Σ jES S + St 2
+
n +
kgs
Let a be a parameter we will fix later:
5:
Yrung
S a x pe 1
(x: - ne, St)
+
4a
Finally, we get that
A S
|x
- 2 2 + 2
8
2
+
2s(s + 1)
Σ
|s
2
+
25(s + 1)
[s. 2
(n + 1)2
(n + 1)²
iES
iES
JES
|1: 2
S
+
280
Xi Me|
|||
2
+
2a
X1 11
Σ
5 +11
11)
S +
2a +1)
iES
iES
iEs
S. 2
+ 2
5
2
+
2(s + 1)
Σ
5 2
+
2(s + 1)
S.
+ Σ
2a
Xi - 11 + Σ
(n + 1)2
(n + 1)2
++1 1
20 + 1)
JES
IES
$ES
| 2
+
2a
X1 11l1
Σ
(n-s)(s (1 1)
|
2
+
(n (n-ah 5) + 1)
2
8 8+1 1
2a(s + 1)
(n + 1)²
(n (n+1)²
JES
-1
Σ
| x2112
+ (2 +
2(s ((s+10 1)²
1
(n-s)(s+1) 1)
|ss{| ||/2|= +
++1 iES
(n + 1)2
20
(n + 1)2
jES
+ 2(s + 1)2
(n - 5)(s + 1)
2
x: - ur| |||
X, - m4] 1
+
S
+
Σ
2a
+2
+ 2a
(n + +)²
2a
(n + 1)²
iES
22

---

-1 Σ
|x Xpl1² + (4+ 1
Σ
| +
$ ++1
2a iES
iES
(4 + 122
2a
Σ iES
20
x Me
| ||
+ 2a X,
Me 1
Using definitions of S and St, Cauchy-Schwarc inequality and properties of quantization we get that
2x²
2( + +7727
|| <
(s + 1)2
182
2s
110reel? + +
||5.11 <
(s + 1)2
18
SES
Next, we plug this in the previous inequality:
A
Σ
|x - X+11+ + Σ
20 Xi - 1/ 1
+ 20
X me| ||
8
iES
IES
1
28 + 28
(25² + (18 + +7)3g2
(4+ +
"/ Pllistel1
20
(8 + 1)2
(s + 112
< -1
| - x,11+ + Σ 2a x -1-mi H:| ||
+ 22 Xr 11| 1
||
8 ++1 1
ES
IES
+ (4 + 20
1 11 + 2R + 7)222)
YES
Next, we calculate probability of choosing the set S and upper bound A. in expectation, for this we define E, as expectation conditioned on the entire history up to and including step
1 E
EAA =
n2
1
|
12 + Σ
20 Xi-
1u|?
+ 22 X, nal
+
EES
$ES
+ (4+ 2a
(1)
| 12 + +(( + 7)873))
iES
(1=1
2a n-11)
||X x111 +
Xi ue|
+ +20 Xe- me|
(x+ (c)
(R-1)
+ (4+ 2a
| 2 + +(RR2 + +7)222)
x|| - Mel 12
+ >>> 2 sa
x - m
12 + 22
Xx +2al|x;
uel ||
(s + 1)m
+ (8 + ) + +7)2g2
Σ n
- (4+
+
2a
< (s 1)n
1 + 2a D. + (8 (R² + +7)
+ Σ
$
(1+
+
1
>n²Bulll
E. Bellhh..ll
n
2a
By setting a
3--1 n(8++8)
2 1
we get that:
8n,
R2 [A( -
1 Φ. 16n R22 + 7)222+
Σ
8sn Be
4n
23

---

Next remove the conditioning. and use the definitions of A and Si (for Sj we also use upper bound which come from the properties of quantization).
B 1 4 +1ll = B|A, + Del - (1
JE|0.] 16n R² +7)?7/ + 85n2 Σ Bl
4n
Lemma B.4. For any time step we have;
[[ S 57
Proof. By combining Lemma 4.4 and 4.6 we have:
E 1 $ (1
1 + 16n ( 7)
4n
8sn [2nK + -KG
4 / vf(m)))
=11
64sL 16 +
+
4n
16nsK (0² 2KG 32B ns K2 2 B f(4))1
S
E[ 16n 16n 2 +
5m
16nsKn + 2KG + 333 B f(
Lemma B.5. For the sum of potential functions in all steps we have:
T
T-1
Σ
B[0,] < S0T +7) 800 - +600" Σ
E V f(1))1
1=0
Proof.
T
10 1+1 5
[[
16 + 7)322+
5m
16nsKin +2KG3 (6nkk))(0+22K3) 3 n2
T-1
[[ + 167n + +) o02
5/
t=0
(
Σ
B[ < 5n $167nR((R + + (0
1=0
-3322nsk' 17
(f()))
SOTni + 7)222 80T KK 2
2KG
T-1 1
160B"
n 1=0
Σ
Vf(4))
Lemma 4.5. For any step
252nz
11441 2 1e(n + 1)²
Σ
E
hi.
+
(n + 1)2 (R² + 7)272.
24

---

Proof.
his + Q(X)) - X
E M4+1 Pell
E -
(n + 1)2
a+1
8
iES
1
(Q(x - -nha,))
-X; - -TTxae)))(
8
+
iEs
1
2011 Σ
2
2
n8 [(x,) x.
+ +
(n + 1)2
9
iES
2
Σ
nTa,.) - -(x; n)/x)a))
+
8 ++
iES
1
2012
E
h4.
+ + +)2g2
(n + 1)²
8
iE8
2011" (H-1)
2
E hige
+
RR² + +7727
(n) + 1)3
(n
+ 1)2
2²²17²
2
18 hu.,
(R² + +722?
n(n + 1)2
(n + 1)2
By plugging Lemma 4.6 in the above upper bound we get that: Lemma B.6. For any step I.
4s Kin + 2KK22
16s 16
Bl| Hell? <
(n + 1)²
n(n + 1)²
8B2 82 (14))1
2(R - 7
(n + 1)²
(n + 1)2
Proof.
Ellpe+1 1el12 < Σ
2
(R² 7)222
nnn 1)²
(n (n+1) 1)2
2
2n + +2KG9) 812 (2
4nk3 S(m))1?
nnn 1)2
2(122 +7)222
(n + 1)2
(n+ 1)2 (02 + 22 16s 1, E[2e]
K1p
n(n + 1)2
(f(a)) + 2(1² + 7) K22
(n + 1)²
11+1)
B.4 CONVERGENCE Theorem B.7, For learning rate 11 n+1
Algorithm 1 converges rate:
'HVT'
[ 2(f(Ho) f.) L +7?22
6KL(02 2KG
VT
H
HT
808n(n+
K2?
2(R² + 7
(02 + 2KG2)
sH3T
(n + 11²sH
25

---

Proof. Let E,, denote expectation conditioned on the entire history up to and including step By L-smoothness we have that
Er { + (L M4+11 -4) m4) + Belllee+ - Hell?
(5)
First we look at E, ((e)) Me+1 M²) (V (V]())), Belue+1 - we]) We have that
If set S is chosen at step / 1,
har + Q(X,) X2
P++1
P4 n +
+
Σ(Q(x) - nps,,)) - -X; -nn),))))
s s 1
8 + 1
ES
Thus, in this case:
7 hig
14]
12
IES
Where we used unbiasedness of quantization and stochastic gradients. We would like to note that even though we do condition on the entire history up and including step / and this includes conditioning on X the algorithm has not yet used h.,e (it does count towards computation of j4)) thus safely use all properties of stochastic gradients. Hence, we can proceed by taking into the account that each set of agents S is chosen initiator with probability
E2 (ut11 [40]
Σ his = nnn + 1) EES
81)
higt
n
S
iES
1=1
and subsequently
E. (Vf())) pet1 1b)
ST
E, ((((())), -ha,)).
n(n + 1)
Hence, we can rewrite (5) as:
Belf(u41)) S f(p))
Σ
ST
L E, (Vf(He) -ha,) + E,
|| Mell?
n(n + 1)
2
Next, we remove the conditioning
sn
[[(++1)] = -[[EE S E(f(p)) +
E(V (())) -14,)
n(n + 1)
L || pell2.
2
This allows us to use Lemmas B.6 and B.3:
871 [[f(#++1) -[((()) n(n + 1) [AKT +(-
3Hn
4
+ 4n k (0² + 2G
L
482 448 112 + 2KG
16s 1, 222
+
2
(n 1)2
n(n + 1)2
8B2 K 12 V f1m)11
2(122 + 77 (n + 1)2
(n 1)2
412K12
8 k2 1,3,
n(n +
(1 1)²
11 K3 K3
2s² K L
(R²2 + 7)292 (n (n+1y)
(o" + +KK2)
n +
(n+ + 1)2
3nsH
SB2 3 sK3
4B2 LT?
)E V f(
1(n + 1)
n n+1
(n + 1)2
26

---

By simplifying the above inequality get:
K [
4oL21)K
2 )(22 2k²
[[(()++1]] - [B[()))]
n(n +1)
n n+1
1) 8B"
(R² + 7)2g2L
-3nsH
(n + 1)2
4(ni + 1)
n+1
4B2 K2L
|B (w))l
(n (n+1) 1)²
by summing the above inequality for = 0 to t = 1, we get that
E[S(UT)] - f1O) v 5ms K I
T-1
2
B[o,] +
n(n + 1)
n+1
(n 1)2
1=0
33sH
8B3L''n' sK
AB2
E (((e)11
1(n + 1)
n+1
(n+ 1)2
(R² + 2TT
(n+1) 1)²
Further, we use Lemma B.5:
[[f()r)] - f(wo) v 5nsKL2
80Tn"(R² + + 3
n(n + 1)
+ n600Bn2sK3) 2
Σ (=0
E (f(()))
2s Kn L
)0² +2KG9) (R² + +7)2,2TT
n+1
(n 1)2
(n+ + (1²
-3nsH
8B"L'
4B25K2Lnn2
E|| [
4(n +1)
n n+1
(n + 1)2
400msmK LTT (O' + +7)272
4s 12 (o2 2²
n+1 35 Kip 1I (T + 2KG2)
n 11 1 (RP + LTT (n+ 1)2
(n (n+
33sHH
8B3 LB"L''''s''
1(n 11)
n +1
800 13 L2
T-1
V ((x))
(n + 1)2
n +
by assuming 77 < 100B.nste we get:
+ 7)227 400msnK L
E[S(TT)] - -((1)) 5
n2 1+1 2 Kn² LT
404Tns² 13
)0² + 2KG²) + (R² + 2 LT n+1
(n + 1)2
(n + 1)2
Hs T-1
Σ 1=0
2(n
Next, we regroup terms, multiply both sides by 2(x+1) and use the fact that f(ur) 2 fa: nHSf
B [(m)) < 2(n + 1)(F(p)) - fa) 800nKL ( + 7)?g²
sH1îT
H
27

---

+ G. H + 1)
808ns
]00 + 2(R² + 7)
+
H
(n + 1)sH1
Finally, we 1 17
n+11 x11 v
E E((S((m) 2(f(Ho) - f.).
800nKL? +797²
6KL(0² + 2KG2)
(6)
T
VT
H
HVVT
808n(n +1)2K2L?
(o² +2KG9 + 2(R + 7
+
(7)
sH3T
(n ( (1+1)
Lemma B.8. For quantization parameters (R² + 77??2
(x+1)²
5H (o² + 2KG f(H))) we
have:
B|V S 5(s(ma)-1) S.)
8KL(0² + 2KG
VT
H2VT
1608n(n (o + +KKG²
800n(n 1)2 (L(((o)) -fa)
sH1T
S3
Proof.
B | & 2(f(po) - f.), L3 +7)22, 6KL 2KG
+
VT
H
H2VT
208m(n+110 11
(o² (0*+2KG9)+ + 2 + 7)
sH3T
(n + 1)?sH
2(S(1o) S.).
800nKL 1)2
(02 2KG [(10) 5ny
VT
82HTT
L
6KL + 2KG
808n(n 1)2K3
(o² +2G2))
H²VT
sH3T
2L 10" + +KG + f(P0) 5(Ho)- 51) -1)
H2
L
5( S.), 8KL(02 +2KG2)
VT
H²VT
1608n(n + I2 + 2KG2
sH3T
800m(n + ()) f.)
Lemma B.9. We have:
T-1
E[ + 3r7
Σ
EE he. < 1 + 7)??
t=0
+ x2 +7)2n²
Proof.
T
58
E
B[ + 3r/
2
T-1
T-1
< 58
Σ
EB + 3n
Σ
(2nK(6) (o² + """"
1=0
1=0
28

---

T-1
S 58
E| + GnTrfK((o 2KG + 24
E B(
1=
R [ + 12mmB212 K2
< 68 Σ
+
+ GnTT) 2KG + 12B nuyy K
< 6s(80Tn + + 80T 80In"s -2K
T-1
+ 1600B"n2sK* 7
E f(4))
T-1
+ +6nTr)'K(0 + 2KG + 12B2
k2
E V f(4))1
1=0
< 4800'' (R + + (480T' Kn) + 6n4 K (o + 2KG
T-1
+9600n 2960n23² B² 12 K3
< 480Tn2 7 + 486 22 2KK22
+ +1000B" / T-1
E {
< 480Tn' s(² + ? + 486T 2 3² Kn)
+ 2KG²)
2(n + 1)()(o)) [.))
QO0TnKL"(1E* + 7)222
+ +1000B2
sHn
H
6TsKn 808T 127p 10² 2K2+)KG)++ 27(R2 + +7)2y2..
H(n 1) +
H
(n + 1)sHn
Ki² 3 < 480Tn2 (RR² + 7 486T
2KG 2000B3 nf -1)
K (
H 6000T
H
B0 K ) + 2KG
H(n + 4000T B' K K2nI +7)2g2
H < 10000 s(H - 7)272 10000T (n + + (0² (2+2
(n + +1) 4000B n sK²
(f(Ho) - fa)
VT
T
< 1 'RR2 7)272 x0 +7)32
Lemma 4.8. Let T 2 Onn²), then for quantization parameters R = 2 + T T and y2 2=2K we have that the probability of quantization never failing during the *H
entire run of the Algorithm is least 1 1 (+).
Proof. Let L. be the event that quantization does not fail during step t. Our goal is to show that
Pr[Uf Li] 2 1 - 0 (+). In order to do this, we first prove that Pr[-Ce+1 LL, C2,... Li] S
O (+z) (0 with respect to 7 here).
29

---

We need need to lower bound probability that
Vi E S :| xxi12 - (R²" 7)²
(8)
|X+ (X² - -1 S (ne 7)2
(9)
|xg xi112 =0 (>((ooly(T))
(10)
17a
0 (
(2 (P(ol((T)) R²
|X - (Xi nyi-n
(11)
We would like to point out that these conditions are necessary for decoding to succeed, we ignore encoding since it will be counted when someone will try decode it. Since, R = 2 + T this means
that ( 3 2 22T 2 7,30 for large enough T. Hence, it is suffices to upper bound the probability
that Eies 1.Xe x + Eies |x (X; - mm? > y2 To prove this, we have:
Σ ||x - X;12 Σ |x, (x n)1,,,)11 - iES
> [51||Xe - Hell
+ 511m
x/11 + 31/ h ) S 5. +317² Σ 1
Now, we use Markov's inequality, and Lemma B.9:
13 R5 + 317
Σ, [/sisel1
L1, (1,,.....,..
Pr| 317" 1 T 7200)222,,0 f2. Lul
TT002
1000Tn3s(R² + 7) + 10000 K +7) +
< 00
7
7
Thus, the failure probability due to the models not being close enough for quantization to be applied
is at most O (7²z ) Conditioned on the event that ||xe Xill and |X -X; - ,)h,,))l are upper
bounded by 1 (This is what we actually lower bounded the probability for using Markov), we get that the probability of quantization algorithm failing is at most
Log
log log( ?
||x, x;I)) ORR
iES
log log( 1
Σ iES
- =|x, - (X, -h)
- 0(H
log log T
0
O
T3
72
By the law of total probability (to remove conditioning) and the union bound get that the total probability of failure, either due to not being able to apply quantization or by failure of quantization chain rule get that
algorithm itself is at most O (+2)) Finally
T
T
Pr|u Cd) = II
Pr U C.)
II
(1 Pr( Cal-Lal U.b
> 1 - Σ Pri-Cal - C.] - (
Lemma 4.9. Let 2 O(n²), then for quantization parameters 2-2 and (R²47)2 (o² 2KG²+ + f(ue)-f=) we have that the expected number of bits used by Algorithm per communication (ddlogg() + log(T)).
1/2
30

---

Proof. At step + 1, by Corollary 4.3, we know that the total number of bits used is at most
Eo dloll xi - -xil==)l)) + Od log = |x, - (Xi (xi=nh),))ll)
R
iES
By taking the randomness of agent interaction at step t + into the account, we get that the expected number of bits used is at most:
R ||x, - -xx - - o Odlogg( - |x] - xxll)) + 0 O (dlog(
Σ
8
ES
Σ
R Oddlog
| xxil)) + oddlog( ?
|xx - (X; r
(0(dlog) g2
R²
|| - xx(13) + 0 ldlo
RR
||xe - (Xt n(taalle)
72
Jensen
ofddlog
R2
_ (11x - x.112 + I|x - (X - -7 -11h,s))13)
??
R2
0 log(
(1Ix,
uell + ||x; wall + (111)),)1133)
Ss 0 (lllog
D1
7 (1aad11)))
Σ
n1
So the expected number of bits per communication in all rounds is at most:
R²
0 dloog
Σ
sT
t=
(
0 doog
R²
Σ
Φ.
1
Σ
n
Σ (Ta.cl1)))
72
n
t=)
Next, By Jensen inequality and Lemma B.9, We get that the expected number of bits used is at most,
R 72
T-1
T-1
o
de log
n
1=0
1=
Jensen
(dlog
R²
T-1
E[
+
T-1
Σ
T
T 1=0
1=0
0 ddog( 72
R²
1 11000'''' ss((2 ((R22+77' +
+7)3}2)))
(d(dlog(R2 'RR + + 10000B"n32K + + Odllgg(n) + (og(T))
Theorem 4.2. Assume the total number of steps T 2 2(n²)), the learning rate nt1 "HVT' and
quantization parameters == = 2 T and 72 = परम (o² + 2KG + (1)))) Let H > 0 be the expected number of local steps alreudy performed by a client when interacting with the server. Then, with probability at least O++) we have that Algorithm I converges at the following rate
2,
T-1 H
EIV((PO11+ 5(f(po) + 8KL + +2G2) +0 ( ( (n² +2G VT
H2
SH3T
and uses O (dTld + log T)) expected communication bits in total.
Proof. The proof simply follows from combining Lemmas B.8, 4.8 and 4.9
31

---

Lemma B.10. For the convergence of the server. we have:
[XV](X))] 15(f(po) fa). + 24K + 2KG
VT
H²
4824n(n + 1)² 320m² (n KI2
10² +2KG)
3HTT
sH²T
2400m(n + 1)2KL
160m² (n + 1)²
)((())) - f-)
22
Proof.
Σ
E
- +
1=0
2
2
(x),) V
Σ
T
T
2L T-1
BI|x; - 1111
2 T
Σ
2L T-1
2 T-1
Σ
B|0,] + T
Σ
| {(r))
T
1=0
< 2I (80
+ +
+ 80n2 2 's sKn
=Kn'(0" (0² +
[V + 2 Σ
+ +160B"n2sK*
[VS(1))
1=0
T-1
S 1,60n2T,2R2 + +7222 160n +2KG2) + Σ [VS(21]1
+2KG2 + 15(f(Ho) - fa). 24KL + 2KG2
160m2L2(1F) + 7)22 +
VT
HRVT
4824n(n () 2KG 2400n(n + (L) fz)
SH
2
< 160nn L322200 + GKG + f(Po) - fr, + 160nn + +KKG) + 15(f(H)) - f+)
VT
20KL(02 + 2KG 4824n(n + () + 2KG2
H2VT 2400n(n + 1)2K)(((H)) - (a) HH
sH3T
15( (c) 24K + 2KG2)
VT
H²VT
4824m(n + 1)2
320m² + 1)2
1(02 + +2KG2
sH3T
sH2T
2400n(n + 1)2KL
160n (n + (0 1)?
)(((p))) - ff)
22
H2T
Finally, the proof of Corollary 4.3 follows from combining Lemmas 1. 4.8 and 4.9
32


Reviews:
[{"review_id": "_hJUJLOTdpb", "reviewer": "Reviewer_ZjQd", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper incorporates quantization and asynchronous communication to well known Federated Learning algorithm. The compression scheme is based on lattice quantization. Convergence analysis of the proposed algorithm is provided and empirically verified through a set of experiments.\n", "summary_of_the_review": "Please see the comments above!\nI will update my score based on the authors feedback.\n", "strength_and_weaknesses": "Strength:\nI think the paper is quite easy to follow and the majority of related works are cited.\n\nWeakness:\nIt is not clear to me at this point why authors specifically chose Latice quantization and what are the advantages of lattice quantization compared to the rest.\nI think it is very important to compare the tightness of the bound with prior work asyncronous FL algorithms such as [A]. What I would like to see is that if your bound of Theorem 4.2 if I do not use quantization $\\gamma=0$ how would your result compete with prior studies? Unfortunately, It is not obvious to me, and not sure whether you could improve the bounds in prior bounds.\nAnother limitation I see is that for both Theorems 4.2 and corollary 4.3 you need to have $T\\geq \\Omega (n^3)$ and $T\\geq \\Omega (n^4)$. In the convergence of FedAvg we do not have these constraints and how would the author comment on that?\nI think the experiment section is also limited. Authors would want to compare with other Asynchrnous FL algorithms as well. Furthermore, as our ultimate goal is accuracy, Authors should compare the accuracy of their results with FedAvg and other SOTA algorithms.\n\n[A]: Koloskova, Anastasia, Sebastian U. Stich, and Martin Jaggi. \"Sharper convergence guarantees for asynchronous SGD for distributed and federated learning.\" arXiv preprint arXiv:2206.08307 (2022).\n\nMinor comment:\nI think the contributions part should be more concise.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "YTICr1kq_I", "reviewer": "Reviewer_xMTC", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper examines the federated learning problem when updates are made asynchronously and communication is compressed. The authors present a new variant of the classic federated averaging (FedAvg) algorithm, namely QuAFL, that supports both asynchronous communication with compression. In some parameter regimes, they demonstrate that their proposed algorithm can provide similar convergence to FedAvg. The authors show that the algorithm ensures fast convergence for a few standard federated learning tasks on the experimental side.\n", "summary_of_the_review": "This paper presents an algorithm for asynchronous federated learning with compressed communications. The authors propose a feedback-based algorithm that reduces communication overhead in the federated framework based on existing research on asynchronous updates and lattice-based quantization. This paper focuses primarily on theoretical studies and analysis. A major area for improvement of the work is the need for adequate comparisons with prior works, both theoretically and experimentally. According to the analysis and experiments, there is no clear evidence that compression reduces communication volume. Additionally, some work is required to improve the presentation of this paper.", "strength_and_weaknesses": "Strengths:\n-New convergence analysis for asynchronous federated learning\n-Incorporating the idea of compressed communication with asynchronous updates\n\nWeaknesses:\n-The server algorithm has an underlying assumption (lines 4-6 of Algorithm 1) that the server can allocate separate memory to each client's parameters. To this reviewer's understanding, this is not a proper assumption for cross-device federated learning. \n-The update in line 6 of Algorithm 1 requires an additional acknowledgment message from the server and client to ensure that the most updated parameter has arrived at the client. When updates are delayed or communication is lost, this creates an additional burden.\n-The assumptions on the compression operator must be stated formally in the paper. Lemma 4.1 does not clearly state the required setup for compression.\n-Section 3 presents briefly (informally) the assumptions about asynchronous communications. Asynchrony is one of the main contributions of this work, so it should be stated as a separate formal assumption in Section 4.\n-There is a limited comparison with prior works. It is necessary to compare the asynchrony assumption to prior works. As far as this reviewer is concerned, it is unclear how this assumption fits into the literature.\n-The benefit of compression in terms of exchanged bits (or other metrics) in the experiments must be presented and discussed. The experiments should include comparisons with other algorithms.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "76vCn0DsNXG", "reviewer": "Reviewer_oDyr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies how to use communication compression and asynchronous training together in federated learning (in particular, FedAvg algorithm). The authors showed that most previous papers used non-standard assumptions when analyzing the convergence of FedAvg with gradient compression. In their new analysis, they are able to use all standard assumptions. Also, they introduce new analysis techniques to analyze asynchronous behaviors. At last, experiments validate the theoretical predictions on how the algorithm changes along with its hyper-parameters.", "summary_of_the_review": "While I appreciate the efforts the authors put into the theoretical analysis, the motivation and some technical details of this paper are not satisfactory.", "strength_and_weaknesses": "Strength\n- The algorithm seems to be very complex but the authors are able to provide a very clean theoretical result.\n- I can imagine that analyzing an FL algorithm with both compression and asynchrony must be complicated. The authors successfully manage the complex derivation process.\n- Most previous analyses on gradient compression used non-standard assumptions. But the authors are able to remove/replace them with standard ones.\n\nWeakness\n- The motivation of this paper is a bit weak. In the introduction, the authors start the paper by saying that both compression and asynchrony are needed for practical FL. This is true. However, both techniques have been studied in previous literature. We already get answers to questions like how to apply asynchronous training in FL, and how to use gradient compression in FL. These two techniques are orthogonal to each other and might be easily combined together. It is unclear to me what are the key algorithmic challenges here. If simply combining them does not work, then the authors need to provide some theoretical or empirical evidence. But I didn't find any. If simply combining asynchrony and compression works, then the authors are supposed to change the introduction and motivate the paper mainly from a theoretical perspective.\n- It is unclear to me how the asynchrony works in the proposed algorithm. At each round, the server needs to randomly select $s$ clients. Then, immediately after receiving the server request, the clients need to upload their local models. That means these clients should already start local training at an earlier time. Then, what if some clients never participate in training before? It seems that the authors assume that at any time all clients are performing local training, which is impractical and a waste of resources. Could the author answer the question: how many clients are concurrently performing local training at any given time?\n- The theoretical result seems to be weak. In particular, the dominant term in Theorem 4.2 is $1/\\sqrt{T}$, which does not depend on the number of all clients $n$ nor the number of sampled clients $s$. This rate is slower than vanilla FedAvg, which gets improved rates when selecting more clients.\n- It would be better to provide an update rule for the proposed algorithm so that people can easily get what the algorithm exactly does at each round.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6JrCBqVCvRT", "reviewer": "Reviewer_ea7y", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper studies asynchorous federated learning with communication compression called QUAFL. In this model, The server randomly pick clients whose gradient might be stale, and clients are assumed to have positive expected number of local steps each time it interacts with the server.  A new model aggregation rule is designed in the paper, with convergence analysis. Experiments illustrate the effectiveness of the method.", "summary_of_the_review": "The paper studies an interesting problem in asynchronous FL. However, I have a few concerns about the algorithm and theoretical analysis. More clarification and experiments might be needed to address this issues. Moreover, the experiments, which mostly consist of ablation studies, are insufficient to show the benefit of the proposed strategies. Thus, I think the paper does not reach the high bar of ICLR.", "strength_and_weaknesses": "S1. The FL problem is important and may interest broad audience of ICLR. The asynchronous model seems novel and meaningful in practice.\n\nS2. The delay model considered here more flexible than the classical model with bounded delays, since here the delay can be unbounded in worst case.\n\n---------------------\nW1. In Algorithm 1 line 5, $Y_i$ is used without definition. I understand the global aggregation rule, but for the local update, why is the global model weighed by $1/(s+1)$? In my understanding, if there are very slow clients, then at local synchronization we should put a large weight on the global model to help the slow clients catch up with the global model. Say, if we have million of clients and $s=n$, then all the clients basically only update on their own data and do not synchronize with the server ($1/(s+1)$ is negligibly small). I doubt that the algorithm still works in this case. Could you please provide more intuition on this weight?\n\nW2. There are some overstatements regarding the theoretical results. The $O(1/\\sqrt{T})$ rate in Corollary 4.3 does not match the best convergence rate of FedAvg in Karimireddy et al. (2020). In that paper, the authors showed that the convergence rate of FedAvg can be $1/\\sqrt{Ts}$. \n\nW3. In Corollary 4.3 the learning rate $\\eta$ increases when $s$ decreases. This is counter-intuitive since typically, when there is fewer participating clients, the variance of gradient estimation gets larger and one need to use smaller learning rates. Additionally in this asynchronous case, smaller $s$ means more delays, which implies larger gradient error caused by staleness. Thus, I'm not very sure if this learning rate schedule is a correct choice.\n\nW4. The experimental evaluation is insufficient. Most results are ablation study and the proposed method is only compared with standard FedAvg in one figure. There are more compression methods other than the lattice quantization used in QUAFL which can be tested. There  might also be other aggregation strategies such as the one I mentioned above, directly updating the local model with the global model when interacted. More results should be provided to justify the unique advantage of the new update rule and quantizer, compared with some standard methods.\n\n------------------------------------------------------------------------------------------\nPost-rebuttal:\n\nI would like to thank the authors for the reply and adding more experiments. I appreciate the additional results on QSGD and FedBuff. However, the rebuttal does not fully address my concerns.\n\n1. While there is one figure in the supplemental file that shows the result with $n=300$, the number of active clients $s$ is only 30, which is still quite small. Also, it seems that the experiments are simulated on iid clients as described in Section A.2. Thus, this is not very convincing to resolve my question on the vanishing weight of the global model in the local model update with large $s$ asymptotically. When $s$ is very large, the local models train on their own data without communicating with others, and the global model simply takes the average of the local models. In my understanding, this should not work with non-iid clients. In addition, I think the \"optimal approach\" you mentioned is exactly the standard averaging strategy in which the global weight equals 1 instead of $1/(s+1)$.\n\n2. Thanks for the explanation and please add some discussion in the paper that your rate matches FedAvg under some specific parameter settings and in the wall-clock sense.\n\n3. In the scaffold paper, they consider two learning rates (global $\\eta_g$ and local $\\eta_l$) and the effect of $s$ is \"balanced out\". In your method you only use one learning rate which increases with smaller $s$. Thus, this still looks unnatural and incorrect to me.\n\nI appreciate the efforts in adding more experiments and baselines. Yet I still have some concerns on the correctness of the algorithm and analysis (and the iid experimental setting). So I will keep my score.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject