SWIFT: Rapid Decentralized Federated Learning via Wait-Free Model Communication
Authors: Marco Bornstein
Tahseen Rabbani
Evan Z Wang
Amrit Bedi
Furong Huang
Venue: ICLR 2023 poster (2023)
Keywords: Federated Learning
Asynchronous
Decentralized
Wait-Free

Abstract: The decentralized Federated Learning (FL) setting avoids the role of a potentially unreliable or untrustworthy central host by utilizing groups of clients to collaboratively train a model via localized training and model/gradient sharing. Most existing decentralized FL algorithms require synchronization of client models where the speed of synchronization depends upon the slowest client. In this work, we propose SWIFT: a novel wait-free decentralized FL algorithm that allows clients to conduct training at their own speed. Theoretically, we prove that SWIFT matches the gold-standard iteration convergence rate $\mathcal{O}(1/\sqrt{T})$ of parallel stochastic gradient descent for convex and non-convex smooth optimization (total iterations $T$). Furthermore, we provide theoretical results for IID and non-IID settings without any bounded-delay assumption for slow clients which is required by other asynchronous decentralized FL algorithms. Although SWIFT achieves the same iteration convergence rate with respect to $T$ as other state-of-the-art (SOTA) parallel stochastic algorithms, it converges faster with respect to runtime due to its wait-free structure. Our experimental results demonstrate that SWIFT's runtime is reduced due to a large reduction in communication time per epoch, which falls by an order of magnitude compared to synchronous counterparts. Furthermore, SWIFT produces loss levels for image classification, over IID and non-IID data settings, upwards of 50\% faster than existing SOTA algorithms.

Published as a conference paper at ICLR 2023
SWIFT: RAPID DECENTRALIZED FEDERATED LEARN- ING VIA WAIT-FREE MODEL COMMUNICATION
Marco Bornstein, Tahseen Rabbani, Evan Wang, Amrit Singh Bedi, & Furong Huang Department of Computer Science, University of Maryland (marcob, trabbani, ezw, amritbd, furongh @umd.
ABSTRACT
The decentralized Federated Learning (FL) setting avoids the role of a poten- tially unreliable untrustworthy central host by utilizing groups of clients collaboratively train a model via localized training and model/gradient sharing. Most existing decentralized FL algorithms require synchronization of client mod- els where the speed of synchronization depends upon the slowest client. In this work, propose SWIFT: novel wait-free decentralized FL algorithm that al- lows clients to conduct training at their own speed. Theoretically, we prove that SWIFT matches the gold-standard iteration convergence rate ((1/VT) of parallel stochastic gradient descent for convex and non-convex smooth optimization (total iterations 7)), Furthermore, we provide theoretical results for IID and non-lID settings without any bounded-delay assumption for slow clients which is required by other asynchronous decentralized FL algorithms. Although SWIFT achieves the same iteration convergence rate with respect to T as other state-of-the-an (SOTA) parallel stochastic algorithms, it converges faster with respect run-time due to its wait-free structure. Our experimental results demonstrate that SWIFT'S run-time is reduced due to large reduction in communication time per epoch, which falls by an order of magnitude compared to synchronous counterparts. Furthermore, SWIFT produces loss levels for image classification, over IID and non-III data settings, upwards 50% faster than existing SOTA algorithms. Code for SWIFT can be found on GitHub at https: / /githtb........gg com/ und wt//:/ddduh-nuuaee Tuaan--ab/SSD
INTRODUCTION
Federated Learning (FL) is an increasingly popular setting to train powerful deep neural networks with data derived from an assortment of clients. Recent research (Lian et al., 2017; Li et al., 2019; Wang & Joshi, 2018) has focused on constructing decentralized FL algorithms that overcome speed and scalability issues found within classical centralized FL (McMaban et al., 2017: Savazzi et al., 2020). While decentralized algorithms have eliminated a major bottleneck in the distributed setting, the central server, their scalability potential is still largely untapped. Many are plagued by high communication time per round (Wang et al., 2019). Shortening the communication time per round allows more clients to connect and then communicate with one another, thereby increasing scalability.
Due the synchronous nature of current decentralized FL algorithms, communication time per round, and consequently run- run-time, is amplified by parallelization delays. These delays are caused by the slowest client in the network. To eircumvent these issues, asynchronous decentralized FL algorithms have been proposed (Lian et al., 2018; Luo et al., 2020; Liu et al., 2022; Nadiradze et al., 2021) 1). However, these algorithms still suffer from high communication time per round. Furthermore, their communication protocols either do not propagate models well throughout the network (via gossip algorithms) or require partial synchronization. Finally, these asynchronous algorithms rely on a deterministic bounded-des -elly assumption, which ensures that the slowest client in the network updates at least every т iterations. This assumption is satisfied only under certain conditions (Abbasloo Chao, 2020), and worsens the convergence rate by adding sub-optimal reliance 7.

---

