Epidemic Learning: Boosting Decentralized Learning with Randomized Communication
Authors: Martijn De Vos
Sadegh Farhadkhani
Rachid Guerraoui
Anne-marie Kermarrec
Rafael Pires
Rishi Sharma
Venue: NeurIPS 2023 poster (2023)
Keywords: Epidemic
Decentralized Learning
Randomized Communication
Peer sampling
TL;DR: We (theoretically and empirically) show that benefit of randomized communication for decentralized learning.

Abstract: We present Epidemic Learning (EL), a simple yet powerful decentralized learning (DL) algorithm that leverages changing communication topologies to achieve faster model convergence compared to conventional DL approaches. At each round of EL, each node sends its model updates to a random sample of $s$ other nodes (in a system of $n$ nodes). We provide an extensive theoretical analysis of EL, demonstrating that its changing topology culminates in superior convergence properties compared to the state-of-the-art (static and dynamic) topologies. Considering smooth non-convex loss functions, the number of transient iterations for EL, i.e., the rounds required to achieve asymptotic linear speedup, is in $O(n^3/s^2)$ which outperforms the best-known bound $O(n^3)$ by a factor of $s^2$, indicating the benefit of randomized communication for DL. We empirically evaluate EL in a 96-node network and compare its performance with state-of-the-art DL approaches. Our results illustrate that EL converges up to  $ 1.7\times$ quicker than baseline DL algorithms and attains $2.2 $\% higher accuracy for the same communication volume.

Epidemic Learning: Boosting Decentralized Learning with Randomized Communication
Martijn de Vos
Sadegh Farhadkhani f
Rachid Guerraoui Rishi Sharma
Anne-Marie Kermarree
Rafael Pires
EPFL, Switzerland
Abstract
We present Epidemic Learning (EL), simple yet powerful decentralized learning (DL) algorithm that leverages changing communication topologies to achieve faster model convergence compared to conventional DL approaches. At each round of EL., each node sends its model updates to random sample of 8 other nodes (in system of nodes). We provide an extensive theoretical analysis of EL, demonstrating that its changing topology culminates in superior convergence properties compared the state-of-the thrtthe-rtt (static and dynamic) topologies. Considering smooth non- convex loss functions, the number of transient iterations for EL. i.e., the rounds required to achieve asymptotic linear speedup.
(*²/z) which outperforms the best-known bound (nn²) ) by factor of s² indicating the benefit of randomized communication for DL. We empirically evaluate EL in a 96-node network and compare its performance with state-of-the-art DL approaches. Our results illustrate that EL converges up 1.7x quicker than baseline DL algorithms and attains 2.2% higher accuracy for the same communication volume.
Introduction
In Decentralized Learning (DL), multiple machines (or nodes) collaboratively train machine learning model without any central server [32, 37, 42]. Periodically, each node updates the model using its local data, sends its model updates to other nodes, and averages the received model updates, all without sharing raw data. Compared to centralized approaches [28], DI. circumvents the need for centralized control, ensures scalability [21, 32], and avoids imposing substantial communication costs central server [58]. However, DL comes with its challenges. The exchange of model updates with all nodes can become prohibitively expensive in terms of communication costs as the network size grows [25]. For this reason, nodes in DL algorithms usually exchange model updates with only a small number of other nodes a particular round, i.e., they perform partial averaging instead of All-Reduce (network-wide) averaging of local model updates [57].
key element of DL algorithms is the communication topology, governing how model updates are exchanged between nodes. The properties of the communication topology are critical for the performance DI. approaches as it directly influences the speed of convergence [27, 54, 56, 52]. The seminal decentralized parallel stochastic gradient descent (D-PSGD) algorithm and many of its proposed variants rely on a static topology, i.e., each node exchanges its model with a set of neighboring nodes that remain fixed throughout the training process [32]. More recent approaches study changing topologies, i.e., topologies that change during training, with notable examples being time-varying graphs [24, 36, 51], one-peer exponential graphs [57], EquiTopo [53], and Gossip Learning [16, 17, 20]. We discuss these works in more detail in Section
Authorr are listed in alphahetical order. Conresponinng author <sadegh. farhadkhani @epfl.ch>.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

This paper investigates the benefits of randomized communication for DL. Randomized communica- tion, extensively studied in distributed computing, has been proven to enhance the performance of fundamental algorithms, including consensus and data dissemination protocols [22, 5, 8). In the case of DI., randomized communication can reduce the convergence time and therefore communication overhead [11]. In this work, we specifically consider the setting where each node communicates with a random subset of other nodes that changes at each round, as with epidemic interaction schemes [12, 38J. We also focus on the scenario where data is unevenly distributed amongst nodes, ie., non independent and identically distributed (non-IID) settings, a common occurrence in DL [18].
To illustrate the potential of randomized communication, we empirically compare model convergence in Figure 1 for static s-regular topologies (referred to as Static-Topo) and randomized topologies (referred to as Rand.-Topo (EI.), our work) in 96-node networks on the CIFAR-10 learning task. As particular static topologies can lead to sub-optimal convergence, we also experiment with the set- ting in which nodes are stuck in an unlucky static s-regular topology (referred to as unlucky topology consists of two network partitions, con- nected by just two edges. Figure I reveals that dynamic topologies converge quicker than static topologies. After 3000 communication rounds, Rand.-Top (EL, our work) achieves 65.3% top-1 test accuracy, compared to 63.4% and 61.8% for
Rand--Topo (EL)
Static-Tope
Staii-TTop-Unlluck
ecqurasy [%6]
60
Test Test Restscurag
66
40
64
This
62
20
60
2
2.5
3
2
3
Communication round (x10²)
Randomized topologies can converge quicker than static ones.
Figure 1:
and Pratic-Unlucky.. respec- tively. Additional experiments can be found in Section 4, and their setup is elaborated in Appendix C.
Our contributions Our paper makes the following four contributions:
We formulate, design, analyze, and experimentally evaluate Epidemic Learning (EL), novel DL algorithm in which nodes collaboratively train machine learning model using a dynamically changing, randomized communication topology. More specifically, in EL., at each round, each node sends its model update to a random sample of other nodes (out of n total nodes). This process results in randomized topology that changes every round.
We first analyze an EL variant, named EL-Oracle, where the union of the random samples by all nodes forms an s-regular random graph in each round. EL-Oracle ensures perfectly balanced communication load among the participating nodes as each node sends and receives exactly s model updates every round. Nevertheless, achieving an s-regular graph necessitates coordination among the nodes, which is not ideal in decentralized setting. To address this challenge, we also analyze another EL variant, named Eoca.. EL--ooal,, each node independently and locally draws a uniformly random sample of s other nodes at each round and sends its model update to these nodes. We demonstrate that El.-Local enjoys a comparable convergence guarantee as EL. Era-le without requiring any coordination among the nodes and in fully decentralized manner.
Our theoretical analysis in Section 3 shows that EL surpasses the best-known static and randomized topologies in terms of convergence speed. More precisely, we prove that EL converges with the rate O (1/vTT + 1/ /- + 1/T), where T is the number of learning rounds. Similar to most state- of-the-art algorithms for decentralized optimization [30, 24] and centralized stochastic gradient descent (SGD) (e.g., with parameter server) [29], our rate asymptotically achieves linear speedup, i.e., when T is sufficiently large, the first term in the convergence rate O(1/vn)) becomes dominant and improves with respect to the number of nodes.
Even though linear speedup is a very desirable property. DL algorithms often require many more rounds to reach linear speedup compared to centralized SGD due to the additional error (the second term in the above convergence rate) arising from partial averaging of the local updates. To capture this phenomenon and to compare different decentralized learning algorithms, previous works [10, 50. 53, 57] adopt the concept of transient iterations which are the number of rounds before a decentralized algorithm reaches its linear speedup stage, i.e., when I' is relatively small such that the second term of the convergence rate dominates the first term.
We derive that EL. requires ('²/.²) transient iterations, which improves upon the best known bound by a factor of s². We also show this result in Table 1. We note that while EL matches the of
2

---

Table Comparison of EL with state-of-the-art DL approaches (grouped by topology family). We compare Or-Orecle and EL-Local to ring, torus, Erdōs Erdōs-Rényi, exponential and EquiTTpo topologies.
Method
Per-Iter Out Msgs.
Transient Iterations
Topology
Communication
Ring (23]
O(n")
static
undirected
Torus [23]
O(n")
static
undirected
E.-R. Rand [45]
Oloo nt)
(nn)
static
undirected
Static Exp. [57]
log n
On log" n)
static
directed
One-Peer Exp. [57]
(n log" n)
semi-dynamic'
directed
D-EquiStatic (53]
log n
O(n*)
static
directed
U-EquiStatic [53]
Iog
O
static
undirected
OD-EquiDyn [53]
(n1))
semi-dynamic'
directed
OU-EquiDyn [53]
O(n²)
semi dynamiyn
undirected
ELL-Oracle (ours)
8
(12)/2)
rand--dnaamic"
undirected
E.L--Lccal (ours)
O(n)/2)
randd-dynamic"
directed
Semi -ini-dyyamic topologies remain fixed throughout the learning process but nodes select subsets of adjacent (ncighboring) nodes each round communicate with. In deddomizze-dyyaamee topology, the topology is replaced each round.
the-art bounds when E O(),, offers additional flexibility over other methods through parameter s that provably improves the theoretical convergence speed depending on the communication capabilities of the nodes. For instance, when 8 (log n) as Erdós-Rényí and EquiStatic topologies, the number of transient iterations for EL reduces to O("" O"n0/1og" n). outperforming other methods. This improvement comes from the fact that second term in our convergence rate superior to the corresponding term O(1 p/PT) in the rate of D-PSGD, where (0, 1] is the spectral gap of the mixing matrix. We expound more on this in Section
We present in Section 4 our experimental findings. Using two standard image classification datasets, compare EL-Oracle and EL-Local against static regular graphs and the state-of of-thh-arrr the-rrt EquiTopo topologies. We find that EL-Oracle and EL-LLocal converge faster than the baselines and save up to 1.7 communication volume reach the highest accuracy of the most competitive baseline.
Epidemic Learning
In this section, we first formally define the decentralized optimization problem. Then we outline EL algorithm and variants in Section 2.2.
2.1 Problem statement
We consider a system of n nodes [n] := {1,..., n2} where the nodes can communicate by sending messages. Similar to existing work in this domain [53], we consider settings in which a node can communicate with all other nodes. The implications of this assumption are further discussed in Appendix D. Consider a data space Z and loss function f : Rd Z + Given parameter E Rd, data point Z incurs a loss of value f(z E). Each node E [n]] has a data distribution D( over 2, which may differ from the data distributions of other nodes. We define the local loss function of over distribution D( as (x)) (z) == Eg [f(x, The goal is to collaboratively minimize the global average loss by solving the following optimization problem:
min F(x) = 1 Σ (O)
(I)
3

---

Round k
Round k
Round k
Round k
EL-Oracle (forming s-regular graph)
EL-Local (forming a s-out graph)
Figure 2: EL-Oracle (left) and EL-Local (right), from the perspective of node j. with and for two rounds. We show both outgoing model updates (solid line) and incoming ones (dashed line).
2.2 Description of EL
We outline EL, executed by node i, in Algorithm 1. We define the initial model of node as xo and a step-size y used during the local model update. The EL algorithm runs for T rounds. Each round consists of two phases: local update phase (line 3-5) in which the local model is updated using the local dataset of node i, and a random communication phase (line 6-9) in which model updates are sent other nodes chosen randomly. In the local update phase, node i samples data point <(") from its local data distribution DD()) (line 3), computes the stochastic gradient 9;" (line 4) and partially updates its local model 1++1/ using step-size y and gradient D; (6) (line 5).
(1)
(4)
The random communication phase follows, where node first selects of other nodes from the set of all nodes excluding itself: [n]] {i} (line 6). This sampling step the innovative element of EL, and
we present two variants later. It then sends its recently updated local model 2441/5 to the selected nodes and waits for model updates from other nodes. Subsequently, each node i updates its model based on the models it receives from other nodes according to Equation (2). The set of nodes that send their models to node is denoted by s( The new model for node is computed as weighted average of the models received from the other nodes and the local model of node i, where the weights
are inversely proportional to the number of models received plus one.
(1) Fi41
x
(1) 14//2
Σ
G) 44//2
s((0)
+1
jES(D
We now describe two approaches to sample other nodes (line 6), namely EL-Oracle and EL-Local:
EL-Oracle With EL-Oracle, the union of selected communication links forms s-regular topology which every pair of nodes has an equal probability of being neighbors. Moreover, if node samples node j.j will also sample i (communication is undirected). Figure 2 (left) depicts EL-Oracle sampling from the perspective node in two consecutive iterations. One possible way to generate such a dynamic graph is by generating an s-regular structure and then distributing random permutation of
Algorithm 1 Epidemic Learning as executed by node i
1: Require: Initial model x (4) E Rd number of rounds T, step-size 7, sample size s.
2: for & 0,..., T 1 do
Line 3-5: Local training phase
3: Randomly sample data point c! from the local data distribution ((t)
4: Compute the stochastic gradient ( fx( (5) (())
(())
5: Partially update local model #/41/2 x;
(6)
7
Line 6-9: Random communication phase
6: Sample other nodes from [n]] (i) using EL-Oracle or EL-Local
(6) 7: Send 1/11/2 to the selected nodes
the set updated models S.
s! the set received models by node in round
Update rf to the average available updated models according (2)
10: end for

---

nodes at each round. Our implementation (see Section 4) uses central coordinator to randomize and synchronize the communication topology each round.
EL.-Local Constructing the s-regular topology in EL--Oracee every round can be challenging in a fully decentralized manner as it requires coordination amongst nodes to ensure all nodes have precisely incoming and outgoing edges. This motivates us to introduce EL-Local, a sampling approach where each node locally and independently samples other nodes and sends its model update to them, without these nodes necessarily sending their model back to i. The union of selected nodes now forms a s-out topology. Figure 2 (right) depicts EL-Local sampling from the perspective of node j in two consecutive iterations. In practice, EL-Local can be realized either by exchanging peer information before starting the learning process or using a decentralized peer-samplin service that provides nodes with (partial) views on the network [20, 41, 55]. While both the topology construction in EI.-Oracle as well as peer sampling in EL.-Local add some communication and computation overhead, this overhead is minimal compared to the resources used for model exchange and training.
Even though each node sends messages for both EL- Oracle and EL-Local, in EL-Local, different nodes may receive different numbers of messages in each training round as each node selects the set of its out-neighbors locally and independent from other nodes. While this might cause an imbalance in the load on individual nodes, we argue that this does not pose a significant issue in practice. To motivate this statement, we run an experiment with n 100, 1000 and 10000 and for each value of n set s = (ogg(n)) We simulate up to 5000 rounds for each configuration. We show in Figure a CDF with the number of incoming models each round and observe that the distribution of the number of models received by each node is very light-tailed. In 000 node network (and s = 13). nodes receive less than 22 models in 99% of all rounds. As such, it is improbable that a node receives a disproportionally large number of models in a given round. In practice, we can alleviate this imbalance issue by adopting a threshold value k on the number of models processed by each node in a particular round and ignoring incoming models after having received l models already. The sender node can then retry model exchange with another random node that is less occupied.
7, 100 nodes
10, 1000 nodes
13, 10000 nodes
13 18 22
100
99th percentile
CDF [96]
13
50
50th percentile
0
0
10
20
30
40
Figure 3: The distribution of incoming models, for different values of n and s.
3 Theoretical Analysis
In this section, we first present our main theoretical result demonstrating the finite-time convergence of EL. We then compare our result with the convergence rate of D-PSGD on different topologies.
3.1 Convergence of EL
In our analysis, we consider the class of smooth loss functions, and assume that the variance of the noise of stochastic gradients is bounded. We use of the following assumptions that are classical to the analysis of stochastic first-order methods and hold for many learning problems [4, 14).
Assumption (Smoothness), For all i [n), the function f() Rd - differentiable and there exists L < de, such that for all x. y E Rd.
())) ()) S I xl1-
Assumption 2 (Bounded stochastic noise). There exists o < oo such that for all i E [n], and x E Rd.
|| [F(c,)))
-1 so²
E E
Moreover, we assume that the heterogeneity among the local loss functions measured by the average distance between the local gradients is bounded.
5

---

Assumption 3 (Bounded heterogencity). There exists H < oo, such that for all E R
()) VF(w)| SH..
MEIM
We note that this assumption is standard in heterogeneous (a.k.a. non-i.i.d) settings, i.e., when nodes have different data distributions [32, 57J. In particular, H can be bounded based on the closeness of the underlying local data distributions [13]. We now present our main theorem.
Theorem 1. Consider Algorithm Suppose that assumptions I, 2 and 3 hold true. Let Do be a real value such that F F(zg) minzera F(x) I Ao- Then, for any T 2 1, 2 2, and 2 1:
a) For Er-Oracle, setting
nAo TLo
Ta.L2 (0² + H2) 11)
Y E
min
we have
19) 1']
(
LAuo2 nll'
a/ 12A (02 + H2)
LAu
VF
2
EO
+ V
12
T
[E|N]
where
1- 8
EO(
E
++
For EL-Local, setting
mdo
D TB.L2 (02 + H2!) 11)
7 7
min (1 TVo2 B.HP)
we have
VF (4 '''
LAu(O? 3,H1))
B.LZA (0² + 112)
LAu
E
nf
T
T
0=
where
B. = 1 11-11-11 n -
(1-(1-
))
1 n -- E c
To check the tightness of this result, we consider the special case when = -1-1. 1. Then, by Theorem 1,
have a, 3. O, and thus both of the convergence rates become O (VLavo"/ + LAs/T)
which is the same as the convergence rate of (centralized) SGD for non-convex loss functions [14].
This is expected as, in this case, every node sends its updated model to all other nodes, corresponding to all-to-all communication in a fully-connected topology and thus perfectly averaging the stochastic gradients without any drift between the local models.
The proof of Theorem is given in Appendix A, where we obtain a tighter convergence rate than existing methods. It is important to note that the mixing matrix of regular graph is doubly stochastic, for EI-OOacle, one can use the general analysis of D-PSGI with (time-varying) doubly stochastic matrices [24, 30] obtain convergence guarantee. However, the obtained rate would not be as tight and would not capture the (1/ (/a) improvement in the second term, which is the main advantage of randomization (see Section 3.2). Additionally, it is unclear how these analyses can be generalized to the case where the mixing matrix is not doubly stochastic, which is the case for our EL-Local algorithm. Furthermore, another line of work [1, 43, 44) provides convergence guarantees for decentralized optimization algorithms based on the PushSum algorithm [22], with communicating the mixing weights. may possible to leverage this proof technique to prove the convergence of EL-Local. However, this approach yields sub-optimal convergence guarantees (e.g., see parameter C' in Lemma of [1]) and does not capture the benefit of randomized communication.
ciieension-dependen

---

Remark 1. Most prior work [24, 32] provides the convergence guarantee on the average of the local models āt = # Eiem ) 14) However, as nodes cannot access the global averaged model, we provide the convergence rate directly on the local models. Nonetheless, the same convergence guarantee as Theorem also holds for the global averaged model.
3.2 Discussion and comparison to prior results
To provide context for the above result, we note that the convergence rate of decentralized SGD with non-convex loss functions and a doubly stochastic mixing matrix [24, 30] is
(VTAR nT
IPA (po² + H²)
LAo +
(3)
D²T²
pf
where p E (0, 1] is the spectral gap of the mixing matrix and 1/p bounded by O( for ring [23], ((n) for torus [23], (1) for Réníi random graph [45], (logn) n) for exponential graph [57], and (1) for Equi [53]. We now compare the convergence of EL against other topologies across two key properties: linear speed-up and transient iterations.
Linear speed-up Both of our convergence rates preserve a linear speed-up of O(IvnT) in the first term. For EL-Oracle, this term the same as (3). However, in the case of EL-Local, in addition to the stochastic noise σ, this term also depends on the heterogeneity parameter H. that vanishes when increasing the sample size 8. This comes from the fact that, unlike EL-Oracle, the communication phase of EL-Local does not preserve the exact average of the local models (i.e.,
Eseja) Fz+1 * Eie(n) -00) and it only preserves the average in expectation. This adds an error term to the rate of El.-Local. However, as the update vector remains an unbiased estimate of the average gradient, this additional term does not violate the linear speed-up property. Our analysis suggests that setting s = H² can help mitigate the effect of heterogeneity on the convergence of EL-Local. Intuitively, more data heterogeneity leads to more disagreement between the nodes, which requires more communication rounds converge.
Transient iterations Our convergence rates offer superior second and third terms compared to those in (3). This is because first, p take very small values, particularly when the topology connectivity is low (e.g., 1 E Onn2) ) for a ring) and second, even when the underlying topology is well-connected p p E O(), such as EquiTopo [53], the second term in our rates still outperforms the one in (3) by factor of 5/. This improvement is reflected in the number of transient iterations before the linear speed-up stage, i.e., the number of rounds required for the first term of the convergence rate to dominate the second term [57]. In our rates, the number of transient iterations is in O(*) whereas /p²) for the homogeneous case and O(" O(""p²) for the heterogeneous case. We remark that p E (0, 1]. but 2 1 is an integer; therefore, when s ((1) the number of transient iterations for EL matches the state-of state-of-the-art bound. However, can be provably improved by increasing s depending on the communication capabilities of the nodes, which adds more flexibility to EL with theoretical guarantees compared other methods, For instance, for s E (log n) as in Erdōs-Rényt and EquiStatic topologies, the number of transient iterations for EL becomes Ore²) log' n) which outperforms other methods (also see Table 1). Crucially, key implication of this result is that our algorithm requires fewer rounds and, therefore, less communication to converge. We empirically show the savings in the communication of EL in Section 4.
and 1
in (3), it (1" /2²)
4 Evaluation
We present here the empirical evaluation of EL and compare it with state-of-the-art DL baselines. We first describe the experimental setup and then show the performance of EL-Oracle and EL-Local.
4.1 Experimental setup
Network setup and implementation We deploy 96 DL nodes for each experiment, interconnected according to the evaluated topologies. When experimenting with s-regular topologies, each node maintains fixed degree of (Tog2(n)]; iee, each node has 7 neighbors. For EL--Oracle we introduce centralized coordinator (oracle) that generates a random 7-Regular topology at the start of each
7

---

Fully connected
EL-Local
EL-Oracle
7-Ragular static
8-U-EquiStatic
Tost accuracc [36]
60
Test accuracy [%]]
60
Test accuracy [%6]
66
+2. +2.2% accuracy
Test loss
40
65
1.5
40
64
20
20
2.9 GIB (17x
2
2.5
3
62
1
2
2
3
100 MiB
GiB
10 GBB
100 GiB
G
G
G
Communication round (x 10"))
Communication volume per node (log scale)
Figure 4: Communication rounds vs. top-1 test accuracy and (left) and communication volume per
node vs. test aceuracy (right) for the CIFAR-10 dataset.
round and informs all nodes about their neighbors for the upcoming round. For EL-Local we make each node aware of all other nodes at the start of the experiment. To remain consistent with other baselines, we fix = [1092(n)] = 7 when experimenting with EL, i.e., each node sends model updates to 7 other nodes each round. Both EL-Oracle and EL-Local were implemented using the Decentralize izeey framework [11] and Python 3,8 For reproducibility, a uniform seed was employed for all pseudo-random generators within each node.
Baselines We compare the performance of EI--Orace and EL-LLcal against three variants of D-PSGD. Our first baseline is a fully- cully-connected topology (referred to Fully connected), which presents itself as the upper bound for performance given its optimal convergence rate [1]. We also compare with a s-regular static topology, the non-changing counterpart of EL-Oracle (referred to as 7-Regular static). This topology is randomly generated at the start of each run according to the random seed, but is kept fixed during the learning. Finally, we compare EL against the communication-cii
topology U-Eqiittatic [53]. Since U-EquiStatic topologies can only have even degrees, we generate U-EquiStatic topologies with degree of 8 to ensure a fair comparison. We refer to this setting as 8 B-U-EquiStatic.
Learning task and partitioning We evaluate the baseline algorithms using the CIFAR-10 image classification dataset [26] and the FEMNIST dataset, the latter being part of the LEAF benchmark [7]. In this section we focus on the results for CIFAR-I0 and present the results for FEMNIST in Ap- pendix C.4. We employ a non-IID data partitioning using the Dirichlet distribution function [19], parameterized with 0.1. We use GN-LENET convolutional neural network [18]. Full details on our experimental setup and hyperparameter tuning can be found in Appendix C.I.
Metries We measure the average top-1 test accuracy and test loss of the model on the test set in the CIFAR-IO learning task every 20 communication rounds. Furthermore, we present the average top-1 I test accuracy against the cumulative outgoing communication per node in bytes. We also emphasize the number of communication rounds taken by EL to reach the best top-1 test accuracy of static 7 7-Regular topology. We run each experiment five times with different random seeds, and we present the average metrics with 95% confidence interval.
4.2
EL against baselines
Figure shows the performance of EL--Orace and EL--Local against the baselines for the CIFAR- dataset. D-PSGD over fully-connected topology achieves the highest accuracy, expected, but incurs more than an order of magnitude of additional communication. EL-Oracle converges faster than its static counterparts of ar static and 8-U AU-EquiStatic. After 3000 communication rounds, EL-Oracle and EL-Local achieve up to 2.2% higher accuracy compared to 7-Regular ar static (the most competitive baseline). Moreover, EL-Oracle takes up to 1.7x fewer communication rounds and saves 2.9 GiB of communication to reach the best accuracy attained by 7-Regular static. Surprisingly, 8 L-U-EquiStatis shows worse performance compared to 7 7-Regular static. The plots further highlight that the less constrained EL-Local variant has a very competitive performance compared to EL-Oracle: there is negligible utility loss when sampling locally compared to generating a s- Reggua graph every round. We provide additional observations and results in Appendix C.
"Souree code can be found at wttpg//phhoooosssollleeeoeeeeeee 2023.

---

Table 2: A summary of key experimental findings for the CIFAR- dataset.
Topology
Top-1 Test Accuracy
Top-1 Test Loss
Communication Target Accuracy
(%)
(GiB)
Fully connected
68.67
0.98
30.54
7-Regular static
64.32
1.21
7.03
8-U-EquiStatic"
62.72
1.28
Er.-Oracle
66.56
1.10
4.12
EL-Local
66.14
1.12
4.37
The 8-U-EquiStatic topology did not reach the 64.32% target accuracy.
EL-Oracle
EL-Local
EL-Oracle
7-regular static
7 -.-.. 4
14
Test accuracy [96]
60
80
65
50
40
40
20
30
2
MiB
100 MiB
GiB
10GiB
3BB
G
10GiB
Communication round (x100)
Communication volume per node (log scale)
Figure 5: The test accuracy of EL-Oracle and EL-Local (left) and communication volume per node of EL-Oracle (right) for different value of sample size and a 7-Regular static topology.
We summarize our main experimental findings in Table 2, which outlines the highest achieved top-1 test accuracy, lowest top-1 test loss, and communication cost to a particular target accuracy for our evaluated baselines. This target accuracy is chosen as the best top-1 test accuracy achieved by the 7-Regular static topology (64.32%), ), and the communication cost to reach this target accuracy is presented for all the topologies in the right-most column of Table 2. In summary, EL-Oracle and EL-Local converge faster and to higher accuracies compared to 7-Regular static and 8-U- EquiStatic topologies, and require 1.7x x and 1.6x less communication cost to reach the target accuracy, respectively.
4.3 Sensitivity Analysis of sample size
The sample size determines the number of outgoing neighbours of each node at each round of EL-Orack and EL-Local. We show the impact of this parameter on the test accuracy in the two left-most plots in Figure 5, for varying values of 8, against the baseline of 7-regular static graph. We chose the values of [10gg(1)] 4, and [2]] We observe that, as expected, increasing s leads to quicker convergence for both EL-Oracle and EL-Local (see Theorem 1). Increasing s also directly increases the communication volume. The two right-most plots in Figure show the test accuracy of EL-Oracle when the communication volume increases. After 3000 communication rounds, EL-Oracle with s 14 has incurred a communication volume of 15.1 GiB, compared to 4.3 GiB for = 4. An optimal value of depends on the network of the environment where EL is deployed. In data center settings where network links usually have high capacities, one can employ high value of s. In edge settings with limited network capacities, however, the value of should be smaller to avoid network congestion.
14, over and above [log2[n)] 7.
Related Work
Decentralized Parallel Stochastic Gradient Descent (D-PSGD) Stochastic Gradient Descent is stochastic variant of the gradient descent algorithm and is widely used to solve optimization problems at scale [14, 39, 46). Decentralized algorithms using SGD have gained significant adoption as method to train machine learning models, with Decentralized Parallel SGD (D-PSGD) being the most well-known DI. algorithm [15, 31-33, 49]. D-PSGD avoids server by relying on a communication topology describing how peers exchange their model updates [32].

---

Static topologies In a static topology, all nodes and edges remain fixed throughout the training process. The convergence speed of decentralized optimization algorithms closely depends on the mixing properties of the underlying topologies. There is large body of work [2, 3. 6, 40J studying the mixing time of different random graphs such as the Renyi graph and the geometric random graph. As the Erdos-Renyi graphs have better mixing properties [45], we compare EL with this family in Table 1. In [57], the authors prove that static exponential graphs in which nodes are connected to (log r)) neighbors are an effective topology for DL. EquiStatic is a static topology family whose consensus rate is independent of the network size [53].
Semi-dynami topologies Several DL algorithms impose fixed communication topology at the start of the training but have nodes communicate with random subsets of their neighbors each round. We classify such topologies as semi-dynamic topologies. The one-peer exponential graph has each node cycling through their O(log n) neighbors and has similar convergence rate to static exponential graphs [57]. In the AD-PSGD algorithm, each node independently trains and averages its model with the model of a randomly selected neighbour [33]. EquiDyn is a dynamic topology family whose consensus rate is independent of the network size [53].
Time-varying and randomized topologies A time-varying topology is a topology that changes throughout the training process [9]. The convergence properties of time-varying graphs in distributed optimization have been studied by various works [23, 35, 36, 43, 45]. While these works provide convergence guarantees for decentralized optimization algorithms over time-varying (or random) topologies, they do not show the superiority of randomized communication, and they do not prove a convergence rate that cannot be obtained with a static graph [53]. Another work [34] considers client subsampling in decentralized optimization where at each round, only a fraction of nodes participate in the learning procedure. This approach is orthogonal to the problem we consider in this paper.
Gossip Learning Closely related to EL-Local is gossip learning (GL), DL algorithm in which each node progresses through rounds independently from other peers [48]. In each round, a node sends their model another random node and aggregates incoming models received by other nodes, weighted by age. While GL shows competitive performance compared to centralized approaches [16, 17]. its convergence on non-convex loss functions has not been theoretically proven yet [47]. While high level, EL-Local with = may look very similar to GL, there are some subtle differences. First, GL operates an asynchronous manner whereas EL proceeds in synchronous rounds. Second, GL. applies weighted averaging when aggregating models, based on model age, and EL aggregates models unweighted. Third, if node in GL receives multiple models in a round, this node will aggregate the received model with its local model for each received model separately, whereas in EL, there will be a single model update per round, and all the received models from that round are aggregated together.
In contrast to the existing works, EL leverages a fully dynamic and random topology that changes each round. While static and semi-dynamic topologies have shown to be effective in certain settings, EL surpasses their performance by enabling faster convergence, both in theory and in practice.
6 Conclusions
We have introduced Epidemic Learning (EL), a new DL algorithm that accelerates model convergence and saves communication costs by leveraging randomized communication. The key idea of EL is that in each round, each node samples other nodes in a n-node network and sends their model updates to these sampled nodes. We introduced two variants of the sampling approach: EL-Oracle in which the communication topology forms a s-regular graph each round, and EL-Local which forms a s-out graph. We theoretically proved the convergence of both EL variants and derived that the number of transient iterations for EL is in O'n*/s²), outperforming the best-known bound O by a factor of 5² for smooth non-convex functions. Our experimental evaluation on the CIFAR-10 learning task showcases the 1.7x quicker convergence of EL compared to baselines and highlights the reduction in communication costs.
Acknowledgement
This work has been supported in part by the Swiss National Science Foundation (SNSF) project 200021-200477
10

---

References
[1] Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning, pages 344 353.. PMLR, 2019.
[2] Itai Benjamini, Gady Kozma, and Nicholas Wormald. The mixing time of the giant component of a random graph. Random Structures & AAlgorithms, 45(3):383-407, 2014.
[3] Andrew Beveridge and Jeanmarie Youngblood. The best mixing time for random walks on trees. Graphs and Combinatorics, 32:2211 1-2239, 2016.
[4] Léon Bottou, Frank E Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM review, 60(2):223-31, 2018.
[5] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Randomized gossip algorithms. IEEE transactions on information theory, 52(6):2508- 2530, 2006.
[6] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah. Mixing times for random walks geometric random graphs. In ALENEX/ANALCOO pages 240-249, 2005.
[7] Sebastian Caldas, Sai Meher Karthik Duddu, Peter Wu, Tian Li, Jakub Konečný, Brendan McMahan, Virginia Smith, and Ameet Talwalkar. Leaf: A benchmark for federated settings. arXiv preprint arXiv: 18/2.01097 2018
[8] Daniel Cason, Nenad Milosevic, Zarko Milosevic, and Fernando Pedone. Gossip consensus. In Proceedings of the 22nd International Middleware Conference, pages 299, 2021.
[9] Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distribuled Systems, 27(5):387-408, 2012.
[10] Yiming Chen, Kun Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip sgd with periodic global averaging. In International Conference on Machine Learning, pages 1791-1802, PMLR, 2021.
[11] Akash Dhasade, Anne-Marie Kermarrec, Rafael Pires, Rishi Sharma, and Milos Vujasinovic. Decentralized learning made easy with DecentralizePP. In 3rd Workshop Machine Learning and Systems, 2023. doi: 10. 00.114/33783563359555777
[12] Patrick T Eugster, Rachid Guerraoui, A-M Kermarrec, and Laurent Massoulié. Epidemic information dissemination distributed systems. Computer, 37(5):60-67, 2004.
[13] Alireza Fallah, Aryan Mokhtari, and Asuman Ozdaglar. Personalized federated learning with theoretical guarantees: A model-agnostic meta-learning approach. Advances in Neural Information Processing Systems, 33:3557-3568. 2020.
[14] Saeed Ghadimi and Guanghui Lan. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM Journal on Optimization, 23(4):2341-2368, 2013.
[15] Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation methods for nonconvex stochastic composite optimization. Mathematical Programming, 155 (1-2):267-300 2016.
[16] István Hegedūs, Gábor Danner, and Márk Jelasity. Gossip learning as a decentralized alternative to federated learning. In Distributed Applications and Interoperable Systems: 19th IFIP WG 6.1 International Conference, DAIS 2019, Held as Part of the 14th International Federated Conference Distributed Computing Techniques, DisCoTec 2019, Kongens Lyngby. Denmark, June 17-21, 2019, Proceedings 19, pages 74-90. Springer, 2019.
[17] István Hegedfís, Gábor Danner, and Márk Jelasity. Decentralized learning works: An empirical comparison of gossip learning and federated learning. Journal of Parallel and Distributed Computing, 148: 1111109-112 124, 2021.

---

[18] Kevin Hsich, Amar Phanishayee, Onur Mutlu, and Phillip Gibbons. The non-iid data quagmire of decentralized machine learning. In International Conference on Machine Learning, pages 4387-4398. PMLR, 2020.
[19] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification, arXiv preprint arXiv: arXiv:1909. 190::06399,33 2019.
[20] Márk Jelasity, Spyros Voulgaris, Rachid Guerraoui, Anne-Marie Kermarrec, and Maarten Van Steen. Gossip-based peer sampling, ACM Transactions on Computer Systems (TOCS), 25 (3):8es, 2007.
[21] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Ar- jun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. Advances and open problems in federated learning, Foundations and Trends in Machine Learning, 14(1-24) (111)):1-210, 2021.
[22] David Kempe, Alin Dobra, and Johannes Gehrke Gossip-based computation of aggregate information. In 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings. pagess 482-491. IEEE, 2003.
[23] Anastasia Koloskova, Sehastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, pages 1478-3487, PMLR, 2019.
[24] 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 Machine Learning, pages 5381-5393, PMLR, 2020.
[25] Lingjing Kong, Tao Lin, Anastasia Koloskova, Martin Jaggi, and Sebastian Stich. Consensus control for decentralized deep learning. In International Conference on Machine Learning, pages 5686-5696. PMLR, 2021.
[26] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The cifar- 10 dataset. 55(5), 2014. URL https://www cs. toronto. addu/krrzzcifat html.
[27] Batiste Le Bars, Aurélien Bellet, Mare Tommasi, Erick Lavoie, and Anne-Marie Kermarrec. Refined convergence and topology learning for decentralized sgd with heterogeneous data, In International Conference on Artificial Intelligence and Statistics, pages 1672-1702. PMLR, 2023.
[28] Mu Li, Li Zhou, Zichao Yang, Aaron Li, Fei Xia, David G Andersen, and Alexander Smola. Parameter server for distributed machine learning. In Big learning NIPS workshop, volume 2013.
[29] Mu Li, David G Andersen, Jun Woo Park, Alexander Smola, Amr Ahmed, Vanja Josifovski. James Long, Eugene J Shekita, and BoinY Su. Scaling distributed machine learning with the parameter server. In 11th (USENIX) Symposium on Operuting Systems Design and Implementation ({OSDI) 14), pages 583-598, 2014.
[30] Xiang Li, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Communication-efficieen local decentralized sgd methods. arXiv preprint arXiv: 1910.09 2019.
[31] Xiangru Lian, Yijun Huang, Yuncheng Li, and Liu. Asynchronous parallel stochastic gradient for nonconvex optimization. Advances in neural information processing systems, 28, 2015.
[32] 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.
[33] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu, Asynchronous decentralized parallel stochastic gradient descent. International Conference on Machine Learning, pages 3043-3052, PMI.R, 2018.
12

---

[34] Ziwei Liu, Anastasia Koloskova, Martin Jaggi, and Tao Lin. Decentralized stochastic optimiza- tion with client sampling. In OPT 2022: Optimization for Machine Learning (NeurIPS 2022
Workshop).
[35] Ilan Lobel and Asuman Ozdaglar. Distributed subgradient methods for convex optimization over random networks. IEEE' Transactions on Automatic Control, 56(6):1291-1306 2010.
[36] Songtao Lu and Chai Wah Wu. Decentralized stochastic non-convex optimization over weakly connected time-varying digraphs. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5770-5774. IEEE, 2020.
[37] Yucheng Lu and Christopher De Sa. Optimal complexity in decentralized training. In Interna- tional Conference on Machine Learning, pages 7111-7123. PMLR, 2021.
[38] Alberto Montresor. Gossip and epidemic protocols. Wiley encyclopedia of electrical and electronics engineering, 1, 2017.
[39] Eric Moulines and Francis Bach. Non-asymptotic analysis of stochastic approximation algo- rithms for machine learning. Advances in neural information processing systems, 24, 2011.
[40] Asaf Nachmias and Yuval Peres. Critical random graphs: diameter and mixing time. 2008.
[41] Brice Nédelec, Julian Tanke, Davide Frey. Pascal Molli, and Achour Mostéfaoui. An adaptive peer-sampling protocol for building networks of browsers. World Wide Web, 21(3):629-6611 2018.
[42] Angelia Nedic. Distributed gradient methods for convex machine learning problems in networks: Distributed optimization. IEEE Signal Processing Magazine, 97(3):22-011, 2020.
[43] Angelia Nedić and Alex Olshevsky. Distributed optimization over time-varying directed graphs IEEE Transactions on Automatic Control, 60(3):601-613 2014.
[44] Angelia Nedić and Alex Olshevsky. Stochastic gradient-pus push for strongly convex functions on time-varying directed graphs. IEEE Transactions on Automatic Control, ((12):3936-3947 2016.
[45] Angelia Nedić, Alex Olshevsky, and Michael G Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. Proceedings of the IEEE, 106(5):953-975 2018.
[46] Arkadi Nemirovski, Anatoli Juditsky. Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization, 19(4): 1574-1609, 2009.
[47] Noa Onoszko, Gustav Karlsson, Olof Mogren, and Edvin Listo 7ec Decentralized federated learning of deep neural networks on non-iid data. arXiv preprint arXiv:2107 08517, 2021.
[48] Róbert Ormándi, István Hegedũs, and Márk Jelasity. Gossip learning with linear models on fully distributed data. Concurrency and Computation: Practice and Experience, 25(4):556-571, 2013.
[49] Pitch Patarasuk and Xin Yuan. Bandwidth optimal all-reduce algorithms for clusters of worksta- tions. Journal of Parallel and Distributed Computing, 69(2): 17-1244 2009.
[50] Shi Pu, Alex Olshevsky, and loannis Ch Paschalidis. A sharp estimate on the transient time of distributed stochastic gradient descent. IEEE Transactions on Automatic Control, 67(11): 5900-5915, 2021.
[51] Alexander Rogozin, Alexander Gasnikov, Aleksander Beznosikov, and Dmitry Kovalev. De- centralized optimization over time-varying graphs: a survey. arXiv preprint arX1v:2210.09719, 2022.
[52] Kevin Scaman, Francis Bach, Sébastien Bubeck, Laurent Massoulié, and Yin Tat Lee. Op- timal algorithms for non-smooth distributed optimization networks. Advances in Neural Information Processing Systems, 31, 2018.
13

---

[53] Zhuoqing Song, Weijian Li, Kexin Jin, Lei Shi, Ming Yan, Wotao Yin, and Kun Yuan. Commumication-eficn topologies for decentralized learning with So(1)S consensus rate. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022. URL http:///pppereeeeeeeeeeeeeeeeeee AyiiHcRzTd.
[54] Thijs Vogels, Hadrien Hendrikx, and Martin Jaggi. Beyond spectral gap (extended): The role of the topology decentralized learning. arXiv preprint arXiv:2301.02152 2023.
[55] Spyros Voulgaris, Daniela Gavidia, and Maarten Van Steen. Cyclon: Inexpensive membership management for unstructured p2p overlays. Journal Network and systems Management, 13: 197-217, 2005.
[56] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. 2019 Sixth Indian Control Conference (ICC), pages 299-300. IEEE, 2019.
[57] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph is provably efficient for decentralized deep training. Advances Neural Information Processing Systems, 34:13975-13987 2021.
[58] Bicheng Ying, Kun Yuan, Hanbin Hu, Yiming Chen, and Wotao Yin. Bluefog: Make decentral- ized algorithms practical for optimization and deep learning. arXiv preprint arXiv: I.04287, 2021.
14

---

Appendix
Organization
The appendices are organized as follows:
Appendix proves the convergence guarantee of EL.
In Appendix B, we prove the key lemmas that are used in the convergence proof.
Appendix C provides experimental details, computational resources used, and further eval- uation EL with independent and identically distributed (IID) data distributions and the FEMNIST dataset.
In Appendix D, we discuss the effect of network connectivity on the performance of EL.
A Convergence Proof
In this section, we prove Theorem 1, by setting
n TLo
Ao
1 20L
7 7: min
(4)
100T L2 (o² H22)
for El.-Oracle, and
A (21102 + 3328,7(3) L' 2507 L2 12 (02 +
nAo
= min
(5)
T
20L
for EL-Local.
Notation:
For any set of n vectors {2(11, ,..., (n)),, we denote their average by = 1 Eiena x(0)
A.1
Proof steps
We outline here the critical elements for proving Theorem 1.
Mixing efficiency of EL. First, we analyze the mixing properties of the communication phase of both variants of the algorithm, and observe that:
(a) while EL-Oracle preserves the exact average of the local vectors, i.e., T.+1 = T/+ EL- Local only does so expectation. This property is critical for ensuring that the global update is unbiased estimator of the average of local gradients, which is necessary for obtaining convergence guarantees with linear speed-up.
(b) The communication phase of both EL-Local and EL-Oracle reduce the drift among the local models by a factor of (11s).
(c) The variance of the averaged model after the communication phase, in EL-Local in (1/ns).
More formally, have the following lemma.
15

---

Lemma 1. Consider Algorithm Let n 2, 8 1, 2 2 1, and & {o...., 13.
1. For EL-Oracle, have
(a) T+41 = 2/2-2/21
(b) 1/2 Dise(n) B
10)
( 2
Sas +22 Eiselm)
E
(1) ( 12]
241/2
where
(1 11- 8 - ===1(0(2
0g = 8 s+1
2. For EL-Local, we have:
(a) E [Tee+]] = E [114//2] (Note that we do not necessarily have Tz+1 T141/2h
(b) # EijemH E [ x(+1
(5)
|
S B. 1 Eije(mn)
1141/2 14/1/2
(c) || 2041/212]
N Ende(m) $|l2ff12 #111/21 119.
S 2n
where
1 11-11-10 n (1-=-))) B. s
n - E
Uniform bound on model drift and gradient drift. Next, using the previous lemma, prove that, for a careful choice of the step-size 7, the local models stay close to each other during the learning process.
Lemma 2. Suppose that assumptions 1, 2, and 3 hold true. Consider Algorithm Consider a 1
step-size y such that 7 '20L. For any t O, obtain that
(6)
xz 101"
S 20
70 (o² + H22 (1 T/a
1 3n,
n2
and
gr of 1/"11p]
Σ iJE(m)
102 + +²²).
n
where 7)s Os for EL-Oracle and n, Ba for EL-Local defined in Lemma
Bound on the gradient norm. Next, we obtain a bound on the gradient of the loss function F(x) by analyzing the growth of F(x), over the trajectory of the average of local models in Algorithm 1.
Lemma 3. Suppose that assumptions and 2 hold true. Consider Algorithm with 7 z.. For any / E (O....,T T 1}. we obtain that
E
VF (2))1
< [(F((t) - F((++1)] +
I
E
(3)
(1) x
||
2n
+ 2L 0²
+
2T
-E
E
[ T2+1/21 18]
7
A.2 Proof of Theorem
We now prove the theorem using the above lemmas.
16

---

Proof of Theorem 1. By Young's inequality, for any i E [n], we have
E
VF
Jt (1)
(=)) 2 |IV (
+2 VF (3t)
VF
(3)
||
2 [IF
(#:)]l
21
| 2(11
(1)
17.
where in the second inequality we used Assumption 1. Then, averaging over i E [n], we obtain that
1 ΣΣ
||F
# >1'l'
2
|FF (1.)
+L E
1
n iE(n)
iE(m
2 |VF (3.)
L2
E
(
2. 11]
(JE(M]
where we used Lemma 5. Combining this with Lemma 3, we obtain that*
Σ
E
VF
Ft
(8)
I''
$
4
[F
F(E++1))
21 n²
22.00
11]
n iE[n]
02 4L
Fot1 - Ze 8e4
(6)
n
We now analyze the two variants of the algorithm separately.
EL-Oracle:
In this case, by Property (2a) of Lemma 1, we have ēz41
I2+1/2
0, therefore, by (6), we have
1 E
F
19
[]] <
4 - 7 - F(0++1)]+
E(F(E))
2L2
Σ
E
x2
(1)
(1)
|1=
2
4L7
o²
n²
n
kEIn
Note also that by Lemma 1, we have
21
S 20 1 + 30
(1 a,) a,? (o² + +1²)
n²
1.jE|n]
Moreover, as shown in Remark 2, we have ar 1/2, and thus, 20 [1-o.)² I 200. Therefore,
Σ E
11
111 200a,,² >2 20020=+20++000000000
n
Combining this with (7), we obtain that
Σ
E
V
F
3
|
4 [((.))
- F( 400a,L??? (o2 + +H²) + 447- o²
7
sEin]
Averaging over E {O.....
1}. we obtain that
E
VF
19
4 (FF(s)) +(0r)))4000,1 1:272 (0²+
+ +H2) + 4I, o²
nT
7T
iE|n]
t=
4
Ao 400a, (0² + H22 + 4L o² n
(8)
I
where we used the fact that F(5o) F ((TT) S F(To) min F(x) s Do. Setting
ndo
Ao 100Ta, (o2 + H2) 20L
1
= min
(9)
T
'In order obtain bound on E (x:)). we skip this step and directly Lemma 3.
17

---

as min(a.b) = mmx{ 1 i for any a, 2 0, we have
1
1 max
TL n
100Ta, L2 [o² + H2a
TLo²
1000 L22 (o2 + H22)
20L
+
+ +00,,
Ao
nao
4o
(10)
Plugging (9) and (10) in (8), we obtain that
|
T.D
0g 1 (a² + H2)
80LAo
E
VF
F
8V
+ +38
n
nT
T
T
T.4
Ogg 1. D (a² + +
LAo
E
E0
+
nT
T
T
where we used the fact that
800 100
S 38.
EL-Local:
The proof is similar to EL-Oracle, up to some additional error terms. By Property (2c) of Lemma 1, we obtain that
E || 2,44/=10
11]
2n
8.
2
E
241/2
2411/
(1)
19]
[JE(m]
B2
Σ
E
79;
(3) - -xe + +7g.") |11
(1)
(11)
2n
?
(JE(M]
B.
(
(1)
2
233
1
E
2
+
Di
n
1.jE(n]
i.jE(n]
(12)
where in the last inequality we use Young's inequality. Combining this with (6), we obtain that
E
VF
VF
(z)
17]
<
4
B[F(E.) F(
2L
E
i
( ||]
7
n2
SE[n
(JE(M)
4Ly
02
4L
3
1
Σ E
||
(
6
4L
1
E
96
(1)
06
[|]
n
7
n
a
n²
1.jE|m]
(.j((n]
EF((()) F( + (2L2+
4
+
ALB.
1
E
24
(8)
(3)
7
TUY
(.jE(z]
0² + + 4Ly
4LAB.
1
Σ E
96
9
[1]
(13)
n
n
Note that by Remark 2, for any s 2 1, and n 2 2 we have 3, $ 1 2. where is Euler's number. Therefore,
1 + 33,
20
S 500.
(1 3.)2
Using this, the first bound in Lemma can be simplified to
Σ
E
10 - 50033,2 (o² + H²))
(14)
n
(J((m)
Combining this with (13), and the second bound of Lemma 2, we have
Σ
VF
(1))
AL- < A B[F(E.) F(I++)())+)) 4L (1 153, + 5003?)
+ 4Ly H2
(153, + 50033) + 121000 (o² + H2)
18

---

Taking the average over E {o...., T - 1}, we obtain that
ΣΣE nf
4
VF +
-
Do
4
(1+ 153, + 5005?)
Ty
n
1=0 EE(n]
H2
+
4 n
(153, + 500 + 1'10003 (o² +H?).
Noting that Bg 1 (Remark 2), we have
[|]
4 Ty
4 La
R VF
<
Do
(2110² 332,,3(2) + 1000,, (o² + H²²
nT
n
1=0
(E(n)
(15)
Now, setting
nAo
Ao 2507 250T L2 (a² + 112) 20T
(16)
(2110 332,, L
we have
T (211o 3323,3339
250T 3, (o2 + H22) 20T.
max
n.pp
Ao
T (2110² + 3328, H²) L
250T B2L (a² + H2² + 20L
(17)
nāo
An
Plugging (17), and (16) in (15) we obtain that
ΣΣ
VF 0 )0]
LAo (211 + 3323,H2)
B,L2 (a2
H22
80L
8/
+ +51
Ao
nf
nT
T
T
(E(M)
La + 3.H22 0
A.L (o² + H2)
LAu
nT
72
T
where we used the fact that
2000 250
< 51. This concludes the proof.
B Proof of the main lemmas
Notation: Let Pt represent the history from step 0 More precisely, we define
P
2o (8)
i = 1, 1,
Moreover, we use the notation [-] E P.)] denote the conditional expectation given the history Pt and E [-] to denote the total expectation over the randomness of the algorithm; therefore have, [-] Eo Er [:]]-
We first prove two simple useful lemmas.
Lemma 4. for any set of vectors (11)
(k), we have
Σ
x
(
Proof. By the triangle inequality, we have
k
Σ
x
x
iml
19

---

The result then follows by noting that using Jensen's 's inequality, we have
h
2
h
Σ
(
S
1:
h
Lemma 5. For any set (x((1)
[se[n] of n vectors, we have
Σ 7
1
1
Σ (.j(nn]
|0(00
-600
sE(mi
Proof.
(1()
||
1
Σ
(o!10) - 5) -))(1)1)) - -z)|
n
n
[JE(m)
(jE(n]
1
(0(())
2
|z(00 - x
+ x1()
2, x(1) xx)= =z)
+
n
2
2
+
x(1) - Ez Σ
(z((i B))
n
[E[m)
jELn]
Noting that Σ EnEnn - x) = 0. yields the desired result.
B.1 Proof of Lemma 1
Lemma 1, Consider Algorithm Let 2 2, 8 2 1,72 1, and E (O...., T 13.
1. For EL-Oracle, we have
(a) Ft-1 = F2+1/2-
(b) 1 Eije(n)
(3) 2 (1) - -1-11 |
S as # Eije(n E
a 2 1/2
(
where
E = 1
0g
1- n2
5 ++1
2. For EL-Local, we have:
(a) E [[r441l E [r41/a| (Note that we do not necessarily have Te+1 T/-
(b) 1 n² Eije(m | - x 11² $ B. d Eisejm E
(3)
|| - 14//33 11?
(1)
|| = 11)
(c) E || - 8241/11
9. 1/2 Ensejn E
where
B, = 1 (1 - n n- (1) n-1 E )
Proof. For simplicity of the notation, make the dependence / implicit, and denote by z(() == (6)) "41/2" the input vector and ( = 2/2 the output vector of node for the communication
phase, and s()) = s( Therefore, we have
y0
x +
Σ x(ا)
8(1)
+1
JES())
20

---

Moreover, in the proof of this lemma, all the expectations E [ are only with respect to the randomness of the communication phase, i.c., we compute the expectations assuming 2'''s are given for all i E [n], and y(t's 's are computed by a random communication phase. Taking the total expectation of the final expression provided for each property then proves it as stated in the lemma.
First, we consider EL-Oracle:
Recall that in EL-Oracle, the communication topology forms random undirected s-regular graph, and for each node i, all other nodes have the same probability of being i's neighbor.
Property (a): We have
1
Σ EEIm]
(0
x1() +
Σ
xl1)
S(6) +1
iE|n)
jESÚO
x
+
Σ
I
n
+
sE(m
jES((
Σ iE(m)
+
Σ
Σ
x6)
n(s+1)
where we used the fact that in EL-Oracle, each node receives exactly & models. Now as each node also sends its model to other nodes, we have
Σ iE|n]
( + Σ
(1)
Σ (0)
E.
n(8 + 1)
n <E(m]
KE
(m
Property (b): We have
(1)
27
Σ EE(M)
E
x(1)
Σ x(0)
1 vE(m)
n
Sti) +1 1
jESO)
1
B
(w((1)
5) +
(z0()) T)
n(8 + 1)2
vE(xe]
JES()
1
(0(0)) T
E
Σ
(x0t) - F)
n18 1)2
(8 1)2 VEinn
(E[x)
JESO)
((69))
+ T1(s + 1)2
2
Σ
E
(c(0) Z).
Σ (z(0) - x3)
(18)
SE[n]
jES())
21

---

Let us define 7 the indicator function showing whether node j and node are neighbors, i.e.,
if and j neighbors and _
0 otherwise. We then have
Σ iE/n]
E
Σ JES(
(xlt)
B)
Σ E
Σ sEIn|/Es3
x)
ie(n)
Σ
E
Σ
7/00
|a00)
+
E
Σ
Σ
I ( (x,))-
B, (0()) -x)
(iE(m)Mt
iE(n
jtt
Σ
Σ
[300
ΣΣ
(1) (xl)) - I, x - 2
#
je/n/
SEin| Jæi kgi,k
Now note that by symmetry (all nodes have the same probability of being neighbor of node i).
Similarly I/ is only when both j and As are neighbors of i, thus
8(8 8(8-1) 1) (n 1) - 2)
I 10 I
Therefore,
Σ vE(x))
E
Σ
(z(()
z)
s Σ
2
Σ
E
Σ
s(8 118-1] 1) (z6))
I, x(() 3)
( - 2)
jESO
iE/m]
vE(n) jtt Ao
Σ
(2(()) I
Σ
8(3 - (2(0) - 3, x(1) - x
n
kc|m
(19)
Also,
Σ E
(o(1)
-x) x). Σ (z(() -x)
Σ
(z(() -6),
x), Σ E [Z(00 (x(() - x)
ie(n]
jES())
iE(ml
j
(1) F, v05 xx)
(20)
n
iEin) iæi
Combining (18), (19), and (20) we obtain that
Σ
E
1+s
(1)
(21)
71
(8
1)2
sE(m]
VE(x]
2s
8(8
(00))
2, x1)) - x.)
(ss + 1)2
12
n
ie غزز
Also note that
ΣΣ iE[n] jæi
- 2, 266 -5) 2)
Σ
((0) 21
200
Σ
(0(()) -
(22)
(x(x)
j7i
15(m)
Combining (21) and (22), we obtain that
E (+)
|
1
Σ
1
|
(23)
8 s+1
1
[r]
22

---

Now note that as y the minimizer of g(2) n
1
Eigin
||l(() - = ==1²]. we have
Σ
E
E
(0(0)
x |17
(24)
72
8Ein]
Combining this with (23), and using Lemma 5 yields
1 Σ E [jE(m]
1
1 s+1
1
E A.jE(n]
n
8
n
n2
which is the desired result.
Now, we consider EL-Local:
Recall that in EL-Local, each node i, locally samples uniformly at random other nodes and sends its model to them. Denote by A == g(0 the number of nodes that send their vectors to node i,
and Z the indicator showing whether node j sends its vector to node or not (z) i its model to i, and z(6) = 0 otherwise). We then have
sends
A
Σ 1
jE(N/M
and
E
A(0)
Property (a):
For any node i, we have
E
(8)
E
2 +
Σ
2
A(
+
JEMNE(
E
E
2/9000
(A(
A
+1
jElo]V())
E
2 +
Σ |E
E
|A0
A0) +1
A
(a)
(0( +
Σ x66)
E
A +1
n
--1
1
jE[m]M{t
A0
E
(1)
(NT 2(()))
A(E)
where (a) uses the fact that EE
[A(1)
(4)
as all other n nodes have the same probability
I
of sending their model to Denoting p = E
A
we obtain that
A
pn
pr
(0)
Averaging over all E [n]] yields the result.
23

---

Property (b): We have
E
x + Σ
x00
A +
iE(n]
JE(1]((
1
E
x09 +
Σ
- 2
(A4())
11
A +1
VE mm]
2
1
Σ
E
(x x) + E
(x
x))
1A(0)
12 EE [x]
A +1
jE(n|({1}
1 Σ
E
1
E
(0(0)
2
+ Σ
(8)
xb61
14(0)
(AO) + 1)2
11 iE(m)
jti
- Σ
E
E
2 > I 01
(
(00
2, x(1)
- x)
Σ Σ
I (xl)) (2,)) x(1)
I,
xx)
14(0)
(AO) + 1)
Hi k
Taking the expectation inside, we obtain that
(|20)= -x
||
E 1 14 |0000 (e(0==1²)
E
E
71
n
(A()
+ 1)2
vE(m)
iE(n)
H
1
(3) [4(0) (w00) - Ft, x0 -+)
E
2
E
(A() + 1)2
iE|n]
E 1 ( - x, (1) x) '1
+
E
Σ
(A + 1)2
Ji Reght,
Now note that (1(0) [A(0] thus
the probability that j selects i, given that in total A nodes select i,
A
E (0)
[90)
Similarly I is only when both j and l: select i, thus
A (A(() - 1)
E I
A4 = (n - 1)(12 - 2)
Also, note that
Σ 1
(0)
I, (0 - x8
F, Σ
(1 x))
= =-1000 10000 x
x
1+1
and
ΣΣ (a0) - I, (A) - 1 = Σ
2(1) I, Σ (x) - x))
jti keikkt
sti
kti
Σ
(z()) -,, (z(() - x) + (c(t)) -z)
= (2
Σ
(116) x 2
jt
24

---

Combining all yields
E
E
1
|1000 x
=|?
+
A
Σ
2001
-000==11]
(A(1) + 1)²
VE(N]
|E[n]
372
1
|,(0)) - x
x =11
E
(A(o) + 1)2
12
im(m]
1 )
A (A 1)
||000 - 5
1| -
2
(2000 - $8 1
E
Σ
(A(* + 1)2
(n 1) 2)
ic|n]
j
1
Σ
(x(()) x
E
1
(1- 2A()
(n- - 1)(n - 22 )
A -11
71
(AO) + 1)2
KE(M]
E
1
A
A (A -11 1)
)
Σ
p000 x 1
(AO) + 1)²
1
(n 1) 2)
sE[M]
Now note that by symmetry, the distribution of (1) is the same as A for any i,j E [n]]. Therefore,
E
-
1
(1)
E
(AAC)) + +12 (1- 24(1)
1
+ (0((A)) 11)
+ +40) (1(( -1)
n
n - 1
(n 1)(n 2)
n-
Now note that
(1
100 - 1)
+ A1)) (A(L) - 1)
1O02 + A(1)
A0
1 n- n-1
+ A
(1+ )1
(n 1)(n 2)
n 2
n n-1
7
thus
11]
1
A
Σ RE|D]
x
1
I
E
E
A(1) +1
12
A
Now note that as each node * 1, independently and uniformly selects set of nodes, A has binomial distribution with parameters n - 1, and R- Therefore, for 8 > O, we have
h
n-1-k
S
E
1
A
+1
+ 1
k
n 1
k=0
k+1
n-1-k
n
n
s
8
1
87L
k:
+
n1 1
n
km0
n 1
1
sn
Also noting that
A01)
1
=1 E
A(1) + 1
A(1 + 1
we obtain that
1
Σ
E
(0))
17
1 1 1
)")
1
Σ
20 -2|?
(25)
n iE[n
n
n
25

---

Noting that 1.4 n Eie(n
E
|1y(0)
0/1²] +/ n Eigin -|1(0)=
=1²]
from (24), and using Lemma
we obtain that
Σ 11000000111
1 - (1 n
1--1---- (---)))) - Σ
2o(0) - 2110 [2]
-
E
n
which is the desired result.
Property (c): Note that
[ - x
E
Σ
y
-5
71
iE|n
E
y (2)
2
(6)
J, (0) 2)}
(26)
n
n2 i
(m(m)
Now recall that
y
1
(z(1) (x(0)))++
Σ
(x(()) -x))
A +
This implics that
(1 -2,
2, 90 -
(a - I, x(1)
E
E
n
(A(H) 1)(AG) + +1)
iE(n) jt
2
(a!t) -I, x(1) - ②)
+
E
n
(AO) + ()()) + +1)
(E(m] jæt kzin
2
ΣΣ Σ
Σ
I I(2)
(o(1) - x, x11
+
n
(A(1 + ()((() + 1)
iEin] jæi ke LANNEA
Now note that by symmetry, for any i,j E [ni]. we have
E
(A() + ()(A)) +1)
(A() + +1((122 +1)
Similarly.
I1(0)
I
E
=E
(A + ()) + 1)
(A() + ()((2)) + +1)
and
I I(- (i)
I I12 (A() + (A((2) +1)
E
-E
(A + 1)(A() 11
This implies that all three terms in (27) can be written as
ΣΣ
200) F, x61 x60) x)
TE|M
where c is positive constant. We also have
Σ
( (0) 2, x0) - x)) x)= =
Σ
(()) I, Σ (x0)) - x)
1E(n] j
(E(m)
371
Σ
(e(()) 5
26

---

Therefore all the terms in (27) are non non-posiiive. Combining this with (26), we obtain that
E
=1
E
x
n
82
2
2
n
AE(m]
where the second inequality uses (25). Combining this with Lemma 5 then concludes the proof.
Remark Note that 3g computed Lemma is decreasing in and increasing in n, therefore, for any 1, and 2, we have
3. n2000
S lim 11-00
B1
1
lim
1-
n-000
n2
-
n2
where e is Euler's 's Number and we used the fact that lim (1
1 Similarly, for any
2 1, and n 2 2, we have
1 1 <
Ols
lim a1
nx000
n-+00
2
e
B.2 Proof of Lemma
Lemma 2. Suppose that assumptions 1, 2, and 3 hold true. Consider Algorithm 1. Consider step-size y such that y 1. For any 1 O, we obtain that
Σ
(4)
x2 100
< 20
(o² + H?2) (1 7T
+ 3n,
7
n
AJE|n]
and
Σ
(
15 (0² + H22
91
(JE(m)
where 7) for EL-Oracle and ne Ba for EL-Local defined in Lemma I.
Proof.
First note that for any E [n.]. we have
9t 9: Dt (4)
((( 2 + (
(7.) + V (x+)
- (z+) + (( (ix) vQ66
(1 () (2 ()
Thus, using Lemma 4, we have
|0.t
6)
V (1) (200) /
4 1o ( (100) - v (5t)
< 5
+
(
(2(1) - 1 (क+)
5
(6 (1
+ ( (zx) の (5>)
Taking the conditional expectation, have
E,
g
(4)
9. [01
< 5E,
9: ( (
(
x 1|"
(1)
+ 5E,
(1 v (ot)
+ 5E,
( ( w (a.) 12
+ 5E,
()
(() (x+4 - v (मx) [|]
+ 5E,
(28)
27

---

Now by Assumption 2, we have
Ex
ge
(()
(zf 11 sof
(29)
By Assumption we have
E
|
(1)
Ft
(1)
V T (x+) ||]
2 L.
|106" Et 1
(30)
Thus, by Assumption 3, and Lemma 5, we obtain that
E2
v
(ax)
V
())
- 2712
(31)
n
Combining (28), (29), (30), and (31), and taking total expectation from both sides, we obtain that
Σ
E
(
1
100²
E
(0
2
10o 1072.
(32)
n
[JE(M]
(E(r)
Now Lemma 5 yields
Σ
E
(1)
10
5L2
E
(0) x
- x
19
+ 100 + 1032.
(33)
n
n
LJE(M)
We now analyze
πσ Eiseja E
(1) 2
From Algorithm 1, recall that for all E [n]. we
have: I 2+1/2 1/
(1)
-7
(i)
We obtain for all i, I E [n]. that
(1)
- 2/// 11
( - [(0) -7 gs
)
27
$ E
ge.
(34)
441/2
$ (1 + c) E
(x0()) - x1 101]]]]]
+ (+
2 E
1100
0i
9.
"
where we used the fact that (x + y)² < (1 c)2² (1+ 1/c8y² for any O. Now recall that
7. as for EL-Oracle, and 1/4- = 3, for EL-Local. Therefore, by Property (b) of Lemma 1, for both
variant of the algorithm, we have
27
T++1
S
2et1/2 - 2441/2
n
KE(M)
rE(m)
Then, applying Lemma we have
2
1 n
Σ
E
- G0
12
n
44
441/2
1441/2
Combining this with (34), we obtain that
1
Σ
E
=2111]]
< c)
1
Σ [
E
22(0) - -2 22,311
n
n
KJE[n]
0 g. 1301
+ 1
n
2
Σ
E
n
[
For
1-9, Anz
obtain that
1
ΣE
E
(8)
0) 21
2
1 3ns
1
Σ E
n2
n2
+ 311s
Σ
E
9
(2)
96 16019
7
n²
(.jE(m)
28

---

Combining this with (33), we obtain that
ΣE
(
1/
37/a
1
(1)
2
1411
E
n2
n2a
1
3n, ?
5T.2
E
22
(1)
- 21.00
+ 1002 107(2
7
n2
{.)((m]
+ 31,
1
+ 37,
1 Σ B
5
NT 7 L?
4
1 1/3
n²
Jel(
1 31
7 (100² + 107H))
7
Now note that for by Remark 2, for both variants of the algorithm, we have 7/s S 1 2 which implies that
(1 n1
7² S
S
(20
20m (1 + 31, L2
Therefore,
Σ E
1
121
11 42
|
S 2 n²
1 1+
Σ
E
2 - -1
1 3n, ns
7 (10o² + 1074))
AJE(n]
(JE(M]
Unrolling the recursion, we obtain that
Σ
-
(
101
20
(1 11 77 (o2 + H2.
1+ 31/
Combining this with (32), we obtain that
Σ
(
15 (o² + + o6 13
E
9i
This is the desired result.
B.3 Proof of Lemma 3
Lemma 3. Suppose that assumptions and hold true, Consider Algorithm I with 7 S 21. For any
E (O...., T 1}, we obtain that
V (T))p < [(F(Tt) - F( +
I
Σ
(
[1]
x
2n
{.jE[n]
+ 2 0²
+ =
2L
E | - -141/21' 12]
Consider arbitrary [T]. Note that, do not necessarily have T441 T241/2- But by Lemma we have [5e+1] E [.++/.] Now by the smoothness of the loss function (Assump- tion 1). we have
Proof.
F(3+1)) - F(tx)= < (8e+1 Fz, VF (ix)) + L ||++11 - Tell2
2
= (āt+1 Te41/o + B241/2 Rr, VF (āx)) + 2 || B,41/o + B241/2 xzll?
29

---

Now denoting VF. 1 /E V/ (z!"). 9t Ei 9f and taking the conditional expectation, we have
E, [F( F(t) s (E, [e41122 - - VF (*.)) 2
4
E. || - Fe41/2 + F241/2 - =zll
Frr, VF (a.) + 2
|10 ||] + LBr ||a2|1 - # 11
m/ F.. 4 VF ( L
||FF,l + Ln2 2020² + LB, [| Fe+ 1/2 113
n
(35)
where (a) uses Young's inequality and (b) is based on the facts that by Assumption 2, we have
Ee 7ell = Ff and E,
||. VF&ll'
||]
e²a Now note that using the fact that 7 S z. we have
-7 VFF, VF (a.) + 4 |F 2 (-2 VF + ||FF, (1 11²)
(- ||F (I. |1 + VF - vF.ll"). (36)
Combining (35), and (36), we obtain that E, [F([==1]] - F S Taking total expectation, we obtain that
2 VF (x:)11
2
VF (zx) - vF,1? + L 00 + LE, || -
+
2
2
_ E B[ F -
(z.) [2 + [ (a.)) -V.1)
2
+ L -
LE
|8441 1//1/2 17]
(37)
n
Now, note that
E
VF.
VF [F)))
=E
(z( Σ
(3.)
<E(M)
(6) ( - 1 (G.))
E
EEID)
(4 (1) / (5x) 1|]
E
11
(0)
L2
E
It
(6)
L
E
(
5
2
2n
M
where (a) uses Assumption 1, in (b), we used Lemma 5. Combining this with (37), we obtain that
E [F((++1)) -((x)) < - ? E
|VF (m.))
L
(
2
+ 2 2n
E
+ L2200 + LE
[i+t1 - Be41/21 12]
Rearranging the terms we have
E
V |VF
(2)))
<
E [FF())) F(Fe+1)]
+ 1
Σ
E
( - 2
|1]
2n
2L o² 2T
[| B241/a 1|] 13]
E
n
30

---

Table 3: Summary of learning parameters used for evaluation. For each dataset, batch size (b), and the number of training steps per communication round (r) are presented.
TRAINING SAMPLES
TOTAL PARAMETERS
TASK
DATASET
MODEL
b
Image Classification
CIFAR-10 FEMNIST
GN-LeNet
8
3
50000
89 834
Image Classification
CNN
16
7
734463
690 046
EL-Oracle
R-Reglr static
8-U EquiStatic
Y 0.01
0.05
0.1
Tost accuracy [96]
60
Test accuracy [%6]
60
Tost accuracy [%%]
60
40
40
40
20
20
Communication round (x10*)
Figure 6: The test accuracy for EL-Oracle, 7-Regular static topologies, and 8- B-U-EquiStatic topologies with different learning rates y, with the CIFAR-10 dataset.
which is the lemma.
C Experimental Details and Further Evaluation
C.1 Experiment setup and learning rate tuning
Table 3 provides summary of the learning parameters, model, and dataset used in the experiments. The models were evaluated on samples from the test set that were unseen during training. The step size (7) was tuned by running each baseline validation accuracy. The plots in Figure show the CIFAR-I0 convergence plots for EL-Oracle, 7 7-Regular static, and 8 8-U-EquiStatia (most prominent topologies) over different step sizes. The optimal step-sizes are y = 0.1 for Fully connected and 8-U L-U-EquiStatic, and y = 0.05 for the remaining algorithms and topologies over CIFAR-10. 10. For FEMNIST, the optimal step size is y = 0.1 for algorithms and topologies. All experiments in Section 4 were conducted for a total of 3000 communication rounds and the experiments for homogeneous data distributions of CIFAR-10 (Figure 7) were conducted for a total of 1000 communication rounds. The experiments over the FEMNIST dataset were conducted for total of 1440 communication rounds.
range of values and taking the setup with the best
C.2 Computational resources
We perform experiments on hyperthreading-enabbe -enbbllle machines with dual Intel(R) Xeon(R) CPU ES-2630 v3 @ 2.40GHz of cores. All algorithms were implemented as part of Decentralizepy [11]. Each DL node was assigned virtual cores. An experiment took most hours in wall-clock time for experiments in Section 4, 2 hours in wall-clock time for FEMNIST experiments. and 1 hour in wall-clock time for CIFAR-10 experiments in Appendix C, summing to a total of 1152 virtual CPU hours. Across all experiments that are presented in this article, including different seeds and learning rate tuning, the total virtual CPU time goes up to approximately 54 700 hours.
C.3 Experiments with homogeneous data distributions
In this experiment, we focused on evaluating the performance of different communication topologies under IID data. The data was generated using Dirichlet distribution with 1.0. As reference
31

---

Fully connected -......
EL-Local
EL-Oracle ---.-.
7-Regular static
8-U-EquiStatic
71
Test accuracy [%6]
Test accuracy [%]]
Tea socuracy [%0]
60
Test loss
60
70
72
1.5
40
69
20
20
68
10
10
100 MiB
G
10
1.BBBB
2GBB
3GBB
Communication round (x 1x%)
Communication volume per node (log scale)
Figure 7: Convergence and communication usage results for homogeneous data partitioning (Dirichlet distribution a 1.0) of the CIFAR-10 dataset.
Fully connected monoo
EL-Local
EL-Oracle - 7- 7-Regular static
8-U-EquiStatic
Test accuracy [%6
80
Test acouracy [%]]
87.2
Test accuracy
60
Test loss
60
87
86.8
86
20
20
86.6
0.5
0.5
G
10 Gi
100
GiB
ITE
GiB
500 GiB
TiB
Communication round )
Communication volume per node (log scale)
Figure 8: Communication rounds vs. top-1 test accuracy and (left) and communication volume per node test accuracy (right) for the FEMNIST dataset.
baseline, established a Fully connected topology. Additionally, we examined EL (EL-Oracle and EL-Local) in comparison to 7-Regular static and 8- L-U-EquiStatic.
We observed that the results the data distribution, which leaves limited room for improvement across the different topologies. In terms of accuracy, the Fully connected topology achieved roughly 2 % better accuracy than the sparser topologies. EL-Oracle displayed a marginal advantage over the other approaches, However, the convergence behavior for EL-Local, 7-Regulas static, and EL-Oracle ping. both in terms of the number of rounds and communication usage. On the other hand, the B-U-EquiStatie approach lagged behind, exhibiting 1 % lower accuracy.
particularly exciting (Figure 7), primarily due to the nature of
nearly overlap-
Although significant improvements were not observed IID data settings, it is worth noting that EL did not hinder convergence. In more realistic non-IID data distributions, EL demonstrated improved accuracy and reduced the network utilization, as shown in Figure 4, Section 4.
C.4 Performance of EL and baselines on FEMNIST
As an additional dataset, we employed FEMNIST [7] evaluate EL against D-PSGD over other topologies. Figure 8 shows the convergence plots for the baselines against both EL-Oracle and EL-Local. We observe the same trend with Fully connected topology performing the best in terms of achieved top-1 accuracy. EL-Oracle outperforms EL-Local and both achieve higher top- accuracy compared the static topologies -Regula static and B-U-EquiStatic. The improvement in accuracy with EL (0.2 % between EL-Oracle and 7-Regular static) does not look as evident as with the CIFAR-10 dataset because the room for improvement (difference between 7Regul ar static and Fully connected) is quite small. This can be attributed to the homogeneity of the FEMNIST dataset and the complexity the digit recognition task.
D Notes on Network Connectivity and EL Performance
The implementation our decentralized scheme built around the condition that nodes can communicate with each other. This is similar to the assumptions of the EquiTopo topologies,
32

---

competitor baseline [53]. However, we argue that the connectivity requirement is a bit more lenient, allowing our EL approach function in wide range of practical scenarios. In data center settings, is common to train on clusters of highly interconnected GPUs, and all-to-all communication should be achievable these settings. edge settings, e-g., a network of mobile devices collaboratively training model while keeping private datasets, the communication barrier might appear more substantial. Nonetheless, Internet networks are generally well-connected. which mitigates this concern. More importantly, from a practical point of view, even if pairwise communications encounter some barriers, the decentralized and randomized nature of EL-Oracle and EL-Local should still allow for effective model learning and convergence. The occasional lack of communication between specific nodes should not significantly impact the algorithm's 's performance, as model updates are still propagated through other communicating nodes, as long as the network is not partitioned.
EL most useful in scenarios where every pair of nodes can communicate, but the total commu- nication budget is limited. Our randomized communication scheme allows for efficient use of the limited resources while ensuring faster model convergence than conventional decentralized learning approaches.
33


Reviews:
[{"review_id": "6PEbLcafbh", "reviewer": "Reviewer_iaf3", "summary": "This paper explores decentralized learning algorithms with the aim of faster model convergence while comparable accuracy compared with conventional DL methods. The new proposed algorithm - epidemic learning (EL) - leverages a dynamically changing, randomized communication topology to train a machine learning model in DL environment. The paper provides theoretical analysis which shows that the EL algorithm surpasses the best-known static and randomized topologies in terms of convergence speed, w.r.t. two key properties: linear speed-up and transient iterations. The experimental results show that the proposed EL-oracle and EL-local achieve quicker convergence than baselines. ", "questions": "1. Compared with semi-dynamic topologies, and time-varying and randomized topologies, what's the signaficance of EL? Have any of the previous works provided theoretical analysis on convergence rate? \n2. What does \"the convergence of GL on non-convex problems remains uncertain\" mean? \n3. Is GL a special case of EL-local with s=1? In the experiment, have you done sensitivity analysis on s values? ", "limitations": "Not applicable.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper is studying a very interesting and important problem - DL algorithms. The paper is well written, which is easy to follow. The proposed EL algorithm is technically sound. The theoretical analysis and experimental results show its effectiveness compared to baselines. \n", "weaknesses": "A major concern is that the proposed EL algorithm is not significantly different with semi-dynamic and time-varying and randomized topologies (they are introduced in related work section). Especially, gossip learning (GL) is like a special case of EL-local with s = 1. \n\nA minor comment: Figure 3 should be improved by giving label for x-axis. Also there is no full words for the first abbr \"CDF\". \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and provide a detailed rebuttal below.\n___\n\n> Q: A major concern is that the proposed EL algorithm is not significantly different with semi-dynamic and time-varying and randomized topologies (they are introduced in the related work section). Especially, gossip learning (GL).\n\nRe: We agree with the reviewer that the idea of running SGD over time-varying and randomized topologies existed in some previous works, including GL (as we outlined in the related work section).\nHowever, our work is the first, to our knowledge, that provides a theoretical foundation highlighting the advantages of randomized communication for decentralized learning.\nIn fact, our main contribution is to prove that an adaptation of SGD over these randomized networks can outperform the state-of-the-art decentralized learning schemes.\nHence, we believe the simplicity and effectiveness of our algorithm only enhance its practical relevance for the community.\n___\n> Q: What does \"the convergence of GL on non-convex problems remains uncertain\" mean?\n\nRe: With this sentence, we mean that the convergence of GL on non-convex loss functions has not been theoretically proven yet in the works that introduce and evaluate GL [15-16]. In fact, these works are mainly empirical and do not provide any convergence guarantee.\n___\n> Q: Is GL a special case of EL-local with s=1?\n\nRe: While at a high level, EL-Local with $s=1$ may look very similar to GL, there are some subtle differences, mainly in the way the aggregation proceeds.\nGL is inspired by the gossip protocols [47], and involves two parallel steps.\nAt each time step, a node sends a message (a model in GL) to one randomly chosen node ($s=1$).\nIndependently, on receiving a single message, a node aggregates the received model from this message with its own model and updates the aggregated model. \n\nIn contrast, EL-Local is designed to be aligned with existing decentralized learning algorithms (D-PSGD), with some basic modifications.\nEL-Local proceeds in rounds where first a node updates its local model on its local dataset and sends its model to $s$ randomly-chosen nodes. \nNext, the node waits to receive the models from other nodes in the current round.\nOn receiving one or more models in the ongoing round, the node aggregates them all together.\nEven if each node chooses exactly one random node to send the message to ($s=1$), it can receive messages from multiple nodes due to randomness.\nIn other words, with $s=1$, if a node receives multiple models in a round, nodes in GL will aggregate the received model with its local model for each received model separately, whereas in EL-Local, there will be a single model update per round, and all the received models from that round are aggregated together.\n\nFrom a theoretical point of view, this subtle difference plays an important role as it ensures the local models of the nodes stay close to each other during the training (Lemma 2), which is essential for the proof of convergence. \n\nIn summary, while GL shares some high-level similarities with our approach, GL is not a special case of EL-Local under $ s=1 $.\n___\n> Q: In the experiment, have you done sensitivity analysis on s values?\n\nRe: We have not done a sensitivity analysis on $ s $ for the original submission, but in response to the reviewer we have conducted this experiment in the rebuttal period.\nWe show in Figure 1 in the attached PDF in the Author Rebuttal the test accuracy for EL-Oracle and EL-Local, for $ s = 4 $, $ s = 7$, and $ s = 14 $, and when using a 7-regular static topology.\nWe observe that increasing $ s $ increases the convergence speed since more models are exchanged, and results in higher test accuracy when the experiment ends."}, {"review_id": "ToduCtrvn8", "reviewer": "Reviewer_VxtD", "summary": "This paper proposes a decentralized learning algorithm in which each node\nupdates its model from a set of s random nodes in a system with n > s\nnodes. The authors provide a theoretical analysis of the convergence speed\nand the number of transient iterations, i.e., the number of rounds required\nto reach linear speedup stage. Experiments are performed for the CIFAR-10\ndataset comparing the proposed two methods EL-Oracle and EL-Local with a\nnumber of baselines that are static topologies. The comparison metrics are\naccuracy, test loss, and communication volume with increasing number of\ncommunication rounds.", "questions": "There are several doubts raised in the Weaknesses section.", "limitations": "The authors do not bring up any limitations. No negative societal impact.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "A simple yet effective solution for decentralized learning. It is easily\nimplementable and can be easily adopted for any decentralized learning\ntask.\n\nThe theoretical analysis has some novel approach and is quite technical.\n\nThe paper is generally well written.", "weaknesses": "Title: Epidemic learning is a very confusing title. The reviewer is of the\nopinion that it is an overloaded term. For example, there are many\ninference problems in the context of contagions (like infectious diseases)\nwhere the objective is to estimate information about an outbreak. Also, the\nreviewer is of the opinion that this title might fail to gain the attention\nof readers from the decentralized learning community. Thirdly, it is very\nshort and non-informative.\n\nTheorem 1 mentions step size \\gamma, which does not feature in any\nexpressions that appear in the statement. The expressions for \\gamma in\nequations (4) and (5) should be included in the statement.\n\nRemark 1: The authors mention that they \"provide convergence rate directly\nfor the local models\". But wouldn't the expected convergence rate of the\nentire global averaged model depend on the maximum of (worst case) the\nconvergence rates among the local models? This is not addressed.\n\nExperiments section is weak: All the inferences are based on a single\nlearning problem on a single dataset. The gain in accuracy is not\nsignificant, but again the reviewer agrees that there are benefits such as\nreduction in communication rounds and volume. Yet, the gain in accuracy is\nlow enough to wonder what would happen if the same was used for, say a\nclassification task on ImageNet.\n\nThe performance for varying s: The authors only use s=7. They mention that\nthis is consistent with baselines. However, they could have performed a\nseparate experiment to study how their method performs under different\nmetrics for varying s. Suppose, they get very good performance for s=5\nitself, wouldn't it be an interesting statement?\n\nDisconnect between theory and experiments: \n\n1. The authors do not make an attempt to connect theoretical results to\nexperiments. For example, they mention that the number of transient\niterations is an inverse function of s. There are no experiments (like the\none suggested above) to test the tightness of the theoretical bounds. A\ntable analogous to Table 1 for experiments would be very helpful.\n\n2. Step size: From a theoretical perspective, the step size \\gamma in\nequations (4) and (5) depends on s. However, in the experiments (Appendix\nD), it is obtained by only running the fully-connected topology. Some\nanalysis of how convergence depends on s and \\gamma (as a function of\ns) would be useful.\n\n7-regular static: The authors consider only one instance of 7-regular\ntopology. There are many possibilities for a 96-node graph. The authors\ncould have considered 5-10 instances of 7-regular graphs and provided\nresults averaged over these topologies.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and provide a detailed rebuttal below.\n___\n\n> Q: Epidemic learning is not a good and informative title.\n\nRe: We can change the title to add some words about the novel element of our approach. For example, we consider changing the title to: \"Epidemic Learning: Boosting Decentralized Learning with Randomized Communication\".\n\n___\n> Q: Theorem 1 mentions step size $\\gamma$, which does not feature in any expressions that appear in the statement. The expressions for $\\gamma$ in equations (4) and (5) should be included in the statement.\n\nRe: Thank you for the suggestion. We will move Equations (4) and (5) to the main paper, in the camera-ready version.\n\n___\n> Q: Remark 1: The authors mention that they \"provide convergence rate directly for the local models\". But wouldn't the expected convergence rate of the entire global averaged model depend on the maximum of (worst case) the convergence rates among the local models? This is not addressed.\n\nRe: Note that exactly the same convergence rate as Theorem 1 holds for the global averaged model as well. In fact, proving the convergence guarantee directly on the local models requires one additional step in our analysis (see Footnote 2 on page 16 in the supplementary material). However, \nwe deliberately decided to provide the convergence guarantee directly on the local models as in practice the nodes may not have access to the global averaged model. We will clarify this in the camera-ready version of the paper.\n\n___\n> Q: All the inferences are based on a single learning problem on a single dataset. The gain in accuracy is not significant. What would happen if the same was used for, say a classification task on ImageNet.\n\nRe: We have selected the CIFAR-10 dataset for our evaluation as it is one of the most common and representative datasets in this field. Due to time and resource constraints, we are unable to run a compute-intensive dataset such as ImageNet, especially in a decentralized setting that demands significantly more resources compared to centralized learning approaches.\n\nThe accuracy gain of EL on the CIFAR-10 dataset compared to the baseline is around 2\\% which may or may not be considered significant.\nHowever, note that EL is designed to be an efficient decentralized learning algorithm, which is shown by the $1.5\\times$ reduction in communication cost. Our experimental results support the theoretical foundations that EL converges faster than the baselines.\n___\n> Q: The performance for varying s.\n\nRe: \nIn response to the reviewer, we have conducted this experiment.\nWe show in Figure 1 in the attached PDF of the Author Rebuttal the test accuracy for EL-Oracle and EL-Local, for $ s = 4 $, $ s = 7$ and $ s = 14 $, and when using a 7-regular static topology.\nWe observe that increasing $ s $ increases the convergence speed since more models are exchanged, and results in higher test accuracy when the experiment ends.\n___\n> Q: The number of transient iterations is an inverse function of s, but there are no experiments that test this.\n\nRe:  Less number of \"transient iterations\" indicates that the algorithm has a smaller second error term, which in turn causes the algorithm to perform better during the learning procedure. This is empirically confirmed in Figure 4. Please see our explanation regarding \"Transient Iterations\" in the global response at the top of the page for a more detailed discussion.\n___\n> Q: Step size: From a theoretical perspective, the step size $\\gamma$ in equations (4) and (5) depends on s. However, in the experiments (Appendix D), it is obtained by only running the fully-connected topology. Some analysis of how convergence depends on s and $\\gamma$ (as a function of s) would be useful.\n\nRe: Our theoretical result should be interpreted as an existence result (on the step-size).\nIn other words, our theory shows that there exists a step size for which the error is bounded by the expression given in the theorem, but it cannot be used to find the exact value of the step-size for the algorithm.\nNote, however, that this kind of existence result is common and constitutes a large part of the optimization literature [23].  In practice, the value of the step size should be found by hyperparameter tuning through a grid search. \nWe originally performed a grid search in a fully-connected topology and used the same learning rates for other experiments, while sanity checking the performance with respect to existing works as doing a grid search for each experiment at a scale of 96 nodes is computationally intensive and we did not want to compromise on the scale.\nTo address the concern of the reviewer, however, we  conducted a grid search for all the baselines in the rebuttal period, and we provide its results in the attached PDF. While we do see some minor differences in the performance for different step sizes, our main conclusion remains the same. \nRegarding the theoretical dependence of the convergence rate on $\\gamma$, note that in Theorem 1, the step-size $\\gamma$ is already fixed with the optimal value given in Equations (4), and (5). Also, the dependence of the rate on $s$ is explained in Section 3.2. In short, the second error term in Theorem 1 vanishes with $s$ with the rate $\\mathcal{O}(\\frac{1}{\\sqrt[3]{s}})$.\n___\n\n> Q: 7-regular static: The authors consider only one instance of 7-regular topology. There are many possibilities for a 96-node graph. The authors could have considered 5-10 instances of 7-regular graphs and provided results averaged over these topologies.\n\nRe: We run each experiment five times, and each run uses a different initialization seed.\nThis seed also influences the generation of the 7-regular static topology.\nTherefore, we generated 5 unique instances of a 7-regular graph and presented the averaged results.\nWe thank the reviewer for pointing this out and will clarify this in the experimental setup in the camera-ready version.\n\n"}, {"review_id": "JpSMPprPsm", "reviewer": "Reviewer_f2yu", "summary": "This paper considers Epidemic Learning, a framework for distributed optimization where each node in a network pushes gradient-descent updates to a uniform random subset of $s$ nodes in the network. Theoretical bounds on the rate of convergence are derived as well as the number of ``transient iterations,\" showing that this scheme improves upon existing fixed and randomized topologies. These results are supplemented by some empirical evaluations that show gains in communication and iterations to convergence compared to complete or fixed sparse topologies. ", "questions": "---As I am not really an expert on these kinds of methods, I'd defer to the other reviewers as to the novelty of this work's approach. I'd be happy to revise my score in light of any such discussions.\n\n---Is there a succinct summary of where the convergence benefits arise compared to, say, fast mixing but fixed network topologies? Intuitively, it seems to be because the convergence is dominated by the second-largest eigenspace, while random averaging avoids any particular bad eigenspace in expectation.\n\n---To elaborate on the above ``Weaknesses,\" one aspect that was not clear to me (and perhaps could be elaborated more) is the relevant tradeoffs in implementing such a decentralized scheme. More concretely, in what scenarios should this kind of randomized scheme that nonetheless must permit communication between any pair of nodes be employed? If the communication architecture is itself a limiting bottleneck, then this scheme cannot work due to the need for pairwise communications. Is the proposed use case meant primarily as a way to speed up/reduce optimization problems that already employ complete topologies?\n\n---While I am not a systems expert either, are there other tradeoffs one must consider with respect to routing/scheduling these randomized communications? For instance, it seems fairly intuitive how to easily route messages in, say, a ring topology --- when each node now must route to $s$ random nodes and received messages from $\\Omega(s)$ random nodes, is there any ``scheduling'' overhead in practice?\n\n---While I did not get the chance to carefully check the analysis in the Supplementary Material, the analysis seemed quite clean and logical, i.e. write out the various expected quantities in the natural way and derive relatively standard-looking GD-type recurrences. Conversely, this could mean that the analysis itself may not lead to new technical insights for others in the community.", "limitations": "N/A", "rating": 6, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The technical results generalize existing convergence rates of complete graphs (i.e. centralized SGD). The analysis is fairly clean and logical, and the paper is fairly well-written. This work also provides some experimental components to support their findings.", "weaknesses": "The practical benefits of this kind of decentralized optimization could be better contextualized (see below). The analysis, while clean, does not seem particularly conceptually surprising.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and provide a detailed rebuttal below. Given that the reviewer has such a good intuition about the problem and our solution, we are a bit surprised by the low confidence score of the review.\n___\n> Q: summary of where the convergence benefits arise ... \n\nRe: The intuition of the reviewer is indeed correct. The convergence behavior of decentralized learning schemes is indeed closely related to the second eigenvalue, or spectral gap, of the mixing matrix which governs the speed of mixing. In our approach, with random communication and under the same communication budget compared to a static topology, we can obtain very fast mixing properties. Please see our response to your last question for a detailed discussion of the theoretical significance of our work.\n___\n> Q: in what scenarios should this kind of randomized scheme that nonetheless must permit communication between any pair of nodes be employed?\n\n\nRe: Thank you for your insightful comment. \nYou correctly identified that the implementation of our decentralized scheme is built around the condition that all nodes can communicate with each other.\nThis is similar to the assumptions of the EquiTopo topologies [51], a competitor baseline.\nHowever, we argue that the connectivity requirement is a bit more lenient, allowing our model to function in a wide range of practical scenarios.\nIn data center settings it is common to train on clusters of highly interconnected GPUs, and all-to-all communication should be achievable in these settings.\nIn edge settings, e.g., a network of mobile devices collaboratively training a model while keeping private datasets, the communication barrier might appear more substantial.\nNonetheless, Internet networks are generally well-connected, which mitigates this concern. \nMore importantly, from a practical point of view, even if pairwise communications encounter some barriers, the decentralized and randomized nature of EL-Oracle and EL-Local should still allow for effective model learning and convergence.\nThe occasional lack of communication between specific nodes should not significantly impact the algorithm's performance, as model updates are still propagated through other communicating nodes, as long as the network is not partitioned.\nEL is most useful in scenarios where every pair of nodes can communicate, but the total communication budget is limited.\nOur randomized communication scheme allows for efficient use of the limited resources while ensuring faster model convergence than conventional decentralized learning approaches. \nWe will incorporate these explanations into the camera-ready version of the paper to clarify the assumptions and practical implications of our work.\n___\n> Q: ``scheduling'' overhead in practice?\n\nRe: The topology construction in EL-Oracle and the peer sampler in EL-Local might introduce some communication and computation overhead, but this overhead is absolutely minimal compared to the resources used for model exchange and training.\n___\n> Q: technical insights of the analysis for others in the community:\n\nRe: \nWe are happy that the reviewer finds our analysis clean and logical.\nTo demonstrate the superior convergence of our EL approach, our analysis proceeds in two main steps.\n\n1) The first step is established in Lemma 1, where we demonstrate that the randomized communication within EL achieves the property of fast mixing, with a mixing coefficient ($\\alpha_s$ or $\\beta_s$) of $\\mathcal{O}(\\frac{1}{s})$.\n\n2) The second step was tightening the conventional analysis of decentralized learning. Let $\\beta = 1 - p \\in [0,1)$ be the mixing coefficient (a.k.a. consensus rate [23]). Existing analyses of decentralized learning propose a convergence rate (as per Equation (3)) of:\n$$\\mathcal{O}\\left(\\sqrt{\\frac{L \\Delta_0 \\sigma^2}{n T}}+\\sqrt[3]{\\frac{L^2 \\Delta_0^2\\sigma^2}{(1-\\beta) T^2}}+\\sqrt[3]{\\frac{L^2 \\Delta_0^2\\mathcal{H}^2}{(1-\\beta)^2 T^2}}+\\frac{L \\Delta_0}{(1-\\beta) T}\\right).$$\n\n\nHere, $\\beta$'s impact on the convergence rate only appears in terms formatted as $\\mathcal{O}\\left(\\frac{1}{(1-\\beta)^k}\\right)$. Therefore, as long as $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$, diminishing $\\beta$ does not affect the order of the convergence rate. Hence, e.g., $\\beta = \\frac{1}{2}$ and $\\beta = \\frac{1}{100}$ would have identical convergence rates (with both yielding $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$ and the exact value of $\\frac{1}{1-\\beta}$ varying by a factor of less than 2). This suggests that we cannot achieve a convergence rate better than the existing state-of-the-art solutions with $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$. However, we observed that this limitation arises from a looseness in the conventional analysis. More specifically, the second and third terms in the above expression can be tightened such that they go to zero as $\\beta$ approaches zero (see Theorem 1, and the discussion below the theorem).  This adjustment allows us to showcase the benefits of EL, which maintains a $\\beta$ in $\\mathcal{O}(\\frac{1}{s})$.\n\nWe do agree with the reviewer that parts of our analysis are similar to the standard analysis for SGD (e.g., a recursion on the function value). However, we believe the same concern applies to most of the previous works as well. After all, these methods are essentially variations of SGD with additional elements that introduce new errors, and the distinctions usually lie in the bounds on these additional error terms, as we explained above.\n\n"}, {"review_id": "Xt27XChgXr", "reviewer": "Reviewer_fwhW", "summary": "This paper proposes a decentralized learning algorithm based on random communication, i.e., each node sends its model to a random set (with a fixed size) of other nodes at each round. This paper theoretically shows the superiority of random communication in terms of transient iterations over other decentralized algorithms, which is further validated by experiments.", "questions": "See the weaknesses.", "limitations": "Limitations have been properly discussed.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. This paper provides a simple yet effective scheme of communication for decentralized learning.\n\n2. This paper is technically sound. The technique developed for convergence analysis is interesting.", "weaknesses": "1. In the proposed algorithm, each node is required to send message to a fixed number $k$ of random neighbors at each round. In practice, this may only be applied to networks with high connectivity (e.g., fully connected), and other application scenarios need to be motivated. In addition, the theoretical superiority of convergence directly depends on $k$, so it might be unfair comparing with other algorithms which conventionally works on arbitrary connected graphs. Can the restriction on $k$ or uniformly random selection be relaxed a little bit, say, allow to communicate with varying number of neighbors?\n\n2. Although the authors conduct an experiment to explain the imbalanced load on different nodes, I still have a concern that the balanced pattern reported in this paper may rely on the uniformly random selection. Such an assumption may not be aligned with the real cases, e.g., the degrees of different nodes vary, then some nodes may have higher load than others under random selection. This problem may arise from the non-doubly stochasticity of the mixing matrices. Could other methods handling asymmetric communication, such as push-sum, be helpful for load balancing?\n\n3. Figure 4 shows that EL outperforms the baseline algorithm throughout the learning process, which seems inconsistent with the theoretical statement that the superiority of convergence lies in transient iterations, i.e., the early stage. As the learning proceeds, the convergence will be dominated by the first term. So I suppose the test accuracy of the various methods may get closer with large $T$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and provide a detailed rebuttal below.\n___\n\n> Q: Only applicable to networks with high connectivity. other application scenarios need to be motivated.\n\nRe: Thank you for your insightful comment. \nYou correctly identified that the implementation of our decentralized scheme is built around the condition that all nodes can communicate with each other.\nThis is similar to the assumptions of the EquiTopo topologies [51], a competitor baseline.\nHowever, we argue that the connectivity requirement is a bit more lenient, allowing our model to function in a wide range of practical scenarios.\nIn data center settings it is common to train on clusters of highly interconnected GPUs, and all-to-all communication should be achievable in these settings.\nIn edge settings, e.g., a network of mobile devices collaboratively training a model while keeping private datasets, the communication barrier might appear more substantial.\nNonetheless, Internet networks are generally well-connected, which mitigates this concern. \nMore importantly, from a practical point of view, even if pairwise communications encounter some barriers, the decentralized and randomized nature of EL-Oracle and EL-Local should still allow for effective model learning and convergence.\nThe occasional lack of communication between specific nodes should not significantly impact the algorithm's performance, as model updates are still propagated through other communicating nodes, as long as the network is not partitioned.\n\nEL is most useful in scenarios where every pair of nodes can communicate, but the total communication budget is limited.\nOur randomized communication scheme allows for efficient use of the limited resources while ensuring faster model convergence than conventional decentralized learning approaches. \n\nWe will incorporate these explanations into the camera-ready version of the paper to clarify the assumptions and practical implications of our work.\n___\n> Q: The theoretical superiority of convergence directly depends on $k$.\n\nRe: Indeed, the superiority of our convergence rate is directly linked to the number of random neighbors $k$ (or $s$ with the notation used in the paper), providing a clear trade-off between convergence speed and communication complexity. This flexibility is a distinguishing aspect of our approach.\n\nSpecifically, we obtain a state-of-the-art convergence rate for $k = 1$, with a number of transient iterations in $\\mathcal{O}(n^3)$, and the rates can be further improved by increasing $k$. While there are existing works that allow several communication levels [51, 55], unlike our method, their convergence rate does not enhance by augmenting the communication budget.\n\nTo obtain this improved convergence guarantee, we needed to enhance the convergence analysis, as the existing analysis suggested that it would not be possible to further improve the convergence rate over the state-of-the-art results and to obtain a number of transient iterations less than  $\\mathcal{O}(n^3)$ even for communication graphs with high connectivity. For a more detailed theoretical discussion on how we addressed this, please refer to our response to the last concern of reviewer f2yu.\n___\n> Q: Can the restriction on $k$ or uniformly random selection be relaxed, say, allow to communicate with varying number of neighbors?\n\nRe: This is an interesting idea and we can give each node a \"personalized\" fan-out value based on characteristics of that node, such as bandwidth capabilities or training speed.\nIn the current form of our algorithm, setting $k$ differently for different nodes would bias the model to fit better the data distribution of nodes with a higher fanout. To solve that issue, one needs to give more weight to the updates coming from less active nodes.\nSince this requires significant modifications to our analysis, we consider this extension beyond the scope of our work.\n\nIt is also worth noting that even though there are some convergence results for arbitrary graphs [23], these results often depend on the spectral gap of the underlying graph, which is a very challenging parameter to compute for an arbitrary graph. As a result most of the theoretical works often rely on graphs with balanced degrees such as ring, torus, grid, exponential and EquiTopo graphs.\n___\n> Q: Imbalanced communication load:\n\nRe: We note that this imbalance only arises in EL-Local as the number of received models per round in EL-Oracle is the same for all nodes.\nIt might indeed happen in EL-Local that some nodes have to process more incoming models during a round than others.\nYet, this concern can be addressed by having a node refuse an incoming model transfer when it has already received a particular number of models during a round, and having the sender node retry model exchange with another random node that is less occupied.\nWe will add these details in the camera-ready version of our work.\n\nIn larger networks, where nodes usually do not know about the participation of all other nodes, it is common to use a peer sampling service to randomly select other nodes [15]. A peer sampling service is a primitive that provides each node with an (almost) uniformly random subset of nodes, and this subset is periodically refreshed. Using an appropriate peer sampler will also help in balancing out the load between different nodes.\n___\n> Q: As the improvement is in the number of transient iterations, the test accuracy of the various methods may get closer with large $T$, which contradicts figure 4.\n\nRe: Less number of \"transient iterations\" does not merely imply that an algorithm is faster only during the initial stages of learning. Instead, it indicates that the algorithm has a smaller second error term, which in turn causes the algorithm to perform better during the learning procedure.  Please see our explanation regarding \"Transient Iterations\" in the global response at the top of the page.\n\n\n\n\n"}, {"review_id": "VPufHYNVXT", "reviewer": "Reviewer_Grsp", "summary": "The authors study the benefits of using randomized communication topologies for decentralized optimization of non-convex functions. Critically, the communication protocols studied are not based on picking/sampling a communication graph that remains fixed throughout learning. Instead the authors study the case where the nodes randomize their communication patterns with the rest of the nodes in each round. Based on this premise they propose two algorithms, EL Oracle and EL local and study their convergence rate. The prosed algorithms are shown to converge asymptotically faster than state of the art. Experiments verify the theoretical advantage empirically. ", "questions": "Another thing that was unclear to me is how is this improvement affected by the fact that we are averaging iterates $x$ instead of gradients. Does the advantage persist in this case? In the case where we are averaging gradients I have the intuition that it would be harder to show an advantage but I am not sure.", "limitations": "No limitations to address.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper communicates clearly and precisely its contribution. Despite extensive work on decentralized algorithms, including randomized and fixed topologies that can vary over time, to the best of my knowledge the proposed algorithms are novel. Importantly, the authors note that time varying randomized topologies have not been shown to have an advantage over their static counterparts.   ", "weaknesses": "I am not 100% sure which quantity is bounded in (3) and if it is supposed to be comparable to the rates provided in Theorem 1. The paragraphs after (3) list various ways EL Oracle and Local improve over (3) but I cannot say I follow them. For example, the first term in EL Oracle in Theorem 1 and (3) are identical but the comments mention an advantage in the first term. Clarifying this would help.\n\nIn its current state, the paper is not adequately explaining which part of the analysis unlocks the potential of non-static randomized communication graphs. I think highlighting which parts of the analysis are critical would help. Intuitively, I would expect that improving communication would have an effect similar to decreasing the variance $\\sigma$ or improving $p$ but it seems like this is not true.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and provide a detailed rebuttal below.\n___\n> Q: Which quantity is bounded in (3)? The first term in EL Oracle in Theorem 1 and (3) are identical but the comments mention an advantage in the first term. Clarifying this would help.\n\nRe: The quantity bounded in (3) is the average of the norm of the gradient which is exactly the same as Theorem 1 and (3) should be compared with bounds provided in Theorem 1. However, there seems to be a small misunderstanding regarding our comparison. We do not claim an advantage in the first term. In line 212, we mention that our algorithm preserves linear speed up which is the same as the bound in (3). In fact, it is not possible to outperform this term as it is the same term even for running a centralized SGD on a single node. Preserving linear speed-up may be surprising for EL-Local as in this case, the maxing matrix is not doubly stochastic.\nWe claim our bound to have a better second error term which is the main error term when comparing different decentralized learning schemes. Please see our explanation regarding \"Transient Iterations\" in the global response at the top of the page. \n___\n> Q: Which part of the analysis unlocks the potential of non-static randomized communication graphs?\n\nRe: To demonstrate the superior convergence of our EL approach, our analysis proceeds in two main steps.\n\n1) The first step is established in Lemma 1, where we demonstrate that the randomized communication within EL achieves the property of fast mixing, with a mixing coefficient ($\\alpha_s$ or $\\beta_s$) of $\\mathcal{O}(\\frac{1}{s})$.\n\n2) The second step was tightening the conventional analysis of decentralized learning. Let $\\beta = 1 - p \\in [0,1)$ be the mixing coefficient (a.k.a. consensus rate [23]). Existing analyses of decentralized learning propose a convergence rate (as per Equation (3)) of:\n$$\\mathcal{O}\\left(\\sqrt{\\frac{L \\Delta_0 \\sigma^2}{n T}}+\\sqrt[3]{\\frac{L^2 \\Delta_0^2\\sigma^2}{(1-\\beta) T^2}}+\\sqrt[3]{\\frac{L^2 \\Delta_0^2\\mathcal{H}^2}{(1-\\beta)^2 T^2}}+\\frac{L \\Delta_0}{(1-\\beta) T}\\right).$$\n\nHere, $\\beta$'s impact on the convergence rate only appears in terms formatted as $\\mathcal{O}\\left(\\frac{1}{(1-\\beta)^k}\\right)$. Therefore, as long as $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$, diminishing $\\beta$ does not affect the order of the convergence rate. Hence, e.g., $\\beta = \\frac{1}{2}$ and $\\beta = \\frac{1}{100}$ would have identical convergence rates (with both yielding $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$ and the exact value of $\\frac{1}{1-\\beta}$ varying by a factor of less than 2). This suggests that we cannot achieve a convergence rate better than the existing state-of-the-art solutions with $\\frac{1}{1-\\beta} \\in \\mathcal{O}(1)$. However, we observed that this limitation arises from a looseness in the conventional analysis. More specifically, the second and third terms in the above expression can be tightened such that they go to zero as $\\beta$ approaches zero (see Theorem 1, and the discussion below the theorem).  This adjustment allows us to showcase the benefits of EL, which maintains a $\\beta$ in $\\mathcal{O}(\\frac{1}{s})$.\n___\n\n> Q: What happens if we average gradients instead of models $x$?\n\nRe:  In the context of decentralized learning, unlike federated learning, averaging gradients may lead to divergence among local models of nodes. As a result, both our work and the existing related works we compared against employ the strategy of averaging the local models. \nWe agree that investigating the effects of averaging gradients in the context of decentralized learning could be an interesting avenue for future research. However, it is important to note that doing so necessitates the introduction of additional mechanisms to prevent model drift, given the potential divergence issue.\n\n \n\n"}]

Author rebuttal:
Firstly, we would like to thank all reviewers for the thorough and insightful comments on our submission. We appreciate the detailed feedback and the points raised, which have offered some valuable new insights.

Below we address two comments that were raised by multiple reviewers.

## Transient Iterations

As multiple reviewers raised concerns regarding the concept of "transient iterations" and its connection to our experimental results, we provide here a clarification:

To clarify, in the context of decentralized learning schemes, the convergence analysis often involves three error terms (as in Theorem 1). Generally, the first error term $\mathcal{O}\left(\frac{1}{\sqrt{nT}}\right)$ is attributed to the stochastic noise in gradient computation during the SGD step. The last error term $\mathcal{O}\left(\frac{1}{T}\right)$ is caused by the initial error in the function value. Notably, these two error terms are generally identical for different schemes since they are not directly related to decentralization. In fact, they even exist when running a centralized SGD on a single node.

In contrast, The second error term $\mathcal{O}\left(\frac{1}{T^{2/3}}\right)$ is the additional error introduced by decentralization and arises due to model drift: different nodes computing gradients on different local models at each step. This term is directly influenced by the efficiency of the mixing within the communication network. Hence, this term is the primary term to consider while comparing different decentralized learning schemes. The first term, despite having a stronger dependence on $T$, does not influence the comparison, as it is always fixed regardless of the communication network, be it say a sparse ring or a complete graph (see Equation (3) in the paper). Also, usually, the number of iterations required for the first term to become dominant is very large and it could even be more than the total number of learning iterations in a practical DL setting.

To capture this phenomenon and facilitate a more straightforward comparison of the second error term, the concept of "transient iterations" has been proposed in previous works. This concept does not merely imply that an algorithm is faster only during the initial stages of learning. Instead, it indicates that the algorithm has a smaller second error term, which in turn causes the algorithm to perform better during the learning procedure.

Considering this perspective, Figure 4 does not contradict the theoretical statement about the superiority of convergence in transient iterations. Instead, it suggests that EL should have a more favorable second error term, resulting in its out-performance throughout the learning process that matches our theoretical findings.

## Additional Experiments

As requested by multiple reviewers, we have added two additional experiments which results can be found in the attached PDF below. Our first additional experiment explores the effect of different values of $ s $, i.e., the number of neighbors we send a model to. Our second additional experiment involves tuning of the step-size $\gamma$. We hope this addresses the concerns of the reviewers.

Meta-review: The paper provides an improved convergence guarantee for distributed optimization that improves on previous work in terms of network scaling. The contribution of the work is clear and all reviewers believe the paper should be accepted.
Decision: Accept (poster)