Scalable Decentralized Learning with Teleportation
Authors: Yuki Takezawa
Sebastian U Stich
Venue: ICLR 2025 Poster (2025)
Keywords: decentralized learning
Primary area: optimization
TL;DR: We propose a novel decentralized learning method, called TELEPORTATION, whose convergence rate does not degrade as the number of nodes increases.

Abstract: Decentralized SGD can run with low communication costs, but its sparse communication characteristics deteriorate the convergence rate, especially when the number of nodes is large. In decentralized learning settings, communication is assumed to occur on only a given topology, while in many practical cases, the topology merely represents a preferred communication pattern, and connecting to arbitrary nodes is still possible. Previous studies have tried to alleviate the convergence rate degradation in these cases by designing topologies with large spectral gaps. However, the degradation is still significant when the number of nodes is substantial. In this work, we propose TELEPORTATION. TELEPORTATION activates only a subset of nodes, and the active nodes fetch the parameters from previous active nodes. Then, the active nodes update their parameters by SGD and perform gossip averaging on a relatively small topology comprising only the active nodes. We show that by activating only a proper number of nodes, TELEPORTATION can completely alleviate the convergence rate degradation. Furthermore, we propose an efficient hyperparameter-tuning method to search for the appropriate number of nodes to be activated. Experimentally, we showed that TELEPORTATION can train neural networks more stably and achieve higher accuracy than Decentralized SGD.

Published as a conference paper at ICLR 2025
SCALABLE DECENTRALIZED LEARNING WITH TELE- PORTATION
Yuki Takezawa" Kyoto University, OIST
Sebastian U. Stich
CISPA Helmholtz Center for Information Security
ABSTRACT
Decentralized SGD can run with low communication costs, but its sparse communi- cation characteristics deteriorate the convergence rate, especially when the number of nodes is large. In decentralized learning settings, communication is assumed to occur on only a given topology, while in many practical cases, the topology merely represents preferred communication pattern, and connecting to arbitrary nodes is still possible. Previous studies have tried to alleviate the convergence rate degra- dation in these cases by designing topologies with large spectral gaps. However, the degradation is still significant when the number of nodes is substantial. In this work, we propose TELEPORTATION. TELEPORTATION activates only subset of nodes, and the active nodes fetch the parameters from previous active nodes. Then, the active nodes update their parameters by SGD and perform gossip averaging on a relatively small topology comprising only the active nodes. We show that by activating only proper number of nodes, TELEPORTATION can completely alleviate the convergence rate degradation. Furthermore, propose efficient hyperparameter-tuninn method to search for the appropriate number nodes to be activated. Experimentally, we showed that TELEPORTATION train neural networks more stably and achieve higher accuracy than Decentralized SGD.
INTRODUCTION
Distributed learning has emerged as an important paradigm for privacy preservation and large-scale machine learning. In centralized approaches, such as federated learning (McMahan et al. 2017 Kairouz et al. 2019) and All-Reduce, nodes update their parameters by using their local dataset and then compute the average parameters of these nodes. Since computing the average of many nodes incurs huge communication costs, communication is the major bottleneck in the training time. In reducing communication costs, decentralized learning has attracted significant attention (Lian et al., 2017 2018 [Asran et al. [2199 Koloskova al.) 2020b). In decentralized learning, a node exchanges parameters with its few neighboring nodes and then computes their weighted average to approximate the average of all nodes. This procedure is called gossip averaging. Since each node only needs to communicate with few neighboring nodes, decentralized learning is more communication efficient than centralized counterparts (Lian et al. 2017 Assran et al.) 2019 Ying et al., (021).
While decentralized learning can run with low communication costs, the degradation of the conver- gence rate due to its sparse communication characteristics a trade-off (Koloskova et al. 2020b). Especially, when the number of nodes is large, the parameters held by each node are likely to be far away during the training, and gossip averaging deteriorates the convergence rate. This makes challenging for decentralized learning to scale to large number of nodes.
In decentralized learning literature, it is commonly assumed that communication can only occur on given topology. However, in many practical cases, the topology merely represents a preferred communication pattern, and connecting to arbitrary nodes is still possible, e.g., in a data center or the case where nodes are connected on the Internet. Since can choose which topology use in these cases, many prior studies designed topologies to reconcile the communication efficiency and convergence rate, attempting to alleviate the degradation of the convergence rate caused by large number of nodes (Wang et al. 2019 Ying et al. 2021 Ding et al. 2023 Takezawa et al. 2023b).
"This work done while visited the CISPA Helmholtz Center for Information Security.

---

Published as a conference paper at ICLR 2025
Specifically, the communication costs are determined by the maximum degree of the topology, and the convergence rate is determined by its spectral gap (Wang et al. 2019 Koloskova et al.) (200b)) Thus, the prior studies designed topologies with large spectral gaps and small maximum degrees and proposed performing gossip averaging on these topologies. However, the approximate average estimated by gossip averaging deviates from the exact average of all nodes the number of nodes increases, and the convergence rate remains to degrade when the number of nodes is substantial.
Can we develop a decentralized learning method whose convergence rate does nol degrade as the number of nodes increases? ? Our work yielded an affirmative answer with the proposal of TELEPORTATION. TELEPORTATION can completely eliminate the degradation of the convergence rate caused by increasing the number of nodes, and the convergence rate consistently improved as the number of nodes increases. Specifically, TELEPORTATION activates only subset of nodes and initializes their parameters with the parameters of previous active nodes. Then, the active node updates its parameters by SGI) and performs gossip averaging on a relatively small topology comprising only the active nodes. By activating only a proper number of nodes, gossip averaging can make the parameters of each node reach the consensus fast, and the parameters of each node can be prevented from being far away even when the total number of nodes is large. We show that by activating an appropriate number of nodes, the degradation of the convergence rate can be completely alleviated. Furthermore, we propose an efficient hyperparameter--uniig method to search for the proper number of active nodes. For an arbitrary number of nodes, the proposed ppperparameter-tuning method can find the appropriate number of nodes to be activated within 21' iterations in total, where T is the number of iterations to run TELEPORTATION once. Experimentally, we demonstrated that TELEPORTATION can converge faster than Decentralized SGD and train neural networks more stably.
In this study, ask the following question:
Note: In this work, we consider a setting where any two nodes can exchange parameters as required, similar previous studies on topology design for decentralized learning (Marfoq et al., 2020 Ying et al. 2021 Song et al., 2022, Takezawa et al. [023b] Ding et al. (023)) A data center is an example, and Assran et al. (2019) demonstrated that decentralize lize methods can train neural networks faster than All-Reduce. In addition to a data center, when nodes are connected to the Internet, any two nodes can communicate by specifying the IP address. TELEPORTATION is not applicable in the presence of pair of nodes that cannot communicate, in wireless sensor networks.
Notation: A graph G is represented by (V, E) where V is a set of nodes and E is a set of edges. For simplicity, we also write ((1,-. n,), E) to represent graph G where n the number of nodes. Ia denotes the d- d-dimentional identify matrix, 0 denotes a vector with all zeros, and 1 denotes a vector with all ones.
2 PRELIMINARY
Problem Setting:
We consider the following problem where the loss functions are distributed
among n nodes:
a 1 72 Σ fz())
min f(x)
f((x) = EENDD [F(()))))
(1)
mcRd
where æ is a model parameter, D; is a training dataset that the i-th node has, &, is a date sample following D,, and the local loss function f. Rd -> IR is defined the expectation of F. F.(:E) over
data sample ç.- Following previous works (Koloskova et al.] [020a]] Yuan et al. 2021 Lin et al. 2021 we assume that the loss functions satisfy the following assumptions.
Assumption 1. There exists f > -oo that satisfies f(x) f* for any x E Rd.
Assumption 2. There exists L 2 0 that satisfies for any x, y E Rd and i (1,2,...,m .n).
I f(()) V(((g)) < L L yll-
(2)
Assumption 3. There exists a 2 0 that satisfies for any x E Rd and i E ...,,...,... (1,2,..-,n))
E ((;
2 52
2

---

Published as a conference paper at ICLR 2025
Assumption 4. There exists that satisfies for any E R..
V\(=) sc².
(4)
Decentralized SGD: One of the most fundamental decentralized learning methods to solve Eq. !
Decentralized SGD (Lian et al. 2017). Let æ; E Rd denote the i-th node parameter. Once the
topology comprising n nodes Gn =I11- nn, E) is specified, Decentralized SGD updates æ; as follows:
Σ We (z - -VF((())))))))) 1=1
where > 0 is the step size and Wi E [0.1] is the weight of edge (i.j) E that satisfies
Σ.=1 Wij Σ i=1 Wij The following assumption is commonly used to represent how well
the topology Gn is connected (Yuan et al. 2021 Koloskova et al. 2020b 2021 Aketi al. 2023
Assumption 5. Ler ) is the i-th largest eigenvalue of W E [0. 1 1|=xn. W is a doubly stochastic
matrix, and Pn. = max (221, 1Am1]² satisfies pn. (0, 1]. That is, it holds that
XW XI S (1 Pn) || x X
for any X R where X _X11.
write Pn to emphasize that pn depends on n. small ps. indicates that the topology is poorly connected, and large Pn indicates that the topology is well connected. Generally, Pn. approaches zero as the number node n increases. For instance, when a ring is used as the underlying topology, Pn is ((n=2)), which rapidly decreases as increases (Nedié et al. 2018). Under these assumptions, Decentralized SGD converges with the following rate.
Proposition (Koloskova al. (2020b)). Suppose that Assumptions 7 7 and 5 hold. Let {(=; a li= Yi= denote the parameters generated by Decentralized SGD. Then, there exists the step size n that satisfies:
T Σ 1=0
50
(V +
( OI pml)
Lra Tpm
+
(5)
T2p2
where = f( - fo and x(1) = - x
is improved, while the second and third terms degrade since pn reaches zero. Thus, as the number of nodes n increases substantially, the second and third terms dominate the convergence rate, and the convergence practical cases, 9n merely represents a preferred communication pattern, and any two nodes can communicate needed, introduced in Sec. [ Since
As the number of nodes increases, the first term O( Lrag" xe
deteriorates. In many
choose which topology cases, many recent studies have attempted to alleviate the convergence rate degradation by proposing topologies with large Pv, (Ying et al. 2021 Ding et al. 2023 Takezawa al. 2023b). However, their Pa. still approach zero as n increases, and the convergence rate degrades when is substantially large. Table in Sec. [ lists the convergence rates of Decentralized SGD with various topologies.
in these
PROPOSED METHOD
In this section, propose TELEPORTATION which completely eliminate the degradation of the convergence rate caused by increasing the number of nodes. In the remainder this section, we
describe TELEPORTATION in Sec. 3.T and analyze its convergence rate in Sec. 3.2 Then, we propose an efficient hyperparameter search method in Sec. 3.3 and analyze its convergence rate in Sec. 3.4
3.1 TELEPORTATION
Pn. represents the speed at which the gossip averaging makes the parameter of each node {æ; ( reach the average n Wc. As the number of nodes increases, averaging all node parameters
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 Simple version of TELEPORTATION
1: Input: the number of nodes set of nodes Vn, number of active nodes k, total number of iteration T, step size y,, and topology comprising active nodes Gs (fl, ,k), E).
2: for E {0,1,-.. . do
3: sample next active nodes v(()) from V, without replacement, and assign 21, ; to
"ncive
variables Stoken_id""
V a randomly without overlap.
4: for i E (1, 2.... n in parallel do
5: if ny E V-(t) then
ugtive
6:
if > 0 then
Let Uj (t-1) denote the node such that token_id
(a token_id
7:
receive x (9 from Uy vilime) and xx!) + =x)/
8:
9:
end if
V )
10: yi
- x
receive
y
from Uy {uz E
active (token id!" token_idf)) E E}.
x; (1+1)
(t) Evit) W 14 id
13:
end if
14:
end for
15:
end for
"The update rule the parameters of the inactive nodes not described because the parameters held by the inactive nodes are discarded and initialized with the parameters of the other active nodes when they are activated in line 8. The parameters of inactive nodes do not affect the behavior of active node parameters.
becomes difficult with gossip averaging, and pr, reaches zero. Thus, as increases, the parameters of each node {x; } comes to be apart during the training, and the convergence rate deteriorates, as discussed in Sec. 2
To prevent the parameters in each node {æ; / from being away when the number of nodes n is large,
we propose updating the parameters of only small subset of nodes and performing gossip averaging on small topology. We refer to the proposed method as TELEPORTATION Let k E (1.... n
denote the number of active nodes and Gj = (fI..... k}. E)) be the topology comprising k active nodes. Essentially, TELEPORTATION consists of the following three steps:
(1) We sample k active nodes V from V, without replacement and assign {1,2, ... k} to variables (token_id
v(0 ) without overlap
(2) The active node v E ((t) fetches the parameters from the previous active node vy E active active
v-(t-1)
whose token_ ia (t-1) stores the same value as that of token_id Then, the active node U; initializes its parameters with the fetched parameter and updates them by SGD.
(3) The active node v, E v(t) active exchanges its parameters with its neighbors {ng E Booke_iid"' tooen_ikidjp ia))) E} and computes the weighted average with them.
V active
We show the pseudo-code and illustration in Alg. and Fig. [ In the above implementation, the first step does not start until the third step is completed. We can solve this issue so that gossip averaging in the third step is performed on the next active node vy. and the first and third steps can be executed simultaneously. We show the optimized version in Sec. A
In TELEPORTATION, gossip averaging is performed on relatively small topology Gk. which can make the parameters of k active nodes reach the average fast. Therefore, using the proper number of the convergence rate by increasing the number of
active nodes k. we can mitigate the degradation nodes n. In the next section, we analyze the convergence rate and show that our proposed method successfully circumvents the negative effect of increasing the number of nodes n.
We named our proposed method TEL TELEPPOTATION reflect the manner in which the active nodes copy their parameters to the next active nodes.
2The first step can be performed in decentralized manner by sharing the same seed value to sample active nodes before starting the training.
4

---

Published as a conference paper at ICLR 2025
Figure 1: Illustration of Alg. I with 8 and h: 3. We line as the topology consisting of active nodes Gn - (11, 2,3). [1,, 1), (1, 2), (2, (2, (3, 3) The black nodes represent active nodes, and the number written the node is token tdden_id!"" id The blue nodes represent the next active nodes, and the number on the node is token_ id. ((( The first and third graphs from the left represent the communication in line 12, and the other graphs represent the communication in line 8.
Comparison with Client Sampling: TELEPORTATION randomly samples a subset of nodes and activates them, but TELEPORTATION is different from the client sampling (Liu et al. 2022). TELE- PORTATION can prevent the parameters of nodes from being away by using the small A because gossip averaging is performed on the small topology Gg. In contrast to TELEPORTATION client sampling incites the parameters of nodes to drift away because gossip averaging is performed on the topology comprising all nodes, and nodes can exchange parameters only when neighboring nodes sampled simultaneously, which makes it more difficult for gossip averaging to make the parameters reach the consensus. Thus, client sampling cannot alleviate the degradation of the convergence rate caused by a large number of nodes and degrades the convergence rate as well as the vanilla Decentralized SGD (see Sec. for more detailed discussion).
3.2 CONVERGENCE ANALYSIS OF TELEPORTATION
We assume that the topology comprising k active nodes G& satisfies the following assumption.
Assumption 6. Let A; is the i-th largest eigenvalue of W E [0, 1] W is doubly stochastic
matrix, and pk = 1 max (22), l |^m]}² satisfies Ps E (0, 1]. That is, it holds that
X x I I - (1- X X ||
(6)
for any X E Raxk where X = T
Note that W is a h x l matrix, and рæ depends on the number of active nodes k. but is independent of the total number of nodes n. Under Assumptions [ convergence rate of TELEPORTATION for any number of active nodes ki.
and [6] Theorem [
provides the
Theorem 1. Suppose that Assumptions 2
3 and hold. Let {(x) (1) 1n Hi denote the initialized with the same parameter (0)) Then, for any number of active nodes ie E {1,2,.. 2.. n]. there exists the step size n such that
parameters generated by Alg. and suppose that {x) (0) 1a
El B|| f "eeive))l"" 1|2 is bounded from above by
Lrolo² + +(1 #=))<²) + (LT80L0* + +(2)(1- pk)
Lro Tps
+
KT
T2pk
where x (t) == Σ
2 and ro = f(x(0)) ft.
Ee,evie evit)
By tuning the number of active nodes k we obtain the following theorem. To determine the proper number active nodes k; the explicit form of pk is necessary. Here, we show the rates when we use ring and exponential graph (Ying et al. 2021 GR-
Theorem 2. Suppose that Assumptions generated by Alg. and suppose that {x m
and
p hold. Let (xx ye be the parameters
is initialized with the same parameter ((0).
Ring: Suppose that the active nodes are connected by ring, i.e.. pa 2ik 2). Then, if we set the number of active nodes & as follows:
(To6
+ Lro
$
k: max
1. min
5

---

Published as a conference paper at ICLR 2025
there exists yi such that
7+I Et B
(t) active) 1|2 is bounded from above by
0 0 Lroo?
Lrolo² + (2)$)
(Lrulop + +2)) (
Lro
nf
T
where a(t) = E
o. and ro = f(x(0)) ft.
active
Exp. Graph:
Suppose that the active nodes connected by exponential graph, i.e., Pk 2 Then, if we set the number of active nodes k. as follows:
)
( + {1
T(o² +
(2)
k= max
1, min
, n
Lru
Lro
there exists such that
21= B/I S
active |1 is bounded from above by
(1)
T4I
(VLroe nT +
L2 + 5
$1 :) (?(o)+(22)))
T(o² +52) +3) Lro
Lro log2
T(o² + {3)
Lro
o
log2
+
Lro
T
All proofs are presented in Sec. B The first term in Eq. 7 is worse than the first term in Eq. ( but Theorem indicates that the first term becomes the same as that of Decentralized SGD by carefully tuning For both cases, only the first term depends on the number of nodes n, which is improved n increases. Therefore, TELEPORTATION can completely climinate the negative effect by increasing the number of nodes nt, and its convergence rate consistently improved as n increases. As discussed in Sec. 2 several previous studies have attempted avoid convergence rate degradation caused by large n by designing topologies with large spectral gaps (Ying et al. 2021 Song et al.) 2022 Takezawal et al. 2023b). However, prior topology, except for complete graph, completely remove this degradation. By comparing with the complete graph, TELEPORTATION is more communication efficient. For instance, if a ring used Gg. each node only needs communicate with three nodes per iteration. Therefore, TELEPORTATION is the first method that does not suffer from large n without sacrificing the communication efficiency.
3.3 EFFICIENT HYPERPARAMETER SEARCH FOR NUMBER OF ACTIVE NODES
TELEPORTATION can eliminate the convergence rate degradation caused by large number of nodes n, while the number of active nodes & E (1,...,, ,n} needs to tuned carefully. becomes
tuned by grid search, it requires nI' iterations in total. This hyperparameter-ttmii expensive as n increases. To alleviate this issuc, we further extend TELEPORTATION by proposing an method for the number of active nodes k. The key idea for efficient hyperparameter-tunigg is based on the following lemma.
efficient hyperparameter--tunin
Lemma 1. Let k* 21,2,3, 3, ... .n) be the optimal number of active nodes. k* n, there exists 2,, 4, 8,... (00ggg that satisfies k. k < k*. Furthermore, holds that > (x+1)))+)))1 2 n.
Algorithm Efficient hyperparameter search TELEPORTATION.
Input: the total number of iteration 2T, and the number of nodes n.
(1) 2: run Alg. for 7' iterations with number of active nodes n, and let (1 (1 denote the generated parameters.
3: for k 2, 22 2e.. 1)]-1} in parallel do
4: run Alg. 1 iterations with number of active nodes k.
5: end for
6: let (1=1))) (ev I denote the parameters generated by Alg. with k active nodes.
7: return the best parameters among k E {1, 2, log., (n+ 1I n).
*Theoretically, select the parameters with the smallest gradient in Theorem In practice, we select that achieves best accuracy on the validation datasets as vanilla grid search.

---

Published as a conference paper at ICLR 2025
Lemma 1 shows that for any optimal number of active nodes k- n
similar number of (1bb)((++))__) This suggests that we only need to search ,2 (1 n) to obtain the appropriate &o and we do not need run Alg. indicates that Alg. can be run with various E {1, 2, 22. 22:... ..... 21log_(n+1]] (1=)()111)111))))) in parallel because the total number of active nodes is less than or equal to Based on these observations, we propose an efficient hyperparameter-tuningg method. The pseudo-code shown in Alg. 2
active nodes is contained in {1, 2, , ,...
from {1, 2, 2
for all E {1, ... , Moreover, Lemma I
3.4 CONVERGENCE ANALYSIS OF TELEPORTATION WITH EFFICIENT HYPERPARAMETER SEARCH
Under the same assumptions as in Theorem The proof is deferred Sec.
Theorem provides the convergence rate of Alg.
Theorem 3. Suppose that Assumptions 1
k u, b,evi YE-o denote the parameters of active nodes generated by Alg. when the number of active nodes is set k, and we
12
3 and hold. Let (ta
define K. = (1, 2², 22. .... 210ogg n Then, suppose that the parameters are initialized
with the same parameter (0))
Ring: If the active nodes are connected by ring, i.e., Pk 2Kk 3), there exists nj such that E ((1) is bounded from above by
minkek
[+I 21=
Amolo=+(922) +
0
11002 nT
LTolO² Lrolo
+ [ + (2)8
Lro T
where = f(z(0))= f* and (11) active, = Ee,e
x K,s""
Exp. Graph: If the active nodes connected by exponential graph, i.e., Pk 22log k), there is bounded from above by
exists 17 such that mingex
T+T
B
(V [ nT +
Lo" +
T(o² + +(o²+
+
Lto log2
T(o*+ Tro
Lro +
O
log2
T2
Lro
T
Theorem 3 shows that Alg. 2 can achieve exactly the same convergence rate as the one shown in
Theorem 2 (i.e., the convergence rate with optimal k). Algorithm Algorithm@rrqqurress only 2T iterations to find the proper number of active nodes, whereas grid search requires n? iterations in total. Thus, Alg. 2 find the appropriate number of active nodes more efficiently than the vanilla grid search.
RELATED WORK
Decentralized SGD and its Variants: The literature decentralized learning can be traced back to Tsitsiklis (1944), and Decentralized SGD (Lian et al. 2017) currently the most widely used for reasons of its simplicity. Recently, many researchers have improved Decentralized SGD in various aspects. Pu & Nedić (2021). Yuan et al. (2019), Tang et al. (2018b). Yuan et al. (2021), Vogels et al. (2021), Takezawa al. (2023a). Aketi al. (2023), and Di al. (2024) proposed decentralized learn- ing methods that are robust to data heterogeneity. Tang et al. (2018a), Koloskova et al. (2019), Vogels al. (2020), Kovalev et (202I). ) and Zhao et (2022) proposed communication compression methods. Liu et al. 2022) analyzed Decentralized SGD with client sampling.
Token Algorithm: Token algorithms (Johansson et al. 2007 Dorfmann & Levy 2022 Even 2023
Hendrikx 2023) are a variant of decentralized learning methods different from consensus-basee decentralized learning methods, such as Decentralized SGD. In contrast to the consensus- based decentralized learning methods, parameter called token randomly walks the topology and is updated on each node. Since token algorithms have only one parameter, they do not suffer from the issue of parameters held by each node drifting away. However, their convergence rates cannot
7

---

Published as a conference paper at ICLR 2025
achieve linear speedup as that in Decentralized SGD EEvn 2023 In TELEPORTATION, k parameters randomly move from previous active nodes to the next active nodes and are updated on the active nodes. Then, by carefully selecting TELEPORTATION can alleviate the issue of parameter drifting without sacrificing linear speedup property.
Client Sampling: Client sampling is widely studied in federated learning to reduce the commu-
nication costs between the central server and nodes (McMahan et al. 2017 Fraboni et al. [202T]
Wu et al. 2023). McMahan et al. (2017) proposed sampling a subset of nodes randomly. Cho et al. (2020) proposed selecting nodes according the loss values. [Chnn et al. (2022) and Wang al.
(2023 proposed sampling nodes according to their gradient norms. In decentralized learning, Liu ctt al. (2022) studied client sampling and analyzed the convergence rate. However, as discussed in Sec. [31] the client sampling cannot alleviate the degradation of the convergence rate caused by
large number nodes.
EXPERIMENT
5.1 SYNTHETIC EXPERIMENT
Setting: We followed the experimental setting in Koloskova et (2020b) and the number of nodes n to 100 and loss function as fi = 7 A, - b;)]l² with A; == Vn Ia and d = 50. b,
was drawn from N(O _ Id) for each node. We defined the stochastic gradient as (F, E) =
((((z) + where was drawn from (o,, x² Ia) each iteration. We used ring and Base-2 Graph (Takezawa et al.] 2023b) as the topology. The ring is one the most commonly used topologies for decentralized learning. The Base-2 Graph is the sfute-of-the-att topology for Decentralized SGD, and Takezawa et al. (2023b) demonstrated that the Base-2 Graph can be superior to the various topologies, e.g., exponential graph, 1-peer exponential graph (Ying et al.) (021), and Equi Topo (Song et af.] (022). Note that the Base-2 Graph assumes that any two nodes can communicate as TELEPORTATION. For each setting, we tuned the step size reach the target accuracy as few iterations as possible. See Sec. G for a more detailed setting.
Teleportation (Ring) Teleportation (Base-2 Graph)
Decentralized SGD (Ring)
Decentralized SGD (Base-2 Graph)
10,
100,
107
Error
301
13a
10"2
10-1
10-2
0,
10
10, 0 10
100, 0
10
Error
108
108
108
10
10
10a
101
10a
10a
0, 0
100
10, 0²
100
100, 0² 100
107
107
107
Emor
108
108
128
10
10
107
107 107
3D"
201
107
202
127
10
301
107
107 1.7
104
201
Iterations
Iterations
Iterations
Figure 2: Convergence of the error to the target accuracy 0.001 for different stochastic noise a² and x as the enror for
heterogeneity S². We plotted Evette) ||x
112 and EE TELEPORTATION and Decentralized SGD, respectively. TELEPORTATION consistently reached the target accuracy faster than Decentralized SGD.
(t)
||=
8

---

Published as a conference paper at ICLR 2025
We depict the results in Fig. 2 For all cases, TELEPORTATION required fewer iterations reach the target accuracy than Decentralized SGD. By comparing De- centralized SGD with ring, TELEPORTA- TION converged up to three orders of mag- nitude faster than Decentralized SGD. Even in the case when the saate-of-the-and topol- ogy, Base-2 Graph, is used, TELEPORTA- TION converged up to 10 times faster than Decentralized SGD, Table lists the number active nodes & selected by Alg. Although the total number of nodes is 100, small number of nodes &t was selected. Therefore, activating only few nodes can prevent the parameters from being far away and lead to a faster convergence rate than that of Decentralized SGD.
Results:
Table The number of active nodes selected by Alg. 2 in Fig. 2 The left value is the number of active nodes when the topology a ring, and the right value is the number when the topology is the Base-2 Graph.
5² = 0
5²
10
ç² = 100
1/1
1/1
4/ 4
x² 10
1/1
1/1
8/8
o² = 100
8/8
8/8
4/16
5.2 NEURAL NETWORKS
Setting: We used Fashion MNIST Xiao et al. 2017) and CIFAR-10 (Krizhevsky 2009) as datasets and used LeNet (LeCun al. 1998) and VGG (Simonyan & Zisserman 2013) as neural networks, respectively. To use the momentum in TELEPORTATION, the momentum copied from the previous active nodes the next active nodes, as well as the parameters. We the number of nodes n to 25 and distributed the data to nodes using Dirichlet distribution with parameter a (Hsu et al. (2019). As approaches zero, each node comes have a different dataset. We repeated all experiments with three different seed values, reporting the averages. See Sec. G for more detailed setting.
We depict the results in Fig. When 0.1, TELEPORTATION outperformed Decentral- ized SGD and trained the neural networks more stably. When a = 10.0, all comparison methods achieved competitive accuracy. By comparing the results with = 0.1 and 10.0, the accuracy curves of Decentralized SGD became unstable in the heterogeneous setting, whereas the accuracy of TELEPORTATION from client drift, while TELEPORTATION can suppress it by initializing the parameters of active nodes by using the parameters of other nodes.
Results:
stable in both cases. This is because Decentralized SGD suffers
Fashion MNIST
CIFAR-10
Teleportation (Ring)
Teleportation (Base-2 Graph)
Decentralized SGD (Ring)
Accuracy
85
Accurapy
85
Decentralized SGD (Base-2 Graph]
80
75
75
100
200
Epoch
Epoch
(a)
10.0 (homogeneous case)
Fashion MNIST
CIFAR-10
90
90
Teleportation (Ring)
Teleportation (Base-2 Graph)
Decentralized SGD (Ring)
Accuracy
Accuraty
Decentralized (Base Graph)
70
70
50
100 Epoch
150
200
200
400
500
(b) 0.1 (heterogeneous case)
Figure Test accuracy TELEPORTATION and Decentralized SGD for different heterogeneity. All methods achieved competitive accuracy in the homogeneous case, while TELEPORTATION outperformed Decentralized SGD in the heterogeneous case.

---

Published as a conference paper at ICLR 2025
10.0
0.1
90
90
Teleportation (Ring)
Teleportation (Base-2 Graph)
Decentralized SGD (Ring)
Accuracy
Accuracy
Decentralized SGD (Base-2 Graph)
60
60
500
1000
1500
500
1000
1500
Second
Second
Figure 4: Test accuracy of TELEPORTATION and Decentralized SGD under the heterogeneous networks with т = Decentralized SGD with the ring reached a high accuracy faster than the other methods in the homogeneous case, while TELEPORTATION reached high accuracy faster in the heterogeneous case. Note that the number of epochs was set the same for all methods.
5.3 COMPARISON UNDER HETEROGENTONI NETWORKS
Next, we examine the effectiveness of TELEPORTATION in terms wallclock time. TELEPORTA- TION, active nodes send the parameters the next active nodes, which randomly sampled from the entire set of nodes. Thus, the communication may happen between distant nodes, e.g., nodes located in distant regions. In this section, we evaluate TELEPORTATION under the heterogeneous networks where communication costs differ between pairs of nodes.
Setting: We used Fashion MNIST and LeNet as with Sec. 5.2 To simulate a heterogeneous net- work, added 7 mod( jl 24) jas delay when nodes and j communicate, where mod(a, b) is the remainder of dividing a by b. We constructed a ring by connecting node i to node (1 + mod(i, (i, 25)). This ring is the optimal topology in terms of the communication delay, and the communication in Decentralized SGD with the ring was delayed by T uas, whereas the communication in TELEPORTA- TION was delayed by most 24T μs. The communication in Decentralized SGD with the Base-2 Graph was also delayed by at most 24T jis since the Base-2 Graph assumes that any two nodes can communicate, and communication occurs between various nodes.
Results: We depict the results with 5 5 in Fig. In the Appendix, we also show the results with 0 in Fig-7] Decentralized SGD with the ring finished the training faster than Decentralized SGD with the Base-2 Graph and TELEPORTATION. However, when a 0.1, the accuracy of Decentralized SGD with the ring increased very slowly, and TELEPORTATION reached a high accuracy faster than Decentralized SGD. When a 10.0, Decentralized SGD with the ring reached a high accuracy faster than the other methods. Therefore, Decentralized SGD with sparse topology is the preferred method when the data distributions are homogeneous, while when the data distributions are heterogeneous, TELEPORTATION can be preferred method even if the network is heterogeneous since the methods that can prevent the parameter drifting are necessary to achieve high accuracy.
6 CONCLUSION AND LIMITATION
In this paper, we propose TELEPORTATION, which activates a subset of nodes and performs gossip averaging on relatively small topology comprising only active nodes. We showed that TELEPORTA- TION converges to the stationary point without suffering from a large number of nodes by activating a proper number of nodes. Furthermore, we proposed an efficient hyperparameter tuning method to search for this appropriate number of nodes. We experimentally investigated the effectiveness of TELEPORTATION, demonstrating that TELEPORTATION can converge faster than Decentralized SGD and train neural networks more stably when the data distributions are heterogeneous.
Limitation: TELEPORTATION is not applicable in the case that there exists pair of nodes that cannot communicate. Extending TELEPORTATION to such a setting is one of the most promising future directions. Furthermore, since active nodes are randomly sampled from the entire set of nodes, communication may happen between distant nodes in the heterogeneous networks. demonstrated that when the data distributions heterogeneous, TELEPORTATION can be preferred method even if the network heterogeneous, while would promising future direction to case this condition to prevent nodes from communicating with distant nodes.
Sec. 5.3 we
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported by JSPS KAKENHI Grant Number 23KJ1336. We thank Anastasia Koloskova for her helpful comments the practical implementation of TELEPORTATION described in Sec.
REFERENCES
Sai Aparna Aketi, Abolfazl Hashemi, and Kaushik Roy. Global update tracking: A decentralized learning algorithm for heterogeneous data. In Advances in Neural Information Processing Systems, 2023.
Mahmoud Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. In International Conference on Machine Learning. 2019.
Wenlin Chen, Samuel Horváth, and Peter Richtárik. Optimal client sampling for federated learning. In Transactions on Machine Learning Research, 2022.
Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. In arXiv, 2020.
Hao Di, Haishan Ye, Xiangyu Chang, Guang Dai, and Ivor Tsang. Double stochasticity gazes faster: Snap-shot decentralized stochastic gradient tracking methods. International Conference on Machine Learning, 2024.
Lisang Ding, Kexin Jin, Bicheng Ying, Kun Yuan, and Wotao Yin. DSGD-CECA: Decentralized SGD with communication-opiinee exact consensus algorithm. In International Conference on Machine Learning, 2023.
Ron Dorfman and Kfir Yehuda Levy. Adapting mixing time in stochastic optimization with Markovian data. In International Conference on Machine Learning, 2022.
Mathieu Even. Stochastic gradient descent under Markovian sampling schemes. In International Conference on Machine Learning, 2023.
Yann Fraboni, Richard Vidal, Laetitia Kameni, and Marco Lorenzi. Clustered sampling: Low- variance and improved representativity for clients selection in federated learning. In International Conference on Machine Learning, 2021.
Hadrien Hendrikx. A principled framework for the design and analysis of token algorithms. In International Conference on Artificial Intelligence and Statistics, 2023.
Tzu-Ming Harry Hsu, Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv, 2019.
Bjorn Johansson, Maben Rabi, and Mikael Johansson. simple peer-to-peer algorithm for distributed optimization in sensor networks. In IEEE Conference on Decision and Control, 2007.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin
Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. D'Oliveira, Salim EI Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Praneeth Vepakomma, Jianyu Wang. Li Xiong, Zheng Xu. Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Advances and open problems in federated learning. In arXiv, 2019.
Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. In International Conference on Machine Learning, 2019.
11

---

Published as a conference paper at ICLR 2025
Anastasia Koloskova, Tao Lin, Sebastian U Stich, and Martin Jaggi. Decentralized deep learning with arbitrary communication compression. In International Conference on Learning Representations. 2020a.
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. 2020b.
Anastasia Koloskova, Tao Lin, and Sebastian U Stich. An improved analysis of gradient tracking for decentralized machine learning. In Advances in Neural Information Processing Systems, 2021.
Dmitry Kovalev, Anastasia Koloskova, Martin Jaggi, Peter Richtarik, and Sebastian Stich. A linearly convergent algorithm for decentralized optimization: Sending less bits for free! In International Conference on Artificial Intelligence and Statistics, 2021.
Alex Krizhevsky. Learning multiple layers of features from tiny images. In Technical report, 2009.
Yann LcCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. In IEEE, 1998.
Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsich, Wei Zhang, and Ji Liu. Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent. In Advances in Neural Information Processing Systems, 2017.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In International Conference on Machine Learning, 2018.
Tao Lin, Sai Praneeth Karimireddy, Sebastian Stich, and Martin Jaggi. Quasi-global momentum: Accelerating decentralized deep learning on heterogeneous data. In International Conference Machine Learning, 2021.
Ziwei Liu, Anastasia Koloskova, Martin Jaggi, and Tao Lin. Decentralized stochastic optimization with client sampling. In Optimization for Machine Learning, 2022.
Othmane Marfoq, Chuan Xu, Giovanni Neglia, and Richard Vidal. Throughput-optimal topology design for cross-silo federated learning. In Advances in Neural Information Processing Systems, 2020.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication learning of deep networks from decentralized data. In International Conference on Artificial Intelligence and Statistics, 2017.
Angelia Nedić, Alex Olshevsky, and Michael G. Rabbat. Network topology and communication- computation tradeoffs in decentralized optimization. In IEEE, 2018
Shi Pu and Angelia Nedić. Distributed stochastic gradient tracking methods. In Mathematical
Programming, 2021.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recogmition. In International Conference on Learning Representations, 2015.
Zhuoqing Song, Weijian Li, Kexin Jin, Lei Shi, Ming Yan, Wotao Yin, and Kun Yuan. Communication- efficient topologies for decentralized learning with O(1) consensus rate. In Advances in Neural Information Processing Systems, 2022.
Yuki Takezawa, Han Bao, Kenta Niwa, Ryoma Sato, and Makoto Yamada. Momentum tracking: Momentum acceleration for decentralized deep learning heterogeneous data. In Transactions on Machine Learning Research, 2023a
Yuki Takezawa, Ryoma Sato, Han Bao, Kenta Niwa, and Makoto Yamada. Beyond exponential graph: Communication-efficeent topologies for decentralized learning via finite-time convergence. In Advances in Neural Information Processing Systems, 2023b.
Hanlin Tang, Shaoduo Gan, Ce Zhang, Tong Zhang, and Liu. Communication compression for
decentralized training. In Advances Neural Information Processing Systems, 201 8a.
12

---

Published as a conference paper at ICLR 2025
Hanlin Tang, Xiangru Lian, Ming Yan, Ce Zhang, and Ji Liu. D²: Decentralized training decentralized data. In International Conference on Machine Learning, 2018b.
John N. Tsitsiklis. Problems in decentralized decision making and computation. In PhD thesis, Massachusetts Institute of Technology, 1984.
Thijs Vogels, Sai Praneeth Karimireddy, and Martin Jaggi. Practical low-rank communication compression in decentralized deep learning. In Advances in Neural Information Processing Systems, 2020.
Thijs Vogels, Lie He, Anastasia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi. Relaysum for decentralized deep learning heterogeneous data. In Advances in Neural Information Processing Systems, 2021.
Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar. Matcha: Speeding up decentralized sgd via matching decomposition sampling. In Indian Control Conference, 2019.
Lin Wang, Yongxin Guo, Tao Lin, and Xiaoying Tang. DELTA: Diverse client sampling for fasting federated learning. In Advances in Neural Information Processing Systems, 2023.
Feijie Wu, Song Guo, Zhihao Qu, Shiqi He, Ziming Liu, and Jing Gao. Anchor sampling for federated learning with partial client participation. International Conference on Machine Learning, 2023.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. In arXiv, 2017.
Bicheng Ying. Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin. Exponential graph provably efficient for decentralized deep training. In Advances in Neural Information Processing Systems, 2021.
Kun Yuan, Bicheng Ying, Xiaochuan Zhao, and Ali H. Sayed. Exact diffusion for distributed optimization and learning- parst i: Algorithm development. In IEEE Transactions Signal Processing, 2019.
Kun Yuan, Yiming Chen, Xinmeng Huang, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. DecentLaM: Decentralized momentum sgd for large-batch deep training. In International Conference on Computer Vision, 2021.
Haoyu Zhao, Boyue Li, Zhize Li, Peter Richtárik, and Yuejie Chi. BEER: Fast O(1/T) rate for decentralized nonconvex optimization with communication compression. In Advances Neural Information Processing Systems, 2022.
13

---

Published as a conference paper at ICLR 2025
A TELEPORTATION WITH COMMUNICATION OVERLAP
In the implementation shown in Alg. 1 line 7 in Alg. 1 does not start until line 12 is completed. We modify Alg. that the exchanges of parameters lines 7 and 12 are performed simultaneously, We show the pseudo-code and illustration in Alg. and Fig. The communication in lines 7 and 12
Alg. T corresponds that in lines 9 and 13 in Alg.
Algorithm 3 TELEPORTATION
1: Input: the number of nodes set of nodes V,, number of active nodes k, total number of iteration T', step size 7, and topology comprising active nodes G3 (fI,
2: sample active k nodes ylo) "etive from V, without replacement.
3: assign {1,2. ... _k} to variables ftoken_iaee
_ E Vadive randomly without overlap.
4: for E 10 , do
5: sample next active & nodes v-(++) from Vn without replacement, and assign f1,2, ... , to
"active
variables (token_ia(()) ((+1) (f+1)
Uy v randomly without overlap.
6: for i E {1, ... n in parallel do
7:
if 0/ E (t)
V (t) active then
Fa (2) (9) tuy E (++3) active
8:
9:
send y
( to
[(token iak E E}.
end
(((+1)
11:
if of E active then
receive yj from Vy E foy E vith
(token id(tt)) wttkeooeiiiffl. idft) E E}.
12:
(1+1) => ev W =a("nnia((")) (((())) taken setn
13:
x;
end
15:
end for end for
16:
'The update rule of the parameters of the inactive nodes not described because the parameters held by the inactive nodes are discarded and initialized with the parameters of the other active nodes when they are activated line 13. The parameters of inactive nodes do affect the behavior of active node parameters.
Figure 5: Illustration of Alg. with n = 8 and 3. We use a line as the topology consisting of
active nodes Gy 2,1, [11, 1), (1, (2, (2, (3, 3)}). The black nodes represent active nodes, and the number written on the node is tooke_nii id The blue nodes represent the next active nodes, and the number on the node is token token_ia
14

---

Published as a conference paper at ICLR 2025
B PROOF OF THEOREMS AND 2
B.1 USEFUL INEQUALITY
Lemma 2. For any a, b E Rd, it holds that
l|a bll (1++))la (1+ 111011
(8)
for any y 0.
Lemma 3. For any a, b E Rd, it holds that
2(a, b) S |all 11bl2
(9)
B.2 NOTATION
In this section, we introduce the notation used in the proof. TELEPORTATION has parameters, {at (a=")) J==1 while the parameters of inactive nodes are not used and do not affect the behavior of the parameters of active nodes. To simplify the notation, we introduce the variables {=m Jm=1 that correspond to the active nodes parameters.
(t)
From line 5 in Alg. text_ia(" has different value for each active node e; active- That is.
v
es v=(0) activee (1, .... k} be the function that takes node index and returns token_ide i i Since g(t) is a bijection function, there exists an inverse function (g(+))-1 f1,2, k} + ii e E v(())
there is one-to-one correspondence between {i V Vative and {1, . Let g())
active }.
Using this inverse function, define variable rode_id00) follows:
node id = (g))))-
for any m E (1,2,...,hh node_ _i stores the node index i whose token token_id_" stores m. Using this notation, we define (1() E IRd as follows:
(t)
id
for all m E f1,2, ... , and f. From the definition (1) we can get its update rule as follows:
2 (1+1) x (1)
node_idii (+)++1)
= Σ
W
Loken (g(()1
(z.)) - 5x :
Σ
W
m,zokee
-
(1)
(1)
(())
Wm.l
VVF
node 1o node_id if bofe)))
iaft)
Wm
(t)
VVF
node s0 (z) (1), (1)) node node_ (.(o0)
(0) In the section, analyze the convergence behavior of (=m Jm=1- Note that sets (1)
(211 J Jm=1
(9)
and (xe(t) w E ((t) are equivalent, and their averages are equivalent, i.e.,
k
1
nodo_idd (d(()
n
W JEE aativ
1
Σ
(10)
15

---

Published as a conference paper at ICLR 2025
where 1
e is indicator function. Furthermore, let Z E R G R and Vf(z)
Ba*k as follows:
2
(1) (t) (0)
1 2
G =
VF
node idf (z) ; e(()
iof)) VF
(2 (t) e(0) s
nodo _
V)(Z = (f((z()) (t) Vf(2)") V)(2)))
By using the above notation, Alg.
can be rewritten as follows:
z(+1)= = - -r) W
WT.
B.3 MAIN PROOF
Lemma 4. Suppose that Assumptions 2 and 6 hold. If the step size satisfies 1j S
27. then
L
holds that
E =((+() - 21 ( /| + (1 +
L
LC2
k --1
2k 1
+
1
n
2k
n
where x(t) = E 2 and 3( = //4 Ei= E||z!" 102
Proof. By calculating the average of the update rule of z (1)
we obtain
k
((++)
Wm.!
2((0
VVF
1a (212) e()))
node i000)
k m=1
1=1
{(!)
FF
node_ id
(0) (2(") e00))
mode__aaf )
where we use Σm
W m,, 1. Using Assumption
we get
E(41f(((+11)
& Σg
= =E4if
z(()=
7 F
nodo o000)
(1) g(t (ooo)
Te
j=1
< {((((1)) 17 V)(2(0).
1
Es+1 VF
mode safo (2)0)
mode
k
+ 2
Ln²
Ee+1
T:
1
AF F
Lifees node_igftt)
node
(2)
(1), c(t)
node_ (g(())
j=
2
= =((((()) 17
()()())
1 k
Σ
Lal² Ex+1
p()
node_id iafo (2(5); c())
node_id
1=1
j=1
T
16

---

Published as a conference paper at ICLR 2025
where use the fact that active nodes are randomly selected, i.e., node_id to {1, ,n), in the last equality. Ti and T2 are bounded as follows:
_id)) is randomly assigned
+ (
\)(2f)) -V((E()))
-Ti = -
2
|| s|?
+ 2
V (f v)(((())
k j=1
)| /|2
1
Σ
[)( - )){= 1
+
21
j=1
||
2
L2
Σ
|2 2(00 =011
+
2h:
==1
k
k
T2 = Ret1
(t)
1ade_1af00 18/0 (2/1))
+ Re+1
VF
_ase_aaff laf0 (2)) (2))):)) 5(0) o00d) - VS nooe 1o (2/11)
k
node
h
node_
2
0²
rode_ node_ (af0 (
<
E141
f
k
k
h
k
+ o²
v)(((()
+ 11+1
f
node iي (z)00) - -V/(=/))))))
k j=1
==1
52 (1
k
+ 0²
1 {)=
n
2
V [(2 v)(2(0)
+2 {>({
||
2
+ k
22
(1 (1-k-
+ k
21 < h:
(1) - =10
+2 /
+ x²
(1 1 k カー 02
where we use the fact that the active nodes (() are sampled from Va without replacement in the third inequality. Using the above inequalities, we obtain
E (() S s()(0)
1
L
2) - /
2h
1=1
1 k
(1)
=00 + Laj
+
2
(1
1
k -
172 +
Loz
12
2k
n
2k
Using 1) S AL
we obtain the desired result.
Lemma S. Suppose that Assumptions 2 and 2 hold. If the step size satisfies v) S
Dt
then
V241.
holds that
E(+1 <(1 Pk P))
6(1 pk ))
V V)(2())
1|= |1=(111-----11111 (11--p))(0 + +
E
Ps
where z(1) 1 - 2
(1) and = t/2 E Ee|2!00 (0 111
17

---

Published as a conference paper at ICLR 2025
Proof.
B++1 z(itt)= 2((t)]12
= -E++1 (2 ,)) WT - (Z n) 1
(2(1) ( (Z)) -n ||2
$ (1 - pa En
(2 ( 20122
< (1 - yd E
(1) ((O(1 200 | + (1 - Pk 2 Ee41 G - [(2
s (1 - Pk
< (1 Pk
(2 (2
z00
(1 P4: p4))((' + m²²
x (1 Pk
| z002
3(1 pk) )))
|)() / +(1 - pb)){(p? + +
2
F
Pk
i' bounded follows:
T = T=2 ()(2())
+2 V)(2w)]
F
212 z - 2001 2h |)
where 200 2 11 Then, we get
(((11) 2((11) 2
Ex+1
6(1 - P2)
Pk
z(1)= - _
|z(0] - -
< (1
2
Pk
6(1
Ph) kT)
\)(=(>>|| /|( + - pk)o(pk 12))
Pk
Using 7 < /21L"
we obtain the desired result.
Lemma 6. Suppose that Assumptions 3 and 6 holld and {x,
(0) pr is initialized with the same
parameter (00)_ If the step size satisfies 1) S /24L'
then it holds that
T + =0 Σ
24(1
24(1-Ps) - Pk)
4(1 pa (o² (2) y?2
T+I
T+I
[T +
17
E (
Pk
where z(t)
==))= = Σ 2 and = = 1/2 Σ E| 201222
Proof. From Lemma 5 we get
E(++1) < 6(1 - ?m) Σ
Pk
+ +(1 - -1- + +(2) Σ
Pk Pkyt-1 4
Pk
4
t=
1-1
6(1 - pm)
Pk
4(1 (1)-p))(02 + +22)
Pk
4
Pk
1=0
18

---

Published as a conference paper at ICLR 2025
By summing up the above inequality from t = to T
1, we obtain
T
6(1 pa nr
T
+ 4(1 - -px) + +(²) 1p
(1)
Pk
(T +
Pk
1=0
6(1 -p
E [V((() 21
Σ (1
Pk
) 4(1 - pk) + +52)
(T + 1)
4
Pk
(=/+1
6(1 - pp T
T-1
4(1 - px) + t22) 11
E [IV](E |1
Σ
(1
Pky pb +
(T + +1)
4
Pk
P=11
24(1 p)a)n²
4(1 (o + +(2) 12
(
12
(T + 1)
Pk
Using ((0) 0 and E|| (
1
0, we obtain the desired result.
Lemma 7. Suppose that Assumptions
3 and 6 hold, and {æ; Rim is initialized with the same
parameter =00). If the step size satisfies r
Ph
then it holds that
V192
T+1 V f + active 11?
8(f 80) f*)
322 5 ph) 1/2 +
4L
(1 k - 1
o²+
+
52
(11)
(T (T+
Pk
k
where (1)) accive = E anty
Σ
Proof. Rearranging Lemma obtain
( 12 4(Ef(=()) Ef(z(++1)
2Lo²
2L
k- n.
+ (1) +
1j
+
11-
7
k
k
Using Lemma
o
we get
T
1
{
+ T
t=
4(f(=(0)) - f²)
4L2 ((t) 2L0²
215²
(1-b-1) "
h 1
1 11
+
n
(T'+ 1)m
T+1
k
n
4(f(2 - f*)
96L2(1 p&)
16L p=) +(2),p
E[[V)(=()))
(T 11 17
(T 1)m
Pk
2
2
k: - --1 n
11
+ b
11
+
n
Using 1)
Ph V192L
and T.. (t)
activee g(t) (see Eq. 100). ). we obtain the desired result.
Lemma 8. Suppose that Assumptions
and 6 hold, and {æ. (0) ye is initialized with the same
parameter x (0), There exists a step size n that satisfies
E V (z 11
T
Lro(o² + (1 - -1-13)) (=))
L330(002 + (1 pb))
Lro
00
(12)
KT
T2
Tpp.
where a (1) = 1 Eo ( and ro = f(z(0)) - ft.
19

---

Published as a conference paper at ICLR 2025
Proof. Choosing the step size as follows:
2kro
ToPk
Pk V1922
1) = min
L(T+ +53)
- (1(1
+ (2)
we have three cases:
When
2krm L(T 1)(0 + - ))
THI E. Bl| (I nctiv) )|² is bounded from above
by
128Lro (2 + (1 --
22048L30 pk) + +2)) $ (T + 1)ppk
k(T + +1)
When 17
1++ El= E f (0)
active) 11 is bounded from above
41.(7+1](1 1x)(0=+(1)
by
32Lro (02 + (1 +=)
1638442r (1pp) px) + < 3
k(T +1)
+ 1))pkk
When V192L' T+I
1 Et ==
V f + (1)
active 1| is bounded from above by
12288Tro
32Lro
02 + (1 o22
-
20048T.23(1 - (o² + (2) {2))²
+
(T + 1)pk
k(T 11
+ 11
Lemma 9. Suppose that Assumptions 2 and holld and {2, ) is initialized with the same
parameter ())) Then, if the active nodes connected by a ring, i.e., ps- (2(k=2), there exists step size 1) > 0 and the number of active nodes E 21,2,-. ... n that satisfies
1
B V (1)(1) )
T
t=0
Lrooz nT +
LrolO" Lro(o=+(3)+ +2)
(Lroloo+ + (2)3) Lro
<0
T
where a acctive
(t)
x
and ro f(x(1)) ft.
Proof. From Lemma
we obtain
T
)|
T+1 1=
Lrolo² +1 -1-
+ k22 (3)
Lrok?
0
+
(13)
KT
T
T
For simplicity, let A, B, and C' denote as follows:
A Irolo² +
12 + (
Lro T
==
C
T
T
20

---

Published as a conference paper at ICLR 2025
Using these notations, obtain
(v%
A
T+1 (4)
(
acuve) )1( 000
Bk + Ck2 +
(14)
We choose & as follows:
[
A
max 1. min
B6
Note that it holds that &o E (1, .n].
When ro + (2) = 0, holds that
1,
and
0. this case,
7+1 E B| V f (f)
2 is bounded from above by
O Lrg
T
When rolo + +3) > O, it holds that
A3
k
B6
m
In this case, we have three cases:
[ 11
When k =
we have
B6
V K
A
- o (A
-
BK -A Ck2 O
By using the above inequalities, T+I Et B1| V f (f) 11 is bounded from above by
0 A A +
When h n, we have
lro + (1 22)
Lroo2 nT
Bk
<O(AB)))
CK 0o (CA
KT
+1
where we use h: < is bounded from above by
By using the above inequalities,
THI El B VJ active )|(
13
Lr nT
+ + +ABB+O)
By summarizing the above inequalities, we obtain the desired results.
3 and hold, and 10 initialized with the same parameter (0), Then, if the active nodes are connected by an exponential graph, iee, Pk = alogg k), there exists a step size 1j > and the number of active nodes l E (1,2, n) that satisfies
Lemma 10. Suppose that Assumptions
Σ E [V (t)
)1
T+1
(Vinn
$) )²)
[ nT
122 +22)
T(o² + +2)
)
Lro log2 + T
T( +(02+(3))
Lro
+
logg
+
T2
Tro
Tro
T
where a (())
= Enjeven
x and ro = f(((0)) ft.
Bastive
21

---

Published as a conference paper at ICLR 2025
Proof. From Lemma g
obtain
E V
(e)
I
T+1
active
2=0
so
Liolo² + (1 )+)
(Lir8l02 + (2) log (Ki 1og)(k)
$
Lro (kge(() (k)
kT
T
T
For simplicity, let A, B, and C denote as follows:
A Lrolo² + +2)
122 + (2)
$
Lro
B=
C
T
T
T
Using these notations, obtain
fa active )1 50 (V
B
B
B logg (k) + C (o)g)(())
t=
We choose & as follows:
max 1, min A
B2
C
11
When ro + (²) = O. it holds that k
1,
A = 0,
and
B = 0. In this case,
Σ B|| [ II? is bounded from above by
Tro
T
When ro(o? +()) > 0, it holds that
A
A
min
B
C
In this case, we have three cases:
When
[( !1"
bounded from above by
18
T+1
:=
(a))
c ))
B loog
Coog
Ba
[A]
When
02
T+I
21=
2 V
bounded from above by
log
+ C Coga
B
C2
When A n, 7
Et E V
active
)12 is bounded from above by
0
(
o
Linoz nT
Bogg 1
A
+ B
+ C' Cloo2
B
C
By summarizing the above inequalities, obtain the desired result.
22

---

Published as a conference paper at ICLR 2025
C PROOF OF THEOREM 3
Lemma 1. For any k- < n, there exists l: E 21,2,488, ... 2 211xg(++1)-11 that satisfies R² 4 < ks (nog, (n-s]]
k* Furthermore, holds that -i=0
S n.
Proof. We define K. = (1,2,4,8, 8,,,.... (1 We have two cases:
When 1 k* < [ngg((++))) 1)1, there exists &s E K. that satisfies & S 2k. When 2 [ng2(++)]]
< k* < Rt it holds that k < k* for all k E K. Then, we have
k² < n x (
Thus, there exists it E that satisfies k < k- 4k.
By combining the above two cases, we obtain the desired result.
Lemma 11. Suppose that Assumptions 1
and h Let (f vev ITo denote the some
parameters of active nodes generated by Alg. when the number of active nodes is set to l and define K 2,, 2,,2,22, 23, ...., (.,.....,,,,,1)))) (1 n... Then, suppose that the parameters are initialized with the same parameter (x)
Ring: If the active nodes are connected by ring, iee, 22(k2 there exists n such that minkek
T+I Ei V (F actve, is bounded from above by
(
[TTOR nT
[Irolo++ (3))
( + (2)
Lro T
T
where ro f( (etivee,k) f* and x (t)
octive En ev Kk
Exp. Graph: If the active nodes are connected by exponential graph, i.e., Ph 52 k). there is bounded from above by
exists 1) such that mingek
T+I Et
LTooz nT
L2rg( +())
T(o² + +
)1)
#)
+ Lro log2
T(o² T(oo+
Lro
+
log2
+
T2
Tro
Tro
T
Proof. By combining Lemmas
and 10 we obtain the statement.
23

---

Published as a conference paper at ICLR 2025
D CONVERGENCE RATE OF DECENTRALIZED SGD WITH VARIOUS TOPOLOGIES
Table 2: Convergence rates of DSGD over various topologies.
Topology
Convergence Rate
Ring Nedić et al.
Lmio? Loaa? nl
1/2
Lxynn
Torus Nedić et al. 2018
+
12
1 Lann
Exponential Graph Ying al.
2021
o
Locer
1'rr lory +ooss +log,
72
loggin)
+ Liu log, (s))
Base-2 Graph Takezawa et al. 2023b
Lager? m
1.
Mogoinio (eeestnn +
Iin lngs.
E CONVERGENCE RATE OF DECENTRALIZED SGD WITH CLIENT SAMPLING
Proposition Liu et al. (2022)). Suppose that Assumptions 7 2 3
and S hold. Let be the
number of active nodes and [(, with client sampling. Then, there exists the step size v) that satisfies:
() yi=) Y denote the parameters generated by Decentralized SGD
T Σ E EI 1=0
(1
[rooo2
(1 +=)))) +
( k
Lrolo /Pn + (²2)
Lro Tpa
+
T+1
KT
Tpn
where To f(x(0)) f
fo and x(1) Ei
(t)
n
Remark 1. The convergence rate in Proposition 2
consistently deteriorates as decreases.
Unlike TELEPORTATION, the convergence rate shown in Proposition 2 and third terms degrade as n increases.
depends pus and the second
24

---

Published as a conference paper at ICLR 2025
F
ADDITIONAL EXPERIMENT
Teleportation (Ring)
Decentralized SGD (Ring)
Teleportation (Base-2 Graph)
Decentralized SGD (Base-2 Graph)
Ç² 0,
0²
c² = 10, =0
= 100, 0² = 0
Consensus Error
10'
10f
109
10
10
10"1
101
10a
10
10
10
10
10a
10
10
Consensus Error
2² = 0, 0² = 10
(² = 10,
0 = 10
<² = 100, o = 10
10
10-2
10-2
10-2
10
10
10
10
10a
10
10a
10a
10a
10a
2² =² 0, 0²
100
Ç = 10, _2
100
Ç²
100,
100
Consensus Error
10'
10a
107
10a
10a
10a
10-1
10-2
10-2
10-4
10-4
10-4
10
10a
105
10
10a
10a
101
10a
10a
Iterations
Iterations
Iterations
Figure 6: The behavior of consensus error
3Σ evv a
x. activell for different stochastic noise
o² and heterogeneity 2 The experimental setup was the same as in Fig. 2 Note that when the optimal number of active nodes & one, did not plot the consensus error. See Table
10.0
0.1
90
90
Teleportation (Ring)
Teleportation (Base-2 Graph)
Decentralized (Ring)
Accuracy
Accuracy
Decentralized SGD (Base-2 Graph)
60
60
100
200
100
200
300
400
Second
Second
Figure Test accuracy of TELEPORTATION and Decentralized SGD under heterogeneous networks with r = 0. The experimental setup was the same as in Fig.
25

---

Published as a conference paper at ICLR 2025
G EXPERIMENTAL SETUP
Table 3: Experimental setups for Fig.
Step size
Grid search over 10.1, 0.075, 0.05, 0.025, 0.01, 0.0001)
Computational resources
AMD Epyc 7702 CPU or Intel Xeon Gold 6230 CPU
Table 4: Experimental setups for Fashion MNIST in Fig.
Model
LeNet
Step size
Grid search over {0.1, 0.01, 0.001
Batch size
32
Momentum
0.9
Epoch
200
Computational resources
Titan x 8
Table 5: Experimental setups for CIFAR- in Fig.
Model
VGG Grid search over {0.1, 0.01, 0.001)
Step size
Scheduler
Cosine decay
Batch size
32
Momentum
0.9
Epoch
500
Computational resources
A6000 x 8 or RTX 3090 x 8
Table 6: Experimental setups for Figs. 4 and
Model
LeNet
Step size
Grid search over {0.1, 0,01, 0.001)
Batch size
32
Momentum
0.9
Epoch
200
Computational resources
A6000 x 8
26


Reviews:
[{"review_id": "FyugfG5kEe", "reviewer": "Reviewer_Neby", "summary": "This work studies a decentralized optimization algorithm whose convergence rate does not deteriorate with increasing number of nodes. Usually, when number of nodes in a network increases, the spectral gap, i.e., $(1 - p_n)$ (according to the notation of the paper), also increases. Larger spectral gap means that decentralized SGD requires a larger number of iterations to converge.\n\nIn order to make decentralized SGD scalable for large networks, the proposed algorithm randomly activates a small subset of nodes by randomly sampling them. These nodes get the updated models from nodes activated in the last iteration, does a descent step, and subsequently communicate with other nodes active in the current iteration to do a local consensus step (only amongst the currently activated node). this process is repeated over multiple iterations.\n\nThe paper analyzes the convergence of this algorithm, and also provides an efficient algorithm to tune the number of active nodes.", "questions": "I have some more questions which are not very critical, but I believe that the paper will benefit from:\n\n1. In the current proposed algorithm, data heterogeneity is not taken into account. Some discussions on how the algorithm might need to be modified in the presence of data heterogeneity would be appreciated. Perhaps optimizing the weight matrix $\\mathbf{W}$ would be helpful?\n\n2. Although less related, in light of the popularity of federated learning literature, the privacy of activated nodes might be an important criteria to consider. Since each node knows which node participated in the previous iteration, this can lead to some degree of privacy leakage, that needs to be quantified. (Please note that I do not see this as a major drawback of the paper -- it is just a suggestion). It ties more with my previous question of practical application scenario, where the network has a large number of nodes, so privacy becomes important.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is generally well-written. The problem statement being addressed is clear, and the proposed algorithm is also quite simple. The paper does a commendable job analyzing their proposed algorithm, in addition to validating numerically. The assumptions are also clearly stated, which are quite standard in decentralized optimization.\n\nThe work also compares their algorithm with client sampling, which is a natural question that came to my mind while reading the paper, and I appreciate that it was answered. I have a few concerns and would be glad if these are addressed. Despite my concerns, I strongly believe that within the current scope of the problem statement considered in the paper, it is adequately addressed.", "weaknesses": "I would appreciate it if the authors would answer some of my concerns.\n\n1. How are the consensus weights $\\mathbf{W}$ chosen, and how is it assumed that the randomly activated nodes at any iteration know these weights? \n\n2. How are the nodes sampled? Are they sampled uniformly at random? Would it help if the nodes were sampled taking some other criteria in mind, such as activating nodes that are more likely to have an edge between them? More generally, how do the authors expect the sampling to be implemented in practice in a fully decentralized topology? More generally, can the authors highlight a practical application scenario?\n\n3. The paper would benefit with some explicit discussion on the dependence of the node-selection strategy, and/or the required number of active nodes on the network topology? For instance, it seems like if the network is sparse, perhaps more nodes need to be activated at every iteration?\n\n4. Will it make sense to change the number of activated nodes in every iteration?\n\nI must acknowledge that I am not completely familiar with the current literature in topology selection for decentralized optimization. So I cannot definitively comment on the novelty of the paper, but based on how it is placed in the writing itself, the contribution seems non-trivial (despite the weaknesses mentioned here).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "iXW2s9NnoY", "reviewer": "Reviewer_AkDU", "summary": "This paper proposes a novel decentralized algorithm designed to perform well when the number of nodes $n$ is very large. The proposed algorithm synchronizes a smaller set of local states $\\\\{z_i\\\\}_{i \\in \\\\{1,...,k\\\\}}$ for $k < n$ by running a single step of Decentralized SGD (DSGD) [Lian et al., 2017] on a subgraph of $k$ nodes, and then transfer the local states to another set of $k$ nodes for computing the gradients of other local objectives. Such algorithm is suitable for fully-connected distributed system. The proposed theorem suggests that this algorithm enjoys linear speedup by the total number of nodes $n$, at the cost of consuming $k$ local gradient computations only.", "questions": "(**About experiment**)\n- I suggest the authors to plot the convergence of consensus error in the experiments as well. This can give a clearer picture to whether the $k$ nodes interaction in the proposed algorithm achieve faster convergence in consensus error than the $n$ nodes interaction in Decentralized SGD.\n\n(**About the proof of Lemma 9**)\n- Let's make it clear when does the dominance order changes in (14) for different values of $k$ by the following statements:\n$$ \\sqrt{A/k} \\leq Bk^{2/3} \\Leftrightarrow k \\ge (A^3 / B^6)^{1/7} \\quad \\cdots (*)$$\n$$ \\sqrt{A/k} \\leq Ck^{2} \\Leftrightarrow k \\ge (A / C^2)^{1/5} \\quad \\cdots (**)$$\nThen, by the choice of $k$ in line 1099, \n- when $k = \\lceil (A^3 / B^6)^{1/7}\\rceil \\leq \\lceil (A / C^2)^{1/5}\\rceil$, $(*)$ is true while $(**)$ is false, i.e., $\\sqrt{A/k} = \\mathcal{O}(Bk^{2/3}) = \\mathcal{O}(A^{2/7}B^{3/7})$ and $Ck^2 = C A^{6/7} B^{-12/7}$. Then line 1106 should be $\\mathcal{O}(A^{2/7}B^{3/7} + C A^{6/7} B^{-12/7})$ instead.\n- when $k = \\lceil (A / C^2)^{1/5}\\rceil \\leq \\lceil (A^3 / B^6)^{1/7}\\rceil$, $(**)$ is true while $(*)$ is false, so that by the similar arguement line 1112 should be $\\mathcal{O}(A^{2/15} B C^{-4/15} + A^{2/5}C^{1/5})$.\n- when $k = n \\leq \\min\\{ \\lceil (A^3 / B^6)^{1/7}\\rceil,  \\lceil (A / C^2)^{1/5}\\rceil \\}$, both $(*)$ and $(**)$ are false and line 1117 should be $\\mathcal{O}(\\sqrt{A/n} + Bn^{2/3} + Cn^2)$.\nTherefore, none of the above cases show a convergence bound that is consistent with the main claim in Theorem 2, i.e., a linear speedup with total number of nodes $n$. May I request the authors to address this issue, and point out my mistakes if I am wrong in the above calculation. \n- The similar argument applies to the proof of Lemma 10.\n\n(**Connection to DSGD**)\n- We can equivalently interpret the proposed algorithm as a DSGD [Lian et. al., 2017] algorithm of $k$ nodes and each node has access to all local objective $f_i, ~i\\in \\\\{1, ..., n\\\\}$. Each iteration of the proposed algorithm with an active node set $V^{(t)}$ corresponds to an iteration of the above-mentioned DSGD algorithm where $\\\\{\\nabla f_j(z^{(t)}_{{\\rm token\\\\_id}_j^{(t)}}, \\xi_j^{(t)}): v_j \\in V^{(t)}\\\\}$ are the sampled local gradients. Therefore theoretically, by the results of [Lian et. al., 2017], I expect that the proposed algorithm to only achieve the linear speedup of $\\mathcal{O}(1/\\sqrt{kT})$. \n- Also, by the above equivalence, the proposed algorithm is only serving as a new implementation of DSGD on large graph without data heterogeneity, i.e., $\\varsigma = 0$ in Assumption 1.3 of [Lian et. al, 2017].\n\n- I suggest the authors to consider along this argument and compare with DSGD in the main text in terms of such equivalence. Also, since this algorithm  is potentially only contributing an efficient large graph implementation of DSGD, I suggest the authors to expand the experiment section with larger scale experiments such as larger dataset and larger number of nodes $n> 100$.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 4, "contribution": 2, "strengths": "- The idea of sacrafising gradient updates of the whole network in favor of maintaning lower consensus error is novel.", "weaknesses": "- In line 268, $k$ can be simplified as \n$$\nk = \\max\\left\\\\{ 1, \\min \\left\\\\{\\left\\lceil \\left(\\frac{T(\\sigma^2 + \\zeta^2)}{Lr_0} \\right)^{1/7} \\right\\rceil, n \\right\\\\} \\right\\\\}\n$$\nbecause $a^{1/7} < a^{1/5}$ for any $a > 1$.\n- The main claim of Theorem 2 might be theoretically flawed and deserves more attention, which relates to the $n$ linear speedup results. More discussion is provided in the section Questions: (**About the proof of Lemma 9**).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "l0rDFkerZc", "reviewer": "Reviewer_bkGn", "summary": "This paper introduces a method called TELEPORTATION aimed at improving decentralized learning, particularly decentralized stochastic gradient descent (SGD). \n\nTELEPORTATION is have a better dependence on the spectral gap of the communication graph in the convergence rate. So, the authors claim that their method can alleviate the convergence rate degradation while maintaining communication efficiency. \n\nThey also propose a method to optimize the number of active nodes so as to fasten the convergence rate. \n\nThe experiments suggest that TELEPORTATION outperforms decentralized SGD in both convergence speed and stability, especially when data distribution is uneven across nodes.", "questions": "1. **Convergence and the Number of Nodes**:  \n   I am unsure why decentralized learning methods should necessarily converge more slowly as the number of nodes increases (line 53-line 60). In fact, in fully synchronized systems, having more nodes typically leads to a linear speedup in convergence. It would be helpful if the authors could clearly formulate why this slowdown happens in decentralized settings and explicitly highlight the limitations of existing methods. A more specific problem formulation, accompanied by examples illustrating why current approaches fail to address this, would make the contribution clearer. (e.g., using a table summarizing existing results).\n\n2. **Discussion on Proposition 1**:  \n\n   The discussion in lines 140-148 seems to rely on the upper bound from Proposition 1. However, this argument feels weak, as the tightness of the upper bound is never discussed. If the bound is loose due to flaws in the analysis, the subsequent discussion would be rendered meaningless. Is there any way to demonstrate that the bound is tight? For instance, you could explore the behavior of a simple quadratic function to provide more concrete support for this bound.\n\n3. **Explanation of Theoretical Improvements**:  \n\n   It appears that the theoretical improvement primarily stems from the dependence on $p_n$. Could the authors clarify the source of this improvement? Is it driven by a more refined analysis, or is it due to a novel aspect of the algorithm itself? Providing a brief but clear explanation of what underlies this theoretical gain would strengthen the paper.\n\n4. **Unclear Impact of Hyperparameter Tuning**:\n\n   The proposed hyperparameter-tuning method for selecting the number of active nodes adds another layer of complexity to the method. However, the impact of this additional tuning on overall training time and resource consumption is not fully explored. In practice, the benefits of communication reduction could be outweighed by the cost of hyperparameter search. A detailed examination of this trade-off would provide more practical insight.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. **Reduced Communication Overhead**: \n\nThe paper proposes a practical solution to reduce the communication costs in decentralized learning by activating fewer nodes. The methods developed to tune the hyperparameters would inspire future work.\n \n2. **Clear Theoretical Analysis**: \n\nThe paper provides solid theoretical support for the claims, including convergence rate bounds and proofs for the proposed method.  \n\n3. The paper is mostly well-written and easy to follow.", "weaknesses": "1. **Lack of Clarity in Problem Formulation**:  \n   The paper could benefit from a clearer and more formal description of the problems posed by decentralized learning, particularly why more nodes lead to degraded performance. Without this clarification, it becomes difficult to fully appreciate the novelty and impact of TELEPORTATION.\n\n2. **Loose Theoretical Guarantees**:  \n\n   Beyond Proposition 1, the paper could be more rigorous in establishing the tightness of the bounds used to justify the method's benefits. A deeper exploration of whether these bounds hold tightly in practical cases (e.g., through empirical validation or consider quadratic cases) would enhance confidence in the theoretical contributions.\n\n3. **Limited Practical Applicability**:\n\n   The assumption that any two nodes can communicate directly (as mentioned in the abstract and discussions) is overly idealized. In many real-world applications, such as wireless sensor networks or geographically distributed systems, this assumption may not hold.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "50jTYEX244", "reviewer": "Reviewer_67Bz", "summary": "The paper addresses degradation in decentralized learning arising from fixed communication patterns. Given the flexibility to select both a communication pattern and a subset of active nodes, the authors propose the TELEPORTATION algorithm. This algorithm activates k nodes per iteration and applies a specific topology to these nodes, facilitating adaptable communication.\n\nThe convergence analysis for TELEPORTATION follows the approach used by Koloskova (2020b), extending it to any number of active nodes k. Additionally, the authors provide an efficient method for tuning k, including determining optimal values for specific graph types, such as rings and exponential graphs, where they establish the theoretically best k and its associated convergence rate.\n\nExperimental results demonstrate that TELEPORTATION consistently outperforms decentralized SGD across various settings and graph structures, reinforcing its potential advantages in decentralized learning.", "questions": "What are the Base-2 graph and what do you mean by superiority of this graph?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The primary strength of this paper lies in its proof of Theorem 1, which effectively addresses a key limitation in previous analyses of similar algorithms. Prior approaches encountered challenges due to the disconnectivity of graphs under certain node activation conditions (e.g., when p=0), resulting in an infinite bound on the number of iterations required for convergence. Remarkably, this paper recovers the bound obtained by Kolosokova (2020b) under a generalized node selective activation scheme, which could prove potential for future research in this domain.\n\nIn addition to the theoretical insights, the paper is also notable for its clear presentation of contributions. The experimental section is both comprehensive and persuasive, further validating the authors' approach and supporting the potential utility of their bound.", "weaknesses": "Even though the distinction of TELEPORTATION from client sampling has been discussed, it still looks to me a follow-up variant in this category (McMahan 2017), and client sampling has been a heavily discussed approach. In the special case where any node is allowed to connect to any node, decentralized learning with client sampling is a very natural idea. Admittedly the proof of this paper could be something new, but the approach they proposed, at least in practice, might have been discussed/implemented allready. In particular, it is expected  when you select a fixed graph of size k, where its spectral gap is known for example in ring and exp. graph, the spectral gap does not show up in the bound. In this sense, \"completely alleviate the convergence rate degradation\" is not that interesting any more.\n\nMinor: there are no black nodes in Figure 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)