Published as a conference paper at ICLR 2023
Algorithu
Iteration Convergence
Clicnt (2) Comm- Complexity
Neighborhood Avg.
Asyachronous
Private Memory
D-SGD
O(1/vT))
( mux k())
PA-SGD
O(IvVT)
O maxxee, Kg)
LD-SGD
O(I/VT)
O(CC max ())
AD-PSGD
O(z/VT)
O
SWIFT
O(I/vT)
O C.I.E)
Notation: lotal Iterations T. communication C, (IC,) T), client neighborhood maximal bounded delay communicaton time
per round V; (2) compared AD-PSGD, SWIFT does not have a convergence rase term doe to using an expected cliemi delay in unalysis.
Table 1: Rate and complexity comparisons for decentralized FL algorithms.
To remedy these drawbacks, we propose the Shared Walt-Free Transmission (SWIFT) algorithm: an efficient, scalable, and high-performing decentralized FL algorithm. Unlike other decentralized FL algorithms, SWIFT obtains minimal communication time per round due to its wait-free structure. Furthermore, SWIFT is the first asynchronous decentralized FL algorithm to obtain optimal O(1/VT) convergence rate (aligning with stochastic gradient descent) without a bounded-delay assumption. Instead, SWIFT leverages the expected delay of each client (detailed in our remarks within Section 5). Experiments validate SWIFT'S efficiency, showcasing a reduction in communication time by nearly an order of magnitude and run-times by upwards of 35%. All the while, SWIFT remains at state-of-the-art (SOTA) global test/train loss for image classification compared other decentralized FL algorithms. We summarize our main contributions as follows.
<> Propose a novel wait-free decentralized FL. algorithm (called SWIFT) and prove its theoretical convergence without bounded-delay assumption.
Implement novel pre-processing algorithm ensure non- non-symmetric and non-doubly stochastic communication matrices are symmetric and doubly-stochastic under expectation.
Provide the first theoretical client-communication error bound for non-symmetric and non-doubly stochastic communication matrices in the asynchronous setting.
Demonstrate significant reduction in communication time and run-time per epoch for CIFAR-10 classification in IID and non-Ill settings compared to synchronous decentralized FI..
RELATED WORKS
Asynchronous Learning. HOGWILD! (Recht et al., 2011), AsySG-Con (Lian et al., 2015), and AD-PSGD (Lian et al., 2017) are seminal examples of asynchronous algorithms that allow clients to proceed at their own pace. However, these methods require a shared memory/oracle from which clients grab the most up-to-date global parameters (e.g. the current graph-averaged gradient). By contrast, SWIFT relies a message passing interface (MPI) to exchange parameters between neighbors, rather than interfacing with a shared memory structure. To circumvent local memory overload, common in IoT clusters (Li et al., 2018), clients in SWIFT access neighbor models sequentially when averaging. The recent works of (Koloskova et al., 2022; Mishchenko et al., 2022) have improved asynchronous SGD convergence guarantees which no longer rely upon the largest gradient delay. Like these works, SWIFT similarly proves convergence without bounded-dell assumptions. However, SWIFT differs as it functions in the decentralized domain as well as the FL setting. Decentralized Stochastic Gradient Descent (SGD) algorithms are reviewed in Appendix D.
Communication Under Expectation. Few works in FL center on communication uncertainty. In (Ye al., 2022), a lightweight, yet unreliable, transmission protocol is constructed in lieu of slow heavyweight protocols. A synchronous algorithm developed to converge under expectation of an unreliable communication matrix (probabilistic link reliability). SWIFT also convergences under expectation of a communication matrix, yet in a different and asynchronous setting. SWIFT is already lightweight and reliable, and our use of expectation does not regard link reliability.
Communication Efficiency. Minimizing each client i's communication time per round E; is a challenge in FL, the radius of information exchange can be large (Kairouz et al., 2021). MATCHA (Wang et al., 2019) decomposes the base network into m disjoint matchings. Every epoch, a random sub-graph is generated from a combination of matchings, each having activation probability Pa.- Clients then exchange parameters along this sub-graph. This requires a total communication- time complexity of O(T) Dm Lk=1 Pk maxjeN; Cz), where M; are client i's neighbors. LD-SGD (Li
2

---

Published as a conference paper at ICLR 2023
et al,, 2019) and PA-SGD (Wang & Joshi, 2018) explore how reducing the number of neighborhood parameter exchanges affects convergence. Both algorithms create a communication set C. (defined in Appendix D) that dictate when clients communicate with one another. The communication-tin complexities are listed in Table 1. These methods, however, are synchronous and their communication- time complexities depend upon the slowest neighbor maxjeN; Ej. SWIFT improves upon this, achieving a complexity depending on client's own communication-tim per round. Unlike AD- PSGD Lian et al. (2018), which achieves a similar communication-ting complexity, SWIFT allows for periodic communication, uses only local memory, and does not require bounded-delay -elay assumption.
3 PROBLEM FORMULATION
Decentralized FL. In the FL setting, we have clients represented as vertices of an arbitrary communication graph 9 with vertex set V = {l,.... ......,,j n and edge set & S V x V. Each client i communicates with one-hop neighboring clients such that (i, E E. We denote the neighborhood for client as N₁, and clients work in tandem to find the global model parameters by solving:
min f(x) = Σ f((z), f((x) := :::::BB BE.DD [((2) E)],
Σp=1, P 202..
(1)
s=1
The global objective function f(x is the weighted average of all local objective functions f(()). In Equation 1, Pi, Vi E [n] denotes the client influence score. This term controls the influence of client i on the global consensus model, forming the client influence vector = )"1 These scores also reflect the sampling probability of each client. We note that each local objective function fi(x) is the expectation of loss function É with respect to potentially different local data & = (G.,) AM j=1 from each client i's distribution D;, i.e., E.j D, The total number of iterations is denoted as T.
Existing Inter-Client Communication in Decentralized FI.. All clients balance their individ- ual training with inter-client communications in order to achieve consensus while operating in decentralized manner. The core idea of decentralized FL is that each client communicates with its neighbors (connected clients) and shares local information. Balancing individual training with inter-client communication ensures individual client models are well-tailored to personal data while remaining (i) robust to other client data, and (ii) able converge to optimal consensus model.
Periodic Averaging. Algorithms such as Periodic Averaging SGD (PA-SGD) (Wang & Joshi, 2018) and Local Decentralized SGD (LD-SGD) reduce communication time by performing multiple local updates before synchronizing. This process accomplished through the use of communication set C., which defines the set of iterations client must perform synchronization,
C, = {t E N & mod (s + 1) = 0, & &<T7 T).
(2)
We adopt this communication notation, although synchronization unneeded in our algorithm.
SHARED WAIT-FREE TRANSMISSION (SWIFT) FEDERATED LEARNING
In this section, we present the Shared W Transmission (SWIFT) Algorithm. SWIFT is an asynchronous algorithm that allows clients to work at their own speed. Therefore, removes the dependency on the slowest client which is the major drawback of synchronous settings. Moreover, unlike other asynchronous algorithms, SWIFT does not require a bound on the speed of the slowest client in the network and allows for neighborhood averaging and periodic communication.
SWIFT Overview. Each client i runs SWIFT parallel, first receiving an initial model x,, communication set C., and counter + 1. SWIFT is concisely summarized in the following steps:
(0) Determine cient-communicattio weights w; via Algorithm 2 in Appendix B.2.
(1) Broadcast the local model to all neighboring clients.
(2) Sample a random local data batch size M.
(3) Compute the gradient update of the loss function E with the sampled local data.
(4) Fetch and store neighboring local models, and average them with one's own local model if c; E C.-
(5) Update the local model with the computed gradient update, well as the counter e C, + 1.
(6) Repeat steps (1)-(5) until convergence.
diagram and algorithmic block of SWIFT are depicted in Figure 1 and Algorithm respectively.
3

---

Published as a conference paper at ICLR 2023
Active Clients, Asynchronous Iterations, and the Local-Model Matrix. Each time client finishes pass through steps (1)-(5, one global iteration is performed. Thus, the global iter- ation t is increased after the completion of any client's averaging and local gradient update.
The client that performs the 1-th iter-
ation is called the active client, and is designated as is (Line 6 of Al- gorithm 1). There is only one ac-
Local Gradient Update
Wait-Free Model Communication
Client 1
Average
rive client per global iteration. All
Fetch & Average
Fetch
other client models remain unchanged during the /-th iteration (Line 16 of Algorithm 1). In synchronous algo- rithms, the global iteration increases only after all clients finish an update. SWIFT, which is asynchronous, in- creases the global iteration t after any client finishes update. In our anal- ysis, we define local-model matrix X E Rdx= as the concatenation of all local client models at iteration t for ease of notation,
Client 2
Average
Fetch & Average
Client 3
Client
Fetch & Average
Average
1 1 G
ZEG
3 4EG
Figure 1: SWIFT schematic with C. = C₁ (i.e., clients communi- cate every two local update steps).
X : [zi:.... ==A11 E Rx
Inspired by PA-SGD (Wang& & Joshi, 2018), SWIFT handles multiple local gradient steps before averaging models amongst neighboring clients (Line 10 of Algorithm 1). Periodic averaging for SWIFT, governed by dynamic client-communication matrix, is detailed below.
Algorithm 1: Shared Wa Free Transmission (SWIFT)
Input Vertex set V, Total steps T, Step-size 7, Client Influence Vector p. Distributions of client data D., Communication set C., Batch size M, Loss function l, and Initial model x n > =!!"
Output: : Consensus model 1
Initialize each client's 's local update counter + 1, Vi E V Obtain each client's 's new communication vector ii using Algorithm 2 for 1. 1....,77 do
if' network topology changes then
L Renew each client's 's communication vector wi using Algorithm
Randomly select an active client i, according to Client Influence Probability Vector p Broadcast active client's model z!, all its neighbors {k: w * 0, +i
Sample batch of active client i," 's local data c == [ mm J- from distribution Di,
Compute the gradient update: g(x;,, Si,) + Em= Vi St,
10
current step falls in the predefined communication set, iee. Ci E C, then Fetch and store the latest models {#f} from i,'s neighbors {k wi,k # 0, k + it)
11
Model average for the active client: F, 1+1/2 Ex wt wa
2 + w st.
12
13
else
Active client model remains the same: Zz, 1+1/2 t x
14
15
Model update for the active client: aftt + v4
1+1/2
Update other clients: 27, <- x/y. 4 + is
17
Update the active client's counter C; Cs. +1
Wait Free. The backbone of SWIFT is its wait-free structure. Unlike any other decentralized FL algorithms, SWIFT does not require simultaneous averaging between two clients or a neighborhood of clients. Instead, each client fetches the latest models its neighbors have sent it and performs averaging with those available (Lines 11-12 of Algorithm 1). There is no pause local training waiting for neighboring client to finish computations average with, making SWIFT wait-free.
Update Rule.
SWIFT runs parallel with all clients performing local gradient updates and model communication simultaneously. Collectively, the update rule can be written in matrix form as
x X'W! GG( S.
4

---

Published as a conference paper at ICLR 2023
where ry denotes the step size parameter and the matrix G( (i,) R is the zero- saro-padded gradient of the active model æf.- The entries of G(at, Si,) are zero except for the iş-th column, which contains the active gradient g 51.) Next, we describe the client-commuuication matrix W
Client- Client-Communne Communication Matrix. The backbone of decentralized FL algorithms is the client- communication matrix W (also known the weighting matrix). To remove all forms of synchroniza- tion and to become wait-free, SWIFT relies upon a novel coem--communiiation matrix W that is neither symmetric nor doubly-stochastie, unlike other algorithms in FL (Wang & Joshi, 2018; Lian et al., 80;8; Li et al., 2019; Koloskova et al., 2020). The result of a non-symmetric and non-doubly stochastic client-communicatioo matrix, is that averaging occurs for single active client in and not over a pair or neighborhood of clients. This curbs superfluous communication time.
Within SWIFT, a dynamic client-communication matrix is implemented to allow for periodic averag- ing. We will now define the active client-commmication matrix Wi, in SWIFT, where in is the active client which performs the I-th global iteration. W can be one of two forms: (1) an identity matrix W = In if Ct. & C. or (2) a communication matrix if Cr2 C, with structure,
W == In + (wi, - -i,)e,, wh, == [w]........ W. R.G. 1 E ER. Σ w = Was 2 1/n Vi. (5) j=1
The vector wi, E R denotes the active cllent-communniatiio vector at iteration 4, which contains the communication coefficients between client is and all clients (including itself). The client- communication coefficients induce a weighted average of local neighboring models. We note that wf is often sparse because clients are connected to few other clients only in most decentralized settings.
Novel Cilenn-Cmmmniiation Weight Selection. While utilizing non-symmetric and non- doubly-stochastic client-comman communicmmiiiiionnn matrix decreases communication time, there are technical difficulties when it comes guaranteeing the convergence. One of the novelties of our work is that carefully design a dilent-communication matrix W i, such that is symmetric and doubly-stochastic under expectation of all potential active clients i, and has diagonal values greater than equal to 1/n. Specifically, we can write
72
Es, [W]] = Σ Di [h + (w)) - -e)ee] In + Σ pi(w; e.)ee W
(6)
where, we denote W the expected client-communication matrix with the following form, 1), and [W*]a, = pyw for i +
[W"]s = 1 + (w
i j.
(7)
Note that W is column stochastic as the entries of any column sum to one. If we ensure that W is symmetric, then it will become doubly-stochastic. By Equation 7, W becomes symmetric if,
p = pews, Vi,j E V.
(8)
To achieve the symmetry of Equation 8, SWIFT deploys a novel pre-processing algorithm: the Communication Coefficient Selection (CCS) Algorithm. Given any client-influence vector Pi, CCS determines all communicionnii coefficients such that Equations 5 and 8 hold for every global iteration Unlike other algorithms, CCS focuses on the expected client-communication matrix, ensuring its symmetry. CCS only needs to run once, before running SWTFT. In the event that the underlying network topology changes, CCS can be run again during the middle of training. In Appendix B.2, we detail how CCS guarantees Equations 5 and 8 to hold.
The CCS Algorithm, presented in Appendix B.2, is a waterfall method: clients receive coefficients from their larger-degree neighbors. Every client runs CCS concurrently, with the following steps:
(1) Receive coefficients from larger-degree neighbors. If the largest, or tied, skip to (2).
(2) Calculate the total coefficients already assigned sw well the sum of the client influence
scores for the unassigned clients Sp.
(3) Assign the leftover coefficients 1 8 to the remaining unassigned neighbors (and self) in manner proportional to each unassigned client i's percentage of the leftover influence scores pi/ sp
(4) If tied with neighbors in degree size, ensure assigned coefficients won't 't sum to larger than one.
(5) Send coefficients to smaller-degree neighbors.
5

---

Published as a conference paper at ICLR 2023
5 SWIFT THEORETICAL ANALYSIS
Major Message from Theoretical Analysis. As summarized in Table I, the efficiency and effective- ness of decentralized FL algorithms depend on both the iteration convergence rate and communication time complexity: their product roughly approximates the total time for convergence. In this section, we will prove that SWIFT improves the SOTA convergence time of decentralized FL as it obtains SOTA iteration convergence rate (Theorem I) and outperforms SOTA communication-time complexity.
Before presenting our theoretical results, we first detail standard assumptions (Kairouz et al., 2021) required for the analysis.
Assumption 1 (Z-smooth global and local objective functions). (() Vf(u)ll S L [|+ vll
Assumption 2 (Unbiased stochastic gradient). Eg-D. [V(<x;)] V f((z)) for each i i V. Assumption 3 (Bounded inter-client gradient variance). The variance of the stochastic gradient is bounded for any x with client sampled from probability vector p and local client data & sampled from D, This implies there exist constants a. 2 0 (where = 0 in IID settings) such that: E, (z) V((())) < =²² Vi, Vi, RE-D, [V((()) Vé(x; S a² Vx.
As mentioned in Section 4, the use of a non mommmmmtttrc,, non-doubly-stochane issues in analysis. In Appendix C, we discuss properties of stochastic matrices, including symmetric and doubly-stochastic matrices, and formally define Pv. a constant related to the connectivity of the network. Utilizing our symmetric and Houbly-stochasee expected tlien-ccomuuiccttion matrix (constructed via Algorithm 2). we reformulate Equation 4 by adding and subtracting out W
matrix : causes
x++ X'W' + XWW, - W") -
Next, we present our first main result in Lemma 1, establishing client-communication error bound. Lemma 1 Sident-oommunication Error Bound), Following Algorithm 2, the product of the difference between the expected and actual client communication matrices is bounded as follows:
E
G
2 II 5
(Wy, bq - W In e.))| = O
0²
+
(1 (10)
M
Remark. One novelty of our work is that we are the first to bound the gliet-commmuicaate error in the asynchronous decentralized FL setting. The upper bound in Lemma is unique to our analysis because other decentralized works do not incorporate wait-free communication (Lian et al., 2017: Li et al., 2019; Wang & Joshi, 2018; Lian et al., 2018). Now, we are ready to present our main theorem, which establishes the convergence rate of SWIFT:
Theorem 1 (Convergence Rate of SWIFT). Under assumptions 1, 2 and 3 (with Algorithm 2), let A fz² -(("), step-size 7/, total iteration T, and average model n² be defined as
/ /M DS
MnnA,
T> LMB p
7 VTL+ VM
TL
Then, for the output of Algorithm I, it holds that
T-1 Σ
2/ T
2 1 1+
1921 20 Pv (0² +66 +62
(11)
T
VTM
Iteration Convergence Rate Remarks. (1) We prove that SWIFT obtains a O11 (T) iteration
convergence rate, matching the optimal rate for SGD (Dekel et al., 2012; Ghadimi & Lan, 2013; Lian et al., 2017; 2018). (2) Unlike existing asynchronous decentralized SGD algorithms, SWIFT's iteration convergence rate does not depend on the maximal bounded delay. Instead, we bound any delays by taking the expectation over the active client. The probability of each client i being the active client is simply its sampling probability p.. We therefore assume that each client i is expected to perform updates at its prescribed sampling probability rate pi. Clients which are often delayed in practice can be dealt with by lowering their inputted sampling probability. (3) SWIFT converges in fewer total iterations T with respect to total clients compared to other asynchronous methods (Lian et al., 2018) (T = ((ntppmaz) in SWIFT versus T = 2(n*)) in AD-PSGD). Similar to AD-PSGD, SWIFT achieves linear speed-up in computational complexity as the number of clients increase.

---

Published as a conference paper at ICLR 2023
Communication-Time Complexity Remarks. Due Due to its asynchronous nature, SWIFT achieves a communication complexity that relies only on each client's 's own communication time per round E, This improves upon synchronous decentralized SGD algorithms, which rely upon the communication time per round of the slowest neighboring client maxjex; E9 (2) Unlike AD-PSGI) (Lian et al., 2018), which also achieves communication-tinn complexity reliant C; SWIFT incorporates periodic averaging which further reduces the communication complexity from 'I' rounds of communication [Ca]. Furthermore, SWIFT allows for entire neighborhood averaging, and not just one-to-one to-oneo-eeeeee-o gossip averaging. This increases neighborhood information sharing, improving model robustness and reducing model divergence.
Corollary (Convergence under Uniform Client Influence). In the common scenario where client infiuences are uniform. P; = 1/n Vi = Pmaz 1/n, SWIFT obtains convergence improvements: total iterations T with respect to the number of total clients n improves to T 12(n²) as compared to T (2nnt))(nr for AD-PSGD under the same conditions.
6 EXPERIMENTS
Below, we perform image classification experiments for a range of decentralized FL algorithms (Krizhevsky et al., 2009). We compare the results of SWIFT to the following decentralized baselines:
The most common synchronous decentralized FL algorithm: D-SGD (Lian et al., 2017).
Synchronous decentralized FI. communication reduction algorithms: PA-SGD (Wang & Joshi, 2018) and LD-SGD (Li et al., 2019).
The most prominent asynchronous decentralized FL algorithm: AD-PSGD (Lian et al., 2018).
Finer details of the experimental setup are in Appendix A. Throughout our experiments we use two network topologies: standard ring and ring cliques (ROC). ROC-xC signifies a ring of cliques with clusters. The ROC topology is more reflective of realistic network, as networks usually have pockets of connected clients. These topologies are visualized in Figures and respectively.
6.1 BASELINE COMPARISON
To compare the performance of SWIFT to all other algorithms listed above, we reproduce exper- iment within (Lian al., 2018). With no working code for AD-PSGD to run on anything but an extreme supercomputing cluster (Section 5.1.2 of (Lian et al., 2018)), reproducing this experiment allows us to compare the relative performance of SWIFT to AD-PSGD.
Decentralized FL
15 Client Ring
Algoritlmss
Epoch (s)
Change
Comm,
Change
SWIFT (C,) )
1.019
-3460
0.086
-86.28
D-SGD (Cc) )
1.558
0.627
TABLOAD
AD.PSGD' (C.)
-15.66
SWIFT
1.016
-34.99
0.064
-89.79
LD-SGD (C.)
1,320
-15.28
0.428
-31.74
PA-SGD (C.)
1,281
-17.78
0.358
-42.00
AD-PSCD come from Table 4 (n ct 2018).
(a) Average epoch and communication times.
(b) Average test loss.
(c) Average train loss.
Figure 2: Baseline performance comparison on CIFAR-10 for 16 client ring.
Table in Figure 2a showcases that SWIFT reduces the average epoch time, relative to D-SGD, by 35% (Co and C1). This far outpaces AD-PSGD (as well as the other synchronous algorithms), with AD-PSGD only reducing the average epoch time by 16% relative D-SGD. Finally, Figure displays how much faster SWIFT achieves optimal train and test loss values compared to other decentralized baseline algorithms. SWIFT outperforms all other baseline algorithms even without any slow-down (which we examine in Section 6.2), where wait-free algorithms like SWIFT especially shine.
6.2 VARYING HETEROGENEITIES
Varying Degrees of Non-IIDness Our second experiment evaluates SWIFT'S efficacy converging to well-performing optima under varying degrees of non-IIDness. We vary the degree (percentage) of each client's data coming from one label. The remaining percentage of data is randomly sampled (IID) data over all labels. A ResNet-18 18 model is trained by 10 clients in 3-cluster ROC network topology. We chose 10 clients to make the label distribution process easier: CIFAR-10 has 10 labels.
7

---

Published as a conference paper at ICLR 2023
As expected, when data becomes non-IID, the test loss becomes higher and the overall accuracy lower (Table 2). We do see, however, that SWIFT converges faster, and to a lower average loss, than all other synchronous baselines (Figure 3). In fact, SWIFT with C₁ converges much quicker than the syn- chronous algorithms. This is an important result: SWIFT converges both quicker and to smaller loss than synchronous algorithms in the non-IID setting.
Deventralized FL.
10 Client Ring of Clisuas -3 Closter Topelogy
Algorithms
Epoch Time (s)
Communication Time (5)
SWIFT (Cs)
1.709
0.197
D-SGD (Cp)
2.116
0.705
SWIFT (C.)
1.517
LD-SGD (C,)
1,973
0.575
PA-SOD (C))
1,929
0.421
Table 2: Average epoch and communication
times for non-lll setting on CIFAR-10.
D-50B
30D
D-5Gn
LI--CD
LE-S2D
LE-SGD
SAIFT
SW
SHIFT
SMIFT
SWIFT SODS
SOT
SWIFT 12 SKO
16
0Gl clakk Tiex (15iae))
Watkebok Time (Milate))
90. Jack Time (Mlitte
Well clak Tean (MTaatin)
(a) 1/4 dogree non-IID data.
(b) 1/2 dogree non-IID data.
(c) 7/10 degree non-lID data.
(d) 9/10 dogree nea-llD data.
Figure 3: Average test loss for varying degrees of non- son-IIDness on CIFAR- 10, 10 client ROC-3C.
Varying Heterogeneity of Clients In this experiment, we investigate the performance of SWIFT under varying heterogeneity, or speed, of our clients (causing different delays). This is done with 16 clients in ring topology. We add artificial slowdown, suspending execution of one of the clients such that it takes a certain amount of time longer (slowdown) to perform the computational portions of the training process. We perform tests in the four times (4x) as slow as usual. We then compare how the decentralized algorithms fare under these circumstances compared to the normal setting with added slowdown.
where a client is two times (2x) and
Decentralzzed FL
No Slowdown
2x Slowdown
4x Slowdown
Algocishms
Total (s)
Epach (s)
Comm. (s)
Total (4)
Epach (s)
Comm. (s)
Total (4)
Epoch (s)
Comm. (s)
SWIFT (Co)
LA33
0.087
2.451
0.964
3.054
1,117
D-SGD (Ca)
3,110
1.45
0.564
3.972
1,571
0.616
6.137
1.666
0.651
SWIFT (C2)
2.44
0
0,061
2.152
0.928
0,040
2.847
1,074
0.065
LDXSGD (C.)
3.323
1.353
0.413
3.762
1.389
0.428
5.917
1.412
0.448
PA-SGD (C,)
3.183
1,270
0,331
3,557
1.262
0.309
5.743
1,270
0.318
Table 3: Average epoch and communication times on CIFAR- 10 for 16 client ring with slowdown.
In Table 3, the average epoch, communication, and total time is displayed. Average total time includes computations, communication, and any added slowdown (wait time). SWIFT avoids large average total times as the slowdown grows larger. The wait-free structure of SWIFT allows all non-slowed clients to finish their work at their own speed. All other algorithms require clients to wait for the slowest client to finish mini-batch before proceeding. At large slow- downs (4x), the average total time for SWIFT is nearly half of those for synchronous algorithms.
D-RGD
DAGD
SWIFT C-SSEN
SWEFT 23SCCA
TU ENN
SWIFT SAIPT 20
SWIFT 2ARDA 20
SWIPTCEO
SWIET
SVIFT
SAIRT CLAEOL AG
05
Walddack Tea (Mtaai
Bicckkkk Tiao (Mllaro
(a) Test loss slowdown.
(b) slowdown.
Figure 4: SWIFT vs. D-SGD for CIFAR-10 in 16 client ring with varying slowdown.
Thus. SWIFT is very effective reducing the run-time when clients are slow within the network.
Figure 4 shows how SWIFT able to converge faster to an equivalent, or smaller, test loss than D-SGD for all slowdowns. In the case of large slowdowns (4x), SWIFT significantly outperforms D-SGD, finishing in better than half the run- time. We do not include the other baseline algorithms to avoid overcrowding of the plotting space. However, SWIFT also performs much better than PA-SGD and LD-SGD as shown in Table 3. These results show that the wait-free structure of S SWIFT allows to be efficient under client slowdown.
8

---

Published as a conference paper at ICLR 2023
6.3 VARYING NUMBERS OF CLIENTS & NETWORK TOPOLOGIES
Varying Numbers of Clients In our fourth experiment, we determine how SWIFT performs versus other bascline algorithms as In Table 4, the time per epoch for SWIFT drops by nearly the optimal factor of the number of clients is doubled. For all algorithms, there bit of parallel overhead when the number of clients is small, however this becomes min- imal the number of clients grow be large (greater than 4 clients). In comparison to the syn- chronous algorithms, SWIFT actually decreases its communication time as the number of clients increases. This allows the parallel performance to be quite efficient, as shown in Figure 5,
vary the number of clients.
(a) Communication time.
(b) Epoch time.
Figure 5: Average communication and epoch times for increasing numbers of clients.
Decentralized FL
Client Ring
Client Ring
Client Ring
2 Client Ring
Algorithms
Epoch
Comm. (s) Epoch (s)
Comm. (s)
Epoch (s)
Comm. (s)
Eguch (s)
Comm, (s)
SWIFT (Ca)
6.971
0.251
D-SGD (Cn)
7.62
SWIFT (C:)
0.232
0.176
LD-SGD (C,)
1,320
0.428
2.217
0.345
3.946
0.300
6.712
0.179
PA-SGD (Ci)
1,281
0.358
2.093
0.285
3.871
0,220
7,303
0.180
Table 4: Average epoch and communication times on CIFAR-I0 with varying clients in ring topology.
Varying Topologies Our fifth experiment ana- lyzes the effectiveness of SWIFT versus other baseline decentralized algorithms under different, and more realistic, network topologies. In this experiment setting, train 16 clients varying network topologies (Table and Figure 6).
Decentralized FL
16 Client ROC-2C
16 Client ROC-4C
16 Client Ring
Algorithms
Epoch (s)
Comm. (s)
Epoch (s)
Comm, (8)
Epuch (s)
Comm, (6)
SWIFT (Cs)
1.793
0.416
1,291
0.124
1.367
0.121
D-SGI (Ca)
2.799
1.479
1.464
0.962
SWIFT (C,)
1.611
0.295
1.494
0.174
1.348
0.085
LD-SGD (C,)
2.408
0.987
2.525
1.105
2.172
0.517
PA-SGD (C))
2.639
0.765
2,216
0.708
1.982
0.500
Table 5: Average epoch and communication times on CIFAR-10 for varying network topologies.
D SCD $CD
D D-DGD SCD
D B.D LD-SGD
SWIFT SWIET
SMIPT
Tos
1.3
TecTank
1.3
SCE)
0.-
0.-
05-
Wud--tock Time Diiaac
WaB-ciec Thmc (MEazz))
Welcked Than
(a) ROC-2C (n = 16).
(b) ROC-CC (n 16).
(c) Ring (n = 16).
Figure 6: Average test loss for varying network topologies on CIFAR-10.
7 CONCLUSION
SWIFT delivers on the promises of decentralized FL: a low communication and run-time algorithm (scalable) which attains SOTA loss (high-performing)) As a wait-free algorithm, SWIFT is well- suited to rapidly solve large-scale distributed optimization problems. Empirically, SWIFT reduces communication time by almost 90% compared to baseline decentralized FL algorithms. In future work, aim to add protocols for selecting optimal client sampling probabilities. We would like to show how varying these values can: (i) boost convergence both theoretically and empirically, and (ii) improve robustness under local client data distribution shift.

---

Published as a conference paper at ICLR 2023
8 ETHICS STATEMENT
We propose novel wait-free decentralized Federated Learning algorithm with strong theoretical guarantees and improved empirical results. Our contributions add to the sparse foundational literature in asynchronous decentralized Federated Learning. Therefore, our work does not have direct societal or ethical consequences. We would like note that it is imperative for users of Federated Learning algorithms in real-world distributed learning applications to respect data privacy.
REPRODUCIBILITY
Our code can be found on GitHub https: /github. ctcchuubccomm. com/und- haand-hhang--- wtallabb//swr. We ran five trials for SWIFT and each baseline algorithm we compared it to with random seeds over each experiment (Sections 6.1, 6.2, 6.2, 6.3). Our plots include error bars from these five trials for each experiment. As stated in Section 6, we perform image classification experiments on the CIFAR-10 dataset (Krizhevsky et al., 2009). In Table 6 we describe the hyperparameters we use in all experiments. Appendix A describes further experimental setup details (computational resources used, how we partition data, and more). Finally we provide pseudocode for SWIFT in Algorithm
10 ACKNOWLEDGMENTS
Bornstein, Rabbani and Huang acknowledge support by the National Science Foundation NSF-IIS- FAI program, DOD-ONR-Offic of Naval Research, DOD-DARPA-Defensse Advanced Research Projects Agency Guaranteeing AI Robustness against Deception (GARD), Adobe, Capital One and JP Morgan faculty fellowships. Rabbani is additionally supported by NSF DGE-1632976. Bedi acknowledges the support by Army Cooperative Agreement W91 W991NNF212077 Bornstein additionally thanks Michael Blankenship for both helpful discussions regarding parallel code implementation and inspiration for SWIFT'S name.
REFERENCES
Soheil Abbasloo and H Jonathan Chao. Sharpedge: An asynchronous and core-agnostic solution to guarantee bounded-delays. CCF Transactions on Networking, 3(1):35-50, 2020.
Alekh Agarwal and John Duchi. Distributed delayed stochastic optimization. Advances in neural information processing systems, 24, 2011.
Tuncer Can Aysal, Mehmet Ercan Yildiz, Anand D Sarwate, and Anna Scaglione. Broadcast gossip algorithms for consensus. IEEE Transactions on Signal processing. 57(7):2748 2761, 2009.
Amrit Singh Bedi, Alec Koppel, and Ketan Rajawat. Asynchronous online learning in multi-agent systems with proximity constraints. IEEE Transactions on Signal and Information Processing over Networks, 5(3):479 2019a.
Amrit Singh Bedi, Alec Koppel, and Ketan Rajawat. Asynchronous saddle point algorithm for stochastic optimization in heterogeneous networks. IEEE Transactions on Signal Processing, 67 (7):1742-1757, 2019b.
Aurélien Bellet, Anne-Marie Kermarrec, and Erick Lavoie. D-cliques: Compensating for data heterogeneity with topology in decentralized federated learning. 2021.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Gossip algorithms: Design, analysis and applications. In Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies, volume 3, pp. 1653-1664. IEEE, 2005.
Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions information theory, (2(6))2508-255) 2006.
10

---

Published as a conference paper at ICLR 2023
Xuanyu Cao and Tamer Başar. Decentralized multi-agent stochastic optimization with pairwise constraints and quantized communications. IEEE Transactions on Signal Processing, 68:3296- 3311, 2020. doi: 10.1 LLL.1999TTSP22222999999999
Ofer Dekel, Ran Gilad-Bachrach, Ohad Shamir, and Lin Xiao. Optimal distributed online prediction using mini-batches. Journal of Machine Learning Research, 13(1), 2012.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341 0112231123366 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1):267-305
2016.
István Hegedfs,, Gábor Danner, and Márk Jelasity. Decentralized learning works: An empirical com- parison of gossip learning and federated learning. Journal of Parallel and Distributed Computing. 148:109-124: 2021.
Beomyeol Jeon, SM Ferdous, Muntasir Raihan Rahman, and Anwar Walid. decentralized aggregation for federated learning. In IEEE INFOCOM 2021 IIEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS), pp. 1-6. IEEF, 2021.
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 in federated learning. Foundations and Trends@ in Machine Learning. 14(1-2):1-215 2021.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized sgd with changing topology and local updates. In International Conference on Machine Learning, pp. 5381-5393 PMLR, 2020.
Anastasia Koloskova, Sebastian U Stich, and Martin Jaggi. Sharper convergence guarantees for asyn- chronous sgd for distributed and federated learning. Advances in Neural Information Processing Systems 35 (NeurIPS 2022), 2022.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
He Li, Kaoru Ota, and Mianxiong Dong. Learning iot in edge: Deep learning for the internet of things with edge computing. IEEE network, 92(1):96-1011 2018.
Xiang Li, Wenhao Yang. Shusen Wang, and Zhihua Zhang. Communication-effiieenn local decentral- ized sgd methods. arXiv preprint arXiv:1910.091 2019.
Xiangru Lian, Yijun Huang, Yuncheng Li, and Ji Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in Neural Information Processing Systems, 28, 2015.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. Advances in Neural Information Processing Systems, 30. 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, pp. 3043-3052. PMLR, 2018.
Qi Liu, Bo Yang, Zhaojian Wang, Dafeng Zhu, Xinyi Wang, Kai Ma, and Xinping Guan. Asyn- chronous decentralized federated learning for collaborative fault diagnosis of pv stations. IEEE Transactions on Network Science and Engineering, 2022.
Qinyi Luo, Jiaao He, Youwei Zhuo, and Xuehai Qian. Prague: High-performance heterogeneity-awar asynchronous decentralized training. In Proceedings of the Twenty-Fifhh International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 401-416, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera Arcas. Communication learning of deep networks from decentralized data. In Artificial intelli- gence and statistics, pp. 2272-1282. PMLR, 2017.
11

---

Published as a conference paper at ICLR 2023
Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth. Asynchronous sgd beats minibatch sgd under arbitrary delays. In NeurlPS 1222-Thitty-sxxth Conference on Neural Information Processing Systems, 2022.
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,
2021.
Angelia Nedié and Alex Olshevsky. Distributed optimization over tare-ng directed graphs.
IEEE Transactions Automatic Control, 60(3):601-613 2014.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54(1 (:81))48-48 61, 2009.
Yurii Nesterov. Introductory lectures on convex programming volume i: Basic course, 1998.
Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu. Hogwild!: A lock-free approach to parallelizing stochastic gradient descent. Advances neural information processing systems, 24, 2011.
Stefano Savazzi, Monica Nicoli, and Vittorio Rampa. Federated learning with cooperating devices: A consensus approach for massive iot networks. IEEE Internet of Things Journal, ((5):441146654 2020.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of communication--ffiiieenn sgd algorithms. arXiv preprint arXiv: 07576, 2018.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang. Gauri Joshi, and Soummya Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. In 2019 Sixth Indian Control Conference (ICC), pp. 299-300. IEEE, 2019.
Hao Ye, Le Liang, and Geoffrey Ye Li. Decentralized federated learning with unreliable communica- tions. JEEE Journal of Selected Topics in Signal Processing, 2022.
12

---

Published as a conference paper at ICLR 2023
Supplementary Material
A ADITIONAL EXPERIMENTAL DETAILS AND SETUP
A.1 COMPUTATIONAL SPECIRICATIONS
We train our consensus model on network of nodes. Each node has an NVIDIA GeForce RTX 2080 Ti GPU. All algorithms are built in Python and communicate via Open MPI, using MPI4Py (Python bindings for MPI). The training is also done in Python, leveraging Pytorch.
A.2 DATA PARTITIONING
For all experiments, the training set is evenly partitioned amongst the number of clients training the consensus model. While the size of each client's partition is equal, we perform testing with data that is both (1) independent and identically distributed (iid) among all clients and (2) sorted by class and is thus non-iid. For the iid setting, each client is assigned data uniformly random over all classes. In the non-iid setting, each client is assigned a subset of classes from which it will receive data exclusively. The classes are assigned in the following steps:
(1) The class subset size for all clients, is determined as the ceiling of the number of classes per
client n. [ Each class & within the class subset will take up 1/ne of the client's total data partition if possible.
(2) The classes within each client's class subset are assigned cyclically, starting with the first client. The first client selects the first n. classes, the second client selects the next ne classes, and so on. Classes can, in some cases, be assigned to multiple clients. If the final class has been assigned, and more clients have yet to be assigned any classes, classes can be re-assigned starting at the first class. (3) Each client is assigned data from the classes in their class subset cyclically (1/n, of its partition for each class), starting with the first client. If no more data is available from specific class, the required data to fill its fraction of the partition is replaced by data from the next class.
Since follow this data partitioning process within experiments, each client is assigned equal partitions of data. Therefore, following the works (Lian et al., 2018; Wang et al., 2019; Ye et al., 2022; Li et al., 2019), set the client influence scores to be uniform for all clients pt 1/n Vi E V.
A.3 EXPERIMENTAL SETUP
Below provide information into the hyperparameters select for our experiments in Section 6.
Experiment Type
Model
Epochs E'
Decay (Rate, E, Frey.)
M
Weight Decay
Momentum
Baseline
ResNet-18 18
200
0.1
(1/10, 81 & 122, Single)
32
10
0.9
Vary non- ITDess
ResNet- 18
300
0.8
(1/2, 200. 10)
32
10
0.9
Vary Heterngeneity
ResNet- 18
100
0.1
(1/2, 50, 10)
32
10
0.9
Vary Clients
ResNet-18 18
200
0.1
(1/10, 81 & 122, Single)
32
10-h
0.9
Vary Topology
200
0.1
(1/2, 100. 10)
10
0.9
Table 6: Hyperparameters for all experiments.
In Table 6, one can see that the step-size decay column is split into the following sections: rate, E, and frequency. The rate is the decay rate for the step-size. For example, in the Baseline row, the step-size decays by 1/10. The term E is the epoch which decay begins during training. For example, in the Baseline row, the step-size decays at E = 81 and 122. Frequency simply how often the step-size decays. For example, in the Vary Topology row, the step-size decays every 10 epochs.
13

---

Published as a conference paper at ICLR 2023
A.4 NETWORK TOPOLOGIES
Ring Topology. Please refer to Figure? 7.
det
Qet
Figure 7: An 8 Client Ring.
Ring of Cliques Topology. Please refer to Figure 8.
Figure 8: (Left) 10 Client, 3-Cluster. (Middle) 16 Client, 2-Cluster. (Right) 16 Client, 4-Cluster.
Like the works of (Jeon et al., 2021; Bellet al., 2021), believe that the ring of cliques network topology is realistic topology in the decentralized setting. In many real-world setting, like one's home (smart appliances, smart speakers/displays, phones, etc.), devices connected together in small clique. Only small amount of these devices have connections to other devices outside the cluster (like phone or router). We wanted utilize this network topology due this realistic nature. Furthermore, (Bellet et al., 2021) shows that ring of clique topology can be used in the decentralized setting to reduce the impact of label distribution skew.
B ALGORITHM DETAILS AND NOTATION
B. NOTATION TABLE
Definition
Notation
Definition
Notation
Global Iteration
Number Clients
Active Client a
i
Parameter Dimension
Client (f.j) Communication Coefficient at
wf.
Data Dimension
f
Local Model of Client
< Rd
Step-Size
Y
Local Model of Active Client
zf. Rd
Total SWIFT Iterations
Mini-Batch Data from Active Client at
s/.
Mini-Batch Size (Uniform)
M
Gradient of the Active Model t
g( &t Rd
Communication Set
C,
Client i Communication Vector
of E m
Global Data Distribution
D
Local Model Matrix at &
X E Rddon
Global Objective
(ar
Zero-Padded Gradient of the Active Model at
G(x), cf ) E Rd
Client Influence Score
Expected Local Model Gradients
G(Xt, g*) Rdxa
Client Influence Vector
R"
Active Client Communication Matrix at
W Raxa
One-Hot Vector
R
Expected Client Communication Matrix
W Raxn
Identity Matrix
1, E IR
14

---

Published as a conference paper at ICLR 2023
Algorithm 2: Communication Coefficient Selection (CCS)
Input CCient Influence Score (CIS) pj IR, Client Degree d, R, Client Neighbor Set J; = {Vj client j is one-hop neighbor of client i), Vi
Output :empuut:Cleenni --w.ell-eCoominn Coneen-Commmniiationn Vector Wy IR Vi E [r]]
for i =: n in parallel do
CIS are non-uniform then
L Initialize Client-Communne
Vector w; [w1,6 W2,1 Wn,e] t- (1/n)e,
else
1. Initialize Client- Communication Vector w; = [u1,i, "2,61 Wnnel k-
Exchange CIS and degree with all neighbors
Store Neighbor CIS Vector PJ [ppbeale Rd
Construct Neighbor Subsets Jt, _SE JE C J, as subsets of i's neighbors with degree larger than, no larger than and equal to d; respectively for Vj J do
10
Wait to fetch Wi, from neighbor client j with a degree larger than d;
Determine the sum of the total coefficients assigned (TCA) s' f- Em=1 Wm, if [i|JSE| > 0 then
11
12
Determine the sum of all remaining neighbors' CIS sp + EjEJst Pj
13
if [J > 0 then
Exchange s and sy with all neighbors j E JE, storing all exchanged si Store % < max 8/c) and 8p +- max op) Vj JE
Set Wjei (1- Vj E JE
17
Recompute 8 Em=1 Wm.s and EjE(SEUNN Pj
(1 (1
19
Set W/,s < W3 +
Vj {JSE Ui} \ JE for all remaining neighbors
Send Wij (1 (1-
to all waiting neighbors j E JSE, JE
20
21
else
22
W4.1 s
B.2 SWIFT PRE-PROCESSING: SETTING CLIENT-COMMUNICATIO WEIGHTS
Below we present the the algorithmic pseudocode here for our novel algorithm Algorithm 2. As a note, we include different cliet-commmnication vector initializations if the client influence scores are uniform versus non-uniform. The reason for this is to ensure that the selfweight for each client i, Wi,s has a value greater than 1/n. This naturally occurs when the CIS uniform, however is not when they non-uniform.
selection
In Algorithm terms 8u and 8p play a pivotal role in satisfying Equations and 8 respectively. Equation 8 is satisfied by assigning weights amongst client and its neighbors as follows
(w-8w)p
Pj
p:
(12)
Assigning weights proportionally with respect neighboring client influence scores and total neighbors ensures higher influence clients receive higher weighting during averaging.
B.3 OPTIMAL STEP-SIZE UNDER UNIFORM CLIENT INFLUENCE
The defined step-size 7 and total iterations 2' for SWIFT is
M < V TL
Mn² D
7:= +TL+ MM
T> 193 LM Ayp2n P
LM32LMM
15

---

Published as a conference paper at ICLR 2023
Therefore, be rewritten as
Mn
7 yS
(1932 spn neennrpPmaa Pmax) )T
1932 1.2 2 Pma
When the client influence scores are uniform (i.e, Ps = 1/n n Vi E V), one can see that our step-size becomes
7= 7=0 (
This mirrors the optimal step-size in analysis of gradient descent convergence first-order stationary points L) (Nesterov, 1998).
B.4 INSTANTANEOUS COMMUNICATION AND OVERCOMING COMPUTATIONAL DELAY
Similar AD-PSGD (Lian et al,, 2018), we assume that model transmission is instantaneous between clients. Within (Lian et al., 2018), two algorithms (Algorithms 2 and 3) are provided within the appendix to provide realistic multi-thread implementation of Algorithm 2 is explicitly told to wait at Line until the gradient buffer is empty. Unless gradient queue utilized, which alters the effective batch-size from the constant M, the computational thread must wait for model transmission if there exists communication delay. Important future work for SWIFT, and within the field of asynchronous decentralized FL in general, is to remove this instantaneous delay assumption and build protocols overcome it (and theoretically guarantee convergence in its presence).
AD-PSGD. The computational thread
We would like to mention that eliminating computational delay is key novelty of SWIFT. Delayed computations are handled by SWIFT through its communication matrix. Unlike AD-PSGD, no model overwriting can
while client performing gradient computations (Line 9 of Algorithm 1). This only occurs due to our novel non-doubly stochastic communication matrix. Therefore, client will never be computing gradients with delayed model. This, of course, assumes that model transmission is instantancous.
SWIFT deals with a slow client (having delayed computations) by allowing a faster client j reuse stored model of client until client i finally finishes its model update. The stored model is still up delayed) since client has finished its gradient computations, updated its model,
date (and and sent out its updated model to neighboring clients (as it experiences delayed computations). If client has not received a message from a neighbor, then their stored model for that neighbor is still its most up-to-date model.
C PROPERTIES OF COMMUNICATION MATRICES
Stochastic Matrices. Within work, we non-symmetric, non-doubly-stochail matrix W for client averaging. Utilizing W comes with analysis issues (it is non-symmetric), however provides the wait-free nature of SWIFT. Interestingly, W does have some unique properties: is column-stochaste Lemma 3 proves that the product of stochastic matrices converges exponentially stochastic vector with common ratio [0, 1).
Symmetric and Doubly-Stochastee Matrices. As mentioned Section 5, we utilize Algo- rithm to select client weights such that have symmetric and doubly-stochastic commu- nication matrix T under expectation. By Lemma 2, there exists a scalar E [0, 1) such that max ( (WW"TW" |A, ((W*)T"'')) S p. Vt. This parameter P reflects the connectivity of the underlying graph topology. The value of is inversely proportionate how fast information spreads in the client network. small value of p results in information spreading faster (p = in centralized settings).
16

---

Published as a conference paper at ICLR 2023
Within our analysis, we denote the parameter Pvr combination of and
Pv = n1
vP + (1- v2)
384
(13)
12
2(1 pp p)
(1 /p-
D REVIEW OF EXISTING INTER-CLIENT COMMUNICATION IN DECENTRALIZED FL
The predecessor to decentralized FL is gossip learning (Boyd et al., 2006; Hegedds et al., 2021) I). Gossip learning was first introduced by the control community to assist with mean estimation of decentrally-hosted data distributions (Aysal et al., 2009; Boyd et al., 2005). Now, SGD-based gossip algorithms are used to solve large-scale machine learning tasks (Lian et al., 2015; 2018; Ghadimi et al., 2016; Nedic & Ozdaglar, 2009; Recht et al., 2011; Agarwal & Duchi, 201 1). A key feature of gossip learning is the presence of globally shared oracle/memory with whom clients exchange parameters at the end of training rounds (Boyd et al., 2006). While wad/wwite-accessiie well-suited for a single-organization ecosystem (i.e. all clients are controllable and trusted), this unrealistic for more general odge-based paradigms. Below, we review newer decentralized SGD algorithms, such as D-SGD (Lian et al., 2017), PA-SGD (Wang Joshi, 2018), and LD-SGD Li et al. (2019). These algorithms theoretically and empirically outperform their centralized counterparts, especially under heterogeneous client data distribution.
shared memory is
Decentralized SGD (D-SGD) (Lian et al. 2017) One of the foundational decentralized Federated Learning algorithms is Decentralized SGD. order to minimize Equation 1, D-SGD orchestrates local gradient step for all clients before performing synchronous neighborhood averaging. The D-SGD process for a single client is defined as:
(14)
The term g(x5,, {)) denotes the stochastic gradient of 2 with mini matih data E sampled from the local data distribution of client j. The matrix W is weighting matrix, where W;; is the amount of xx-1 which will be made up of client j's local model after one local gradient step (e.g. if Wa, = 1/2, then half of 2 will have been composed of client j's model after its local gradient step). The weighting matrix only has a zero value Wi, = if clients i and j are not connected (they are not generally selected ahead of time by central
within the same neighborhood). The values of Wi host, with the usual weighting scheme being uniform. In D-SGD, model communication occurs only after all local gradient updates are finished. These gradient updates computed in parallel.
Periodic Averaging SGD (PA-SGD) (Wang & Joshi, 2018) The Periodic Averaging SGD algorithm is an extension of D-SGD. In order save communication costs when the number of clients grows to be large, PA-SGD performs model averaging after an additional I local gradient
steps. Thus, the communication set for PA-SGD defined
C₁ {t N t mod (I1 + 1) 0}.
The special case of I 0 reduces D-SGD, The PA-SGD process for single client i is defined as:
Σ j=1 W [z] g( {)), t x
++1
(15)
{))
otherwise.
Compared with D-SGD, PA-SGD still suffers from the inefficiency of having to wait for the slowest client for each update. However, PA-SGD saves communication costs by reducing the frequency of communication.
Local Decentralized SGD (LD-SGD) (Li al., 2019) Continuing to generalize the foundational decentralized Federated Learning algorithms is Local Decentralized SGD. LD-SGD generalizes PA-SGD by allowing multiple chunks of singular D-SGD updates, described in Equation 14, in between the increased local gradient steps seen in PA-SGD. The number D-SGD chunks is dictated by parameter Tz.
17

---

Published as a conference paper at ICLR 2023
Wall clock time
Node
Node
Node 3
Node 4
Node
12
Figure 9: I1 Depiction (from (Li et al., 2019)).
In this case, the communication set for LD-SGD is defined as
C1,,12 -U 4111 - {t e N mod (i + 1) 0}
if 1 0, if 11 0.
For example, in the case 1 = 3, 12 = 2, LD-SGD will take three local gradient steps and then perform two D-SGD updates (which consists of local gradient step and then averaging) shown in Figure 9. The special case of I2- reduces to PA-SGD. The LD-SGD process for a single client i is defined
Perform Ej=1 Wiy [=] [D), t C,1,12 at g( {
(16)
otherwise
In the literature, there also exist other asynchronous decentralized learning methods such as in Cao Başar (2020); Bedi et al. (2019a;b) but they limited to convex objectives and hence not applicable to the setting in our work.
E PROOF OF THE MAIN THEOREM
Before beginning, we quickly define the expected gradient E,, [G(z) (2;)
G(xt, ,4) = E,, [G {t) Σ p.G(
(17)
Proof of Theorem 1. In this theorem, we characterize the convergence of the average of all local models. Using the Gradient Lipschitz assumption with Equation 9 yields
X
1n
X
1n
X'1n X'(W, - W G(,,,
+
X*W;
WOL1
G(at, : Sh
+
(18)
We first denote the average over all local models as कt = X'1n Taking the expectation with respect to the updating client i, yields
VI(T") X'(W" Wy In n
1( <s(x)) +
-0(X1 Sa.t)
n
L
x'( w/y 1n GG( ctre)
1n
E.
(19)
2
V)(E9) -GG(X' E.,)) 1n
=f((') +
X'(Wi, wo G ct:
1n
(20)
2
18

---

Published as a conference paper at ICLR 2023
M
=f(3') +
VI(("),
V V Sm, Sm,,))))
Mn
1=1 m=1
+ 2
1
Rig
x'(W,, -
In
G c/:
1n n
2
(21)
n
M
=s(x') - 7 ((())) Mn
Pa V
V((x sm,e)
T. R X' /r) In 2
1n n
2
G ch:
(22)
n
Taking the expectation over all local data EE-D, yields
- - 7
(V((T))
Σ p. (iV(((ttt)
i=1
L De
XW wy
Go stt
In
2
(23)
n
71
By properties of the inner product
f(a(t1)- - -(()) s
2 2n
1 +
Σ PiVsf((tt)
n - -V((E)) Σ
ps P.V.RGGS
L RewDis
X'(,,
Wy In G(al Eliee
1n
+ 2
(24)
Bounding Term A: Given the update equation, term A can be transformed into
Bg ((
x (W", W*) GG(x), st:,,)
1n
n Eg (
1n
2
(25)
n2
Due to the symmetric and doubly stochastic property of W this reduces to
EEWDint
|| - 0²11² = EEnDii
(x x²) EgNDrnk 1 (0(t) - =x/)
(26)
1 BenDinke |1 -xt, 11?
(27)
2²
S BEWDiid || - 112 + || - 11 + +1112t11 x 2T112)
3
(28)
n²
Combining like terms yields
(1 EE-D.. || - 3²11 - n
BEDD.. | - x++1 1|2 + || - 21,11 -
(29)
n
Since n (we assume at least devices are running the algorithm) we find the following result
RE-Diin | - 2²112 5 (n² -3-3) 3) BenDash [ - 5442|1 + ||
3
2²,113 1a--=%%,1'
(n² 3) ESND. Σ Ps -
n
- 1/ + || - at." 22l(²)
(30)
i=1
Thus, we have bounded Term A. Substituting this back into Equation 24 results in
p Vilaat () Vf(3") Σ
< Y
(1
+
Σ
n
p. vi((a))))
12
2n
1=1
2(n² -3) EEND Σ Pi -
3L
xt + 1--0=200 xill?
(31)
i=1
Taking the sum from = 0 f- = T - yields
T
< )(39)-
1(05)-
7
Σ
v |
Σ
V V Σ
ps v ((a+))
2n
19

---

Published as a conference paper at ICLR 2023
Σ Pe Vilee
3L.
T-1
|| at 11 + +111 1 x.!1?3)
BEWD.
Pi
(32)
2(n² - 3)
Using the Lipschitz Gradient assumption, the following term is bounded as
T-1
Vz(z)
Σ P. (VVA(()))))
Σ
P P.V Σ (i(e)(())))
(33)
Vf(('' vd((a\)]
(34)
|| x;'
(35)
1=1
S 1 Pmar
Ph 1+--=$11 xt'1?
(36)
t=
Placing this back into Equation 32, and rearranging, yields
1(#) - -
7
| 2
Σ
Σ Pc V (o
2n
t=
T- n
+ 2(n²
3L
REWD
R
Pi ||
+ 1|0*
af'l?
3)
1=
7
2 Pmax
T-1 1
ΣΣ
1| - x/11
(37)
2n
1= i=1
Given that 50
=x² for all clients i, one can see that
T-
T-1 1
Σ
Pa || |--
2
112 +
++1
_
x
2
(38)
t=
t= ==1
1=1
7
Σ
Ps || -|''==/'1' x=!
Σ
Ps RT
x
11
(39)
1= i=1
Ps ||
x
(40)
t=
Using the result of Equation
38 condenses Equation 37 into
T-1
T
22
5(5")-
7
7
P
(x+)
2n
2n
t=
(n²
3L
3)
+
2n
BE-D.
T-1
Pi
x.
122
(41)
Bounding Term B. The recursion of our update rule can be written as
x++1 = X
Eole II W" - > Gaa
II (W" - W
(42)
1=0
-=++1
1=0
g=f+1
The recursion equation for the expected consensus model of and expected local model for client i can be computed by multiplying by la and e, respectively
x
x ++1 = 00
Σ Gl
1n
Σ
G(
II (Wa. - 1 1n
(43)
0=0
j=0
3
20

---

Published as a conference paper at ICLR 2023
II e -2 E (add
II (W", - W9)e; (44)
2 1i
1=0
4=j+1
j=0
9=1+1
Using the recursive equations above transforms the bound on term T-1
Eg Pi [
, 11
= Bvo Eii E
-E cldd,,)) 4o- -T mes) - Ej &1)1,, 1000 will
-eil (45)
2
T-1
527 BeNDD Ps
Σ
ln Glol Skn)
G(
W
1=0 i=1
j=0
g=i+1
Σ G 1y
(W in
In -ee)
(46)
T-1
1n
B
G(rly (2n)
W
P
9=1+1
:=B;
G )
II (W?, Wo)
1n e4)
1=0
4=1+1
B3
t II G(L,
Σ (G(d))
1n
In n 5
II w)),))
n
q=f+1
=B
Σ ز=
Goad, 2 II (W2 - way - e)) Glaf
II (Wg
w - (47)
Bounding Term B1. Using Lemma 2,
In
Eg 1=0
G(a
W
n
4=/+1
1n
< EEnD. Σ
W
(48)
1=0
g=1+1
M Vllad
= EewD. Σ
n
II W
(49)
M
n
1=0
j=
M
- 1
< R Dj
V V sth
(50)
M
j=0
m=l
Using Lemma 4, the equation above becomes
(-=))))))))))))))))) )P
= 2
+
(51)
M
n
1=0
0²
n
1
Σ
V
(4tt 1||
(1-
(52)
n
7
21

---

Published as a conference paper at ICLR 2023
2(n - 1)0²
L (1 (1- P) + +2
V (of) ||| 2
1 10- )0-
(53)
j=0
n
Taking the expectation over worker ig yields the desired bound
2( 1)0²
Vii, (a ||² n 10-
Ei /
+2
Mn
j=0
2(n 2
2(n 1)
Biy Vfey (12, || |||p>- pr-
(54)
(1 MM
n
Bounding Term B2. Using Lemma 2,
2
(G C
m
II W)ee). Gldly
II w)e)))
1= 1=
g=s+1
9=
Gldd (+ -1r-st Weeill
- mee)
(55)
For any 0, > 0 we find
carL t )| Cac +
200ss'
ajs' (hr -I Wres)
Weail
(56)
2
1' low [
Bjr'p'
min(
n (2)
5
O.j.'' ayj
(57)
20ye''
2
jt3 By applying inequality of arithmetic and geometric means the term in the last step, we can choose O' > s.t.
n (1o ( M (utt <
(58)
n
J
[G : ا +
G( y (
11
A-mininn' n'2
(59)
71
2
n 1
Σ
aa ( /|( m-min(ss')
(60)
n
G | بج
(61)
n
j=0
o' 1==++
1
GGrl | 1| 2( - -''0"
(62)
n f=0
n Σ
2(t - j)p ف
1 1 Σ
M
V ve )
(63)
n
M
j=0
m=
Using Lemma 4 (and the expectation Eg-D, that was omitted above but is present) yields
2(n
1) n
Σ
1
2(1 [''-)>p²>" '
0²
M +
(64)
1=0
4(n - 1) /po
2(n 1)
Σ
1
Vie, (44,,) )1 2(1 -
(65)
Mn(1 2
n
1=0
22

---

Published as a conference paper at ICLR 2023
Taking the expectation over worker ig yields the desired bound
4(n
vpo
2
1) n
f (at, 1| 2(t -1)pp -
Mn(1
vp)
j=0
4(n 1), 10
2(n 1)
t
Ei
V fi, (oc >/|
2( -))
(66)
Mn(1 vp)
n
j=0
Bounding Term B3.
2
RS Dj
Σ
G(
(W?, - W9) 1n - ei)
1=0
DD Σ
1
G(0 1
W 6 + 61 W 1
e;)
(67)
n
1=0
4=
II I1- - (2 - -e,) - III 3-1--11 3:1 (W -11 1m ei) || (68)
-B Σj
G
<2BenD:
Σ
G( (
II (W2, =11)(( 1n c:)
|=
$=1+1
2D
Σ 5=0
GlLl II (Wo (Ww-01T) x 1n
ci)
(69)
n
@=1+1
Due to the structure of ØiT, multiplying this matrix by i. n or es yields the same result. Using this, as well as the double stochasticity of W, we find
2E Ei
( (W7, (1 - e + catl I[ wr -
ei)
(70)
2E Ei
[1oce,, (2t IT IT a ed)|²
lau 2 In II W
] (71)
4
Using the result of Lemma 3, as our communication graph G is uniformly strongly connected and [W[]k, k., 2 1/n by construction, we see that
[[
II W
Ø1T] h.
I 44 4 h k.
(72)
g=1+1
Using this result, we find that
II (W." - - 9=1+1
1n e:) v1 S 8( n2 - - ) h. n
(73)
We can remove the -1 exponent by doubling the constant out front
II (W2, by 61)) 1n -:)) S 16( g=j+1
w
1 h.
(74)
n
n
Finally, using the fact that G( , all zeros except for one column, the iy columi, yields the desired result
E EDWD.
Σ
G(
(W2,
01T) 1n
es)
n
y=0
g=f+1
M
2
256( n ) 1) BeWD.
Σ
V
55 5o.j
(75)
M
1=0 0
m=
23

---

Published as a conference paper at ICLR 2023
Utilizing Lemma 4 yields
0²
Vit, (2tt )l'
256 n
2
((--))
1)
(76)
M
By properties of geometric series, and taking the expectation over worker iy, we find
256 1t 1 ) + 256 "1
V fi, (z) || 2((0-))
E2
(77)
(1 v
j=0
Using the bound of B1 in the main proof above, we arrive at the final bound of B3
W In
B
G
II (W",-
ez)
1=0
g=1+1
5120²
1
4(n 1)o²
512 n
(
(210-1))
Eig
(1 v2)
)M
n
p)Mn
0
4(n 1)
Σ
Vi, (ot || p'~s
(78)
n
i=0
4(n 1)o²
128
Mn
(1 p)
(1 - v2)
4(n
Big Vli, p-+ 128
(79)
11
y=0
Bounding Term B1. Following similar steps as bounding Term Bg we find
BR Lnj GGlat, "l W e.), Glrl, 11m w
e.))
G(ol, (T==s+(W" - W ca)
<2BEnD, D.
Σ
2
j=0 j'=j+1
Cloy (2'''
11 (W? - ( =a)l
(80)
<2 EgEDD 1=0
Σ
E
II (w
W 1n c;i
(81)
ig
Once again, we can use the proof of Lemma I to bound this result.
Finishing Bound of Term B. Putting all terms together, we find that Term is bounded above by
xx 2
Pt
22
T-1 1
Pi
2(n -1)22
+ 2(n 1)
Σ E,,
Vi,, (=t))) p's
pm
1= 1=1
0=
4(n
1) TTo2
2(n 1)
Σ Ei, V (2r)) )|
2(t 5
+
Mn Vp)²
n
j=0
12(n - 1)02
1
128
+ (1 -1-60 v2)
Mn
(1
12(n - 1) Σ
V (1tt))1
Eig
(82)
1=0
24

---

Published as a conference paper at ICLR 2023
Simplifying results in
T-1
4(n - 1)o²
7
vp
384
22
Pi
Mn
2(11 pp)
+ (1- vp)² + (1 v²)
0
1=1
4(n
1)
V Vfi, (or) }1( (
Big
2 + (t - 5)p + 384 38422(-11)
(83)
n
j=U
87 TT
11
7 + (1 vp)2 (1 (1- v2
vp
384
M
2(1 - p)
=
8(n
1)72
T-1
Vie (or (1))))((p)))) 7
(1- + + 33112 (84)
Big
1=
1=1
1=0
Using Lemma 5 results in
87202 Pv
8(n 1)7?
T-1 n
ΣΣ
ps Σ
n
Pt P.V.s(a)))
+
M
"
i=1
j=0
i=1
+ 12T.2
n
Ps
T0 1 ||
+ 6C²)
(2
77
- + (t - -)p²" (t-j)p²
38462((-1)
(85)
8 Pv
16(n- 1)7²
T-1
ΣΣ
Σ (iVli(ott
M
n
1=
+ 6T. Σ
n
Pt
T5 x 1|?
+ +x(2)
7 (2000 (t- - (0-D)p= + ((--1)
(86)
87202T Pv.
16(n 1)7?
T-1
P.V/fi(t)) ((
Σ
Σ
M
1=tt1
+ 6T.2 Σ
Pi
A 2! ||? + 3x22
foo (1 -'='pp=''' + -3-42((-1))
(87)
07 Pv
16(n- 1)72
Σ
T-1
Σ pc v
M
j=n
ee||*+ +35²)
Σ 7
+ 6L
Pi
E -
20th
hhp + 384 24
(88)
1=1
Am0
87 To Pv
T-1
+ 1
Σ Pe (i((()
+ +692 Σ
Ps
x -x2l
=21
+ 35²
(89)
M
5
1m1
Using Equation 38 ends with
2 16p Σ
Σ Pr v.(
M
T-1 n
+ 26L 2
Σ
ps
||
|
x
(90)
t= 1=1
Now subtract the final term on the right hand side from both sides
T
T Pv
ΣΣ p |
2++1 |1²
1- 9696
pu?? 1-96L"pp7?
<
+ 48T
M
1=
T-1
+ 16pu7
Σ P V (x
91)
1=0
25

---

Published as a conference paper at ICLR 2023
By Lemma 6, we can divide from both sides
T-1 n
8y
48T pu
16
T-1
12
ΣΣ
Pe |
- 2
Σ
Σ
P: fi (ス+)
(92)
2
2
t=0
Finishing Bound of Term A. Substituting the bound of B above into Equation 41 yields
T-1
T-1
"
- S
?
E |
?
Σ
P.V
2n
2n
3L
Pmaa
8y pv
48T 48T 2
+
nn2
- 3)
2n
Mz
2
2
T-1 Σ
P4 VILCO))
1
(93)
1=
i=1
Rearranging terms simplifies the inequality above to
T-1
32p - Σ Σ V
s(3") S
E
fi(a))
2n
2n
1=
00
4807 22
(94)
M
From Lemma 8, we find that (1 32p.0mm above can be removed.
2 0. Therefore, the second term of the right hand side
T-1
8pyP0"Tp
P
f(=")
E |
(95)
2n
2
Rearranging the incquality above and dividing by 7 yields
2n (f())) - f(²"))
16ndno Pv
96
E [V{
(96)
T7
Mz
2m 2n (f(() f(x")) Ty
1670npu
0²
+ 6( M
(97)
2
From Lemmas 6 and 7, the inequality above becomes
T T Σ
- 2n(f(F)) - f(z"))
1921
LYPP
0²
10
+
6C
(98)
Ty
M
Substituting in the defined step-size y (as well as its bound) yields 2n (f( f((T))
VTL+ VM M
E |<
T
V
10
+ +c22)
(99)
VTT.
M
2
2/A A
f
2/LA,
1921
V LA Ip ( (02 + 6C2 VM)
(100)
T
VTM
VTM
The final desired result is shown as
2 LA,
1 1921
Pv (0² + 6
2/
T
(101)
T
VTM
26

---

Published as a conference paper at ICLR 2023
F ADDITIONAL LEMMAS
Lemma 2 (From Lemma 3 in Lian et al. 2018 (Lian et al., 2018)). Let W be symmetric doubly stochastic matrix for each iteration Then
T
ln
II
W' E
T VT 2 0. 11
Lemma 3 (From Corollary 2 in Nedic and Olshevsky 2014 (Nedić & Olshevsky, 2014)). Let the communication graph & be uniformly strongly connected (otherwise known as B-strongly-comnen for some integer B >> 0), and A(t) [2nx be column stochastic matrix with [A(t)]i, 1/n Vi, t.
Define the product of matrices A(t) through A(s) (for 2 2 0) as A(t 8) == A(t) A(s). Then,
there exists stochastic vector <(t) E IR" such that
[[t s)]k.j +x((1) S Cu'
will always hold for the following values of C and V,
= V (1 1/n 1/nBBBBBBBBB
Lemma 4.
Under Assumption 1, the following inequality holds
M
E
Ee-D,
Σ
Ve(x,,
Si..)
M + V[
M m=1
Lemma 5. Under Assumption I, the following inequality holds
E, [.([((())) 2
Σ P.V.(((a)))
+ 121
2
Pa
2//1² +62.
Lemma 6. Given the defined step-size y and total iterations T in Theorem 1, the term is and bounded by
384
1>2:=1- 9-0--9622p p 2
193
Lemma 7. Given the defined step-size 7 and total iterations T in Theorem 1, the term & is and bounded by
3L
122Mpmax <
L (12
2
6: : (n22 - 3)
2n
122
775(193)
Lemma 8. Given the defined step-size n and total iterations T in Theorem we find the following bound
32pm
20
G LEMMA PROOFS
Proof of Lemma I. These steps shown in the Main Theorem proof. Due the symetry and double stochasticity of W we find
BEWD.
Σ
G(
II (W - W 1n q=7+1
es)
(102)
1=0
1n
=Eg-D. Σ
G
II g=1+1
(W - 21 + +11 W n
ei)
(103)
by
1=0
=EgnD, 2/1
G61 -
- - -e))
-11 -11 (Wa -01T( - e.)
(104)
<2EenD. Σ
Glay 5
II (W3 - Φ1T) 1
ei)
1=0
@=
27

---

Published as a conference paper at ICLR 2023
+ 2 D.
Σ
G(oy C
II (w - In es)
(105)
n
g=+1
Due to the structure of @i,T, multiplying this matrix by in e, yields the same result. Using this, as well as the double stochasticity of W, we find
-IT mill |oud (455) w
ei
(106)
||aue ( (T an ai|l" aud S dn
DD Σns
II 0-2+1
(107)
=P; Using the result of Lemma 3, as our communication graph G is uniformly strongly connected and [W 2 1/n by construction, we see that
II W q=i+1
61T)
n,a S 40' h,
(108)
Using this result, we find that
II (W"," σ1T)( 1n -ei) S 8( Dr- b h. g=++1
(109)
n
We remove the -1 exponent by doubling the constant out front
[[ II (W7, - -01T( In -;)], nl S 16( T > a=++1
V h.
(110)
Finally, using the fact that G( < is all zeros except for one column, the iy-th column, yields the desired result
EE-D
Σ
G(
(W?. - Φ1T)( 1a
e;)
n
j=0
g=1+1
M Σ
S Σ 256(
2(- 2,,
BEND.
V
5x
(111)
71
M
1=0
m=1
Utilizing Lemma 4 yields
02
V l')
256
(t-
(112)
n
M
j=0
By properties of geometric series, and taking the expectation over worker ij, we find
256o²
n nー 1 )2 256
V (at,) || ((1))
Ex
(113)
(1
v²)M
n
n
Using the bound Equation 54 (term B1) in the main proof above, we arrive at the final bound
In
BgNDD
Σ
G(
II
(W iq
W
es)
n
1=0
9=1-1
5120²
n2 1 )² +
4(n - 1)o²
+ 512(
n
)2
Σ E, 1=
V (fi (1t))/ 20(0)))
(1 - v2)
n
(1 - MM
4(n 1)
Eig Vfi, (xt, (1, o
(114)
n
1=0
4(n 1)02
128
+ (1 122
Mn
(1 1--p) p)
4(n - 1)
Eig V (44 || 1| (0-1+ 1 128))(1-))
(115)
71
j=U
28

---

Published as a conference paper at ICLR 2023
Thus, we have our desired result
E
Gl
II
(W - WD)( In
es)
s 0 0²
+E
_
(116)
n
M
g=i+1
Proof of Lemma 4.
M Σ
ESND.
Vl(oi )
(117)
M
mmm
M
1
E
BEND.
Vilat, V + Vf((a()
(118)
M
m==1
1
RENDD
Σ
Ve(at, Vsi(ot)) + BEND
Σ (((ttt)
M
M
M
+
2
BE-D,
(vilat) smme) - v)i(x());
Σ V)i(z!))
(119)
M
mm1
m=1
M
EEWD.
- -...)-v-fie V.i(x:))| + M² Ví{ 2
(120)
M
m=1
0²
(121)
M
Proof of Lemma 5.
E, [f(22))] = E, Vf((zt) Σ Py (((())) + Σ
De vf((tt))
(122)
Vi((oa)) Σ (((
n
)
S 2E,
+
Σ P3 (
(123)
The first term on the right hand side can be bounded by
E,
fi(!))
Σ ps ((()))
Vlil X'1
X'1n V
a Σ 5=1
-3E,
Vi((s!)
+ Σ PS
p3 (155)(
n
n
Vfi X' ) Σ P3 5
X'1n n )
+
(124)
j=l
S3E,
L2 |1 - z²112 + Σ
Pj
V fa ( V
+ ([ - ))(3))12)
(125)
1=1
<3E,
1,2 | - 2'11 + 1,2 Σ
ps || - - =m(1() + 3322
(126)
1-1
2
Pi - = + 35²
(127)
29

---

Published as a conference paper at ICLR 2023
Combining all terms yields the final result
"
E [/ <
Σ (.V()
12L2
Σ p: ||
2/122
(128)
Proof of Lemma 6. It is trivial to see that <
We now determine the lower bound of given
2, Pmax 2 1/n, and pv 775/4
Mn² D
-96L PuT 99I2 Pal
96L2p
(129)
TL
1932 12 2 Pma
96
384
1 1
(130)
1932 2
(775)
Proof of Lemma 7, Given 2 2 and Pv 2 775/4. /4, and the definition 7 and T, one can see
3L
L'Appman
Lynpman
② =
(131)
n - 3)
2n
n (1 3/n²)
2
L
Lnpmax
Mn²Aj
(132)
n - 3/n²)
2
VTL
3
Lmpmma
1
L
3
+
+
(133)
n
(1 - 1133//² 3/n²)
2
193Ipp
22
(1
3/4)
38ppv
(12 + 775(193)
(134)
n
Proof of Lemma 8, Given 2 2, Pmax 2 1/n Lemma 6, and Lemma 7, one can see
1-1 32p
32p
1
32n
(135)
193
193L
32(12 775[193]
16(12 + 775(193) 1933)
1
2 0
(136)
1932n
193(1
193" (775)
30


Reviews:
[{"review_id": "r4MPlTs4D1D", "reviewer": "Reviewer_BZ9x", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper propose a novel wait-free decentralized FL algorithm, which is a decentralized SGD algorithm with heterogeneous local updates and asynchronous local model synchronization. Theoretical analysis is provided for both iid and non-iid cases. The empirical results show good performance.", "summary_of_the_review": "In overall, I think this is a good paper with thorough theoretical and empirical analysis. ", "strength_and_weaknesses": "Strength:\n1. This paper propose a novel wait-free decentralized FL algorithm, which is a decentralized SGD algorithm with heterogeneous local updates and asynchronous local model synchronization. \n2. A novel client-communication weight selection algorithm is proposed.\n3. Theoretical analysis is provided for both iid and non-iid cases. \n4. The empirical results show good performance.\n\nWeakness (concerns and questions):\n1. In the experiments, 2 network topologies including ROC and ROC-xC are used. Are these 2 types of topologies common for the FL scenario? If so, is there any reference to support that? Otherwise, I would recommend the authors to explain why these 2 types of topologies are chosen for the experiments, or adding more experiments with other types of topologies.\n2. How is the convergence affected by the network topology, or the properties of the mixing matrix W (e.g., eigenvalues of its graph Laplacian)?\n3. The communication pattern of SWIFT actually have 2 kinds of uncertainty: 1. inactive clients; 2. randomly selected active client for communication. However, I could only find 1 expectation, namely the client-communication matrix. Does the expected client-communication matrix resolve the uncertainty for both inactive clients and random communication? If so, I believe that the expected client-communication matrix indicates the expected delay for all the clients. Given the expected delay, we surely do not need the upper bound of the delay for the theoretical analysis. I think this is a simple trick, but the authors' overclaim of the theoretical analysis without the bounded delay assumption may get the readers confused. I would recommend the authors to clarify it.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "m8hMI_b96aT", "reviewer": "Reviewer_KnPQ", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 proposes a new asynchronous decentralized training algorithm with local updates, named SWIFT. Compared to previous works in this direction, the authors removed the bounded delay assumption in analysis, and hence, obtained better theoretical results. In order to ensure the convergence, a new technique is introduced to allow non-symmetric non-doubly stochastic mixing matrices. At the end, experiments on CIFAR10 dataset with a cluster of machines validate the superiority of the proposed algorithm.", "summary_of_the_review": "I believe this paper make a good contribution in advancing asynchronous decentralized training algorithm, but some technical details are unclear such that I cannot accurately evaluate its significance.", "strength_and_weaknesses": "## Strength\n1. The authors removed the bounded delay assumption in nearly all previous works when analyzing asynchronous decentralized training algorithms.\n1. In order to ensure convergence, several new techniques are introduced to deal with non-symmetric and non-doubly stochastic mixing matrices.\n1. The authors are able to run experiments on a real cluster of machines, instead of just simulating runtimes on a single machine. So the experimental results are more convincing.\n\n\n## Weakness\n1. Asynchronous decentralized training is already a mature technique. As the authors mentioned in the paper, several papers already proposed, such as AD-PSGD, and [1]. After reading the paper, it is unclear why do we need a new asynchronous algorithm. I understand that it is an important contribution to remove the bounded delay assumption. But it should be clear whether the algorithmic changes or new analysis techniques enable this theory advancement. The authors are supposed to highlight the insights on how and why. \n2. The authors mentioned several places (e.g. in the abstract) that SWIFT reduces the communication time per round. But this statement is not accurate. As an asynchronous algorithm, SWIFT does not change the communication time but just reduce/remove the idle time in waiting for slow workers. I suggest the authors to refine the related statements.\n3. I did not get why SWIFT needs to randomly select an active client at each round. If so, there must be some idle time at some clients, as they are not selected but may already finish computation. In practice, the active clients should be determined by the randomness in the client computation time. Once a client finishes local computation, it can trigger a communication and be labeled as the active clients. Server cannot control this process. The authors are supposed to provide clarifications on this.\n4. If the above point is true, then that means the actual running SWIFT is different from what the authors analyze. The authors model the randomness in computing time by randomly selecting active clients. This can be a very rough approximation. The authors should justify why this theoretical approximation make sense and why this assumption is better than bounded delay assumption. Also, it should be made clear in the paper that their analysis is applied to a variant (possibly simplified version) of SWIFT.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "GbgWCw5Zx5", "reviewer": "Reviewer_Cc5h", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes SWIFT, which is claimed to be a wait-free asynchronous decentralized optimization algorithm. This paper provides a theory for the convergence rate and uses experiments to show the effectiveness of the proposed algorithm.", "summary_of_the_review": "Here I list the summary and my questions. I hope that the authors can point out my misunderstandings about the settings or clarify my questions during the author's response.\n\n1. (Major) The setting. To me, the setting considered in this paper is the synchronous setting, not the asynchronous setting. The asynchronous setting considered in [1] allows clients to grab the model \"before\" another client ends the round. The author should discuss much more why the setting considered in this paper is also asynchronous setting, e.g., by giving more citations.\n2. (Major) The author should also discuss how the experiment is done, e.g., if a client needs to wait until another client finishes its round. From the algorithm, it seems not but for the general understanding of the asynchronous algorithm, it should be yes.\n3. For comparison, I suggest the authors to compare with the best synchronous optimization algorithms that can also deal with data heterogeneity, e.g., D2 [2].\n4. Why the theory needs $T \\ge \\Omega(n^2)$. Naively thinking, $\\tilde O(n)$ rounds should be equivalent to a single round in the synchronous setting, and thus intuitively, $T$ should only larger than $\\Omega(n)$?\n\nGiven the questions above, I believe this paper does not reach the acceptance bar at this time. I am happy to adjust the score after the authors point out my conceptual misunderstanding or answer my questions.\n\n\nCitations\n\n[1] Asynchronous Stochastic Gradient Descent with Delay Compensation. Zheng et al., 2016\n\n[2] D2 : Decentralized Training over Decentralized Data. Tang et al., 2018", "strength_and_weaknesses": "Strength:\n1. The proposed algorithm uses the ideas from local steps, which is well applied in federated learning scenarios.\n2. In the theory part, it tries to remove the bounded delay assumption used by most other asynchronous optimization algorithms. (See the weakness part for more discussion on this)\n3. The numerical experiment result seems interesting if the authors can justify their experiment is actually in the asynchronous setting. (See the weakness part for more discussion)\n\nWeakness:\n1. (Major) I think the setting in this paper considered is not the asynchronous setting, at least from the theory part. This is more like the \"partial participation\" case in the distributed optimization/federated learning but not the asynchronous setting, and thus I still think that it is a synchronous algorithm (or at least the analysis is for the synchronous setting). The reason is that, this paper seems to require that only a single agent/client can do the update during each round, but the asynchronous setting does not require this and the other clients can start updating even before the other client ends. Nonetheless, partial participation/client sampling is still interesting for decentralized optimization algorithms. From an empirical point of view, this partial participation/client sampling can indeed make communication faster (because do not need to wait for all), but from the theory side, it is very different from the asynchronous setting.\n2. (Major) It is not clear how the experiment is done (even in the appendix): for example if there is a notion of a round in the implementation. If yes (and it is exactly what is show in the algorithm), then the implementation is also not asynchronous but synchronous, and it should be compared to the synchronous algorithms.\n3. (Minor) Why not compare to the best synchronized decentralized algorithms like D2? D2 can better handle the data heterogeneity issue than D-SGD.\n4. (Minor) The theory needs the bounded dissimilarity between each client/agent, and thus may not handle arbitrary heterogeneity.\n5. (Minor) For theory, T needs to be larger than $n^2$, which seems not tight.", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "54V4urJLEPx", "reviewer": "Reviewer_1Mgi", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper considers asynchronous training in the absence of a central server. They propose a novel algorithm SWIFT to address the problem and does not rely on the common bounded delay assumption. Convergence rates and empirical validations are provided ", "summary_of_the_review": "I have listed two questions that concern me. I recommend rejection if the authors cannot address them. ", "strength_and_weaknesses": "There are two aspects that concern me the most:\n\n- Algorithm 1 is not wait-free according to Line 11 and 12. As far as I can see, worker i has to wait for the models from all of its neighbors before averaging. If any update of its neighbor is delayed, which could be an unbounded delay, then worker i is blocked.  Then in the future communication rounds, all neighbors of i are blocked as they have to wait for worker i for updates. I didn't find how the asynchrony is actually addressed in the algorithm.\n\n- There is no theoretical benefit to use SWIFT. The convergence rate is $O(1/sqrt{T})$ which does not scale with the number of workers $n$.  It means SWIFT is not benefiting from the collaborative training and only have the same rate as training alone.", "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": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster