DIGEST: FAST AND COMMUNICATION EFFICIENT DECENTRALIZED LEARNING WITH LOCAL UPDATES
Authors: Peyman Gholami
Hulya Seferoglu
Venue: Submitted to ICLR 2023 (2023)
Keywords: Decentralized Learning
Distributed Optimization
Communication Efficient Learning
Local SGD
Federated Learning

Abstract: Decentralized learning advocates the elimination of centralized parameter servers
(aggregation points) for potentially better utilization of underlying resources, de-
lay reduction, and resiliency against parameter server unavailability and catas-
trophic failures. Gossip based decentralized algorithms, where each node in a net-
work has its own locally kept model on which it effectuates the learning by talking
to its neighbors, received a lot of attention recently. Despite their potential, Gossip
algorithms introduce huge communication costs. In this work, we show that nodes
do not need to communicate as frequently as in Gossip for fast convergence; in
fact, a sporadic exchange of a digest of a trained model is sufficient. Thus, we
design a fast and communication-efficient decentralized learning mechanism; DI-
GEST by particularly focusing on stochastic gradient descent (SGD). DIGEST is
a decentralized algorithm building on local-SGD algorithms, which are originally
designed for communication efficient centralized learning. We show through anal-
ysis and experiments that DIGEST significantly reduces the communication cost
without hurting convergence time for both iid and non-iid data.

Under review as a conference paper at ICLR 2023
DIGEST: FAST AND COMMUNICATION EFFICIENT DECENTRALIZED LEARNING WITH LOCAL UPDATES
Anonymous authors Paper under double-blind review
ABSTRACT
Decentralized learning advocates the elimination of centralized parameter servers (aggregation points) for potentially better utilization of underlying resources, de- lay reduction, and resiliency against parameter server unavailability and catas- trophic failures. Gossip based decentralized algorithms, where each node net- work has its own locally kept model on which it effectuates the learning by talking its neighbors, received lot of attention recently. Despite their potential, Gossip algorithms introduce huge communication costs. In this work, we show that nodes do not need to communicate as frequently as Gossip for fast convergence; in fact, sporadic exchange of global model is sufficient. Thus, we design fast and communication efficcienf decentralized learning mechanism; DIGEST by par- ticularly focusing stochastic gradient descent (SGD). DIGEST is decentral- ized algorithm building on local-SGI algorithms, which are originally designed for communication efficient centralized learning. We show through analysis and experiments that DIGEST significantly reduces the communication cost without hurting convergence time for both iid and non-iid data.
INTRODUCTION
Emerging applications such as Internet of Things (IoT), mobile healthcare, self-driving cars, etc. dic- tates learning be performed on data predominantly originating at edge and end user devices (Gubbi Li et al. (018a) A growing body of research work, e.g., federated learning (McMahan 2016 Kairouz et al. 2021 Konecný et al. 2015 McMahan et al. 2017 [i et al. 2020a b) has
al.
2013
itt al. focused on engaging the edge in the learning process, along with the cloud, by allowing the data to be processed locally instead of being shipped to the cloud. Learning beyond the cloud can be advan- tageous terms of better utilization of network resources, delay reduction, and resiliency against cloud unavailability and catastrophic failures. However, the proposed solutions, like federated learn- ing, predominantly suffer from having a critical centralized component referred to as the Parameter Server (PS) organizing and aggregating the devices' computations. Decentralized learning emerges as a promising solution to this problem.
Decentralized algorithms have been extensively studied in the literature, with Gossip algorithms receiving the lion's share of research attention (Boyd et al. 2006b; Nedic & Ozdaglar lar 2009a Koloskova et al.) 2019; Ayssl et al. 2009 Duchi al., 2012a Kempe al., 2003 Xiao & Boyd 2003 Boyd et al. 2006a). In Gossip al algorithms, each node (edge or end user device) has its own locally kept model on which it effectuates the learning by talking its neighbors. This makes Gos- sip attractive from failure-tolerance perspective. However, this comes at the expense of a high network resource utilization. As shown in Fig. Ia all nodes in a Gossip algorithm in a synchronous mode perform model update and wait for receiving model updates from their neighbors. When a node completes receiving all the updates from its neighbors, it aggregates the updates. As seen, there should be data communication among all nodes after each model update, which is a significant com- munication overhead. Furthermore, some nodes may be a bottleneck for the synchronization as these nodes (which are also called stragglers) can be delayed due to computation and/or communication delays, which increases the convergence time.
Asynchronous Gossip algorithms, where nodes communicate asynchronously and without waiting for others are promising to reduce idle nodes and eliminate the stragglers, i.e., delayed nodes (Lian) et al. 2018 Li et al. 2018b] Avidor & Tal-Israel, 2022). Indeed, asynchronous algorithms signif- icantly reduce the idle times of nodes by performing model updates and model exchanges simul- taneously as illustrated in Fig. [b For example, node can still update its model from x! to x/41 and x while receiving model updates from its neighbors. When it receives from all (or majority)

---

Under review as a conference paper at ICLR 2023
Pwrt
Reov
10206
X
Fwwy
Reck
00d02
Reev
Rew
nod80
22
>3
Rodc3
00000
Piay
Rooy
(a) Syne-Gossip
(b) Asyne-Gossie
144
1046
Xmli
1930
Jent
*442
x2
09262
V1
111
127
rode3
Xmi
(c) Handom-WWal
(d) DIGEST
Figure 1: DIGEST in perspective compared to existing decentralized learning algorithms; (a) syn- chronous Gossip, asynchronous Gossip, and random-walk Note that "V" represents a model update. "Xmit" represents the transmission of model from node to one of its neighbors. "Reev" repre- sents the communication duration while receiving model updates from represents model aggregation. xi shows the local model of node iteration t. For random walk algorithm, the global model iterates are denoted as X₃.
a node's 's neighbors. "A"
of its neighbors, it performs model aggregation. However, asynchronous Gossip does not reduce communication overhead as compared to synchronous Gossip. Furthermore, the delayed updates. also referred gradient staleness in asynchronous Gossip may lead to high error floors (Dutta al. 2021. or require very strict assumptions to converge to the optimum solution
(Lian et al. 2018).
If Gossip algorithms are one side of the spectrum of decentralized learning algorithms, the other side random-walk based de- centralized learning (Bert- sekas
PS
12
X
X
x
X
X
x
node
V
V
V
V
1996; Ayache & Rouayheb 2021 2021 Sun et. al.
Figure 2: Local-SGD with // sequential SGD steps in node v.
2018| al., 2014). The random- malk algorithms advocate activating a node a time, which
would update the global model with its local data as illustrated in Fig. Ic Then, the node selects one of its neighbors randomly and sends the updated global model. The selected neighbor becomes newly activated node, it updates the global model using its local data. This continues until conver- gence. Random- walk algorithms significantly reduce the communication cost as well as computation and power utilization in the network with the cost of increased convergence time.
Our key intuitions this work are that (i) nodes do not need to communicate as frequently as in Gossipfor fast convergence; in fact, sporadic exchange of a model is sufficient, and (ii) nodes do not need to wait idle as in random walk. Thus, we design fast and communication-effieee -eftttiinneffiienttt de- centralized learning mechanism; DIGEST by particularly focusing (SGD). DIGEST a decentralized algorithm building on local-SGD algorithms, which are origi- nally designed for communication efficient centralized learning (Stich) 2019 Wang & Joshi [021]] Lin et al. 2020). In local-SGD, each node performs multiple model updates before sending the model
stochastic gradient descent
PS as illustrated in Fig. 2 The PS aggregates the updates received from multiple nodes and transmits the updated global model back to nodes. The sporadic communication between nodes and the PS reduces the communication overhead. Our goal in this work is to exploit this idea for decentrulized learning. The following are our contributions.
Design of DIGEST. anism; DIGEST by particularly focusing on stochastic gradient descent (SGD). DIGEST works as follows. Each node keeps updating its local model all the time as in local-SGD. Meanwhile, there is ongoing stream of global model update among nodes, Fig. ld For example, node
We design a fast and communication-efficee
decentralized learning mech-
2

---

Under review as a conference paper at ICLR 2023
starts transmitting the global model to node 2 at time t. When node 2 receives the global model from node 1, it aggregates it with its local model. The aggregated global model is transmitted to node 3 next. We note that the exchanged models are global models as each node adds its local updates to the received model. node that has the global model selects the next node for global model transmission randomly among its neighbors. After all the nodes update their mod- els with a global model, DIGEST pauses global model exchange, while local SGD computations still continue. The global model exchange repeated at every // iterations. DIGEST reduces the communication overhead as compared to both synchronous and asynchronous Gossip there is no need for exchanging models among all nodes after every model update. DIGEST improves the convergence time as compared to manomm-walk as it eliminates idle times at nodes by employing local-SGD updates. To summarize, DIGEST gets the best of both Gossip and random-walk algo- rithms by exploiting local-SGD. Furthermore, DIGEST is designed to support both iid and non-iid data distributed over nodes.
DIGEST supports multiple streams of global model updates. For example, node may transmit its semi-global model to node 2 while node 3 transmits its semi-global model to node illustrated in Fig. 3 We use the term semi-global model in the multi-stream DIGEST as the global model can be obtained only after semi-global models are aggregated. The motivation behind introducing multiple streams is to further improve the convergence time as compared to the single stream DI- GEST. We note that the communication overhead increases when the number of streams increases, and there is nice convergence and communication overhead tread-off.
Convergence analysis of DIGEST. We analyze the convergence of single- and multi-stream DI- GEST, and prove that both algorithms approach the optimal solution asymptotically, Our con- vergence proof is novel in the sense that it removes symmetric communication capabilities among nodes, which is needed for the Gossip convergence proof (Koloskova al., 2020). Furthermore, our convergence proof holds for any (i) any non-iid data distribution across nodes, (ii) any (and possibly time-vary varying) network topology as long as the underlying graph is connected.
Evaluation of DIGEST. We evaluate the performance of DIGEST for (i) two data sets; w&a (Platt 1999) and MNIST (eecun et al., 1998). (ii) iid and non-iid data, and (iii) network topologies with different number of nodes. The simulation results confirm that the communication cost of DIGEST is low as compared to the baselines, and it has nice convergence properties; i.e., its convergence time is better than or comparable to the baselines.
RELATED WORK
Decentralized optimization has been studied at least since Tsitsiklss (1984). Decentralized optimization algorithms are designed, where nodes interact with their neighbors to solve an optimization problem Nedic & Ozdaglar | (2009)); Chen & Sayed (2012); Duchi et al. (2012b). Despite their potential, these algorithms suffer from bias in non-iid data (Yuan) et al., 2016), and they require synchronization and orchestration among nodes, which is costly in terms of communication overhead.
stream
node
node 1
node 4
node 5
node 7
node 3
node
stream 2
Decentralized algorithms based on Gossip usually involve a mixing step where nodes compute their new models by mixing their own and neighbors' models Koloskova et al. 22000); Scaman et al. 2019 Xiao & Boyd (203)). However, this is costly in terms communication as every node requires O(deg( (G) data exchange for every model update. Also, some existing Fossip-basee approaches require symmetrical data exchanges, i.e., if node sends to node j, then node j should be able to receive from node i, (Koloskova al. 22200] Lian et al., 2018). Our goal in this paper to reduce the communication cost in decentralized learning for any network topology and data distribution.
Figure 3: Example multi-stream DIGEST.
is discussed in Giaretta & Girdzijauskas (2019) that existing Gossip-based algorithms usually have strong assumptions on data distribution, the communication power of the nodes, and the connectiv- ity among them. Violation of these assumptions may lead to slow convergence and/or bias in the final model Giaretta & Girdzijauskas (2019). To address such problems, Gossip SGD with periodic global averaging is proposed in Chen et al. (202I), a method for accelerating convergence on large and sparse networks by adding periodic global averaging into Gossip. For scenarios like wireless
3

---

Under review as a conference paper at ICLR 2023
sensor networks, where global averaging is prohibitively expensive, it is suggested to multiple Gossip communication steps in succession once in a while with no computations in between (Be- rahas et al. 2019). An asynchronous decentralized parallel stochastic gradient descent algorithm is designed in Lian et al. 2018), where nodes do not wait for all other nodes and only communicate in decentralized manner. However, it has the same limitations of Gossip-based algorithms as it uses a similar model exchange policy as well as gradient staleness.
A random walk-based decentralized learning is proposed in Ayache & Rouayheb (2021), which is similar to work on random walk data sampling for stochastic gradient descent, e.g., (Sun et al, 2018 Needell et al., 2014). Reducing the global averaging rounds as compared Gossip- mechanisms is considered in Sppridonoff et al. (2021) by one-shot averaging. However, the global averaging rounds require long synchronization duration for large networks, which increases the convergence time. Also, only iid data is considered [Spiridonoff et al. (2021). As compared to this line of work, DIGEST designs a communication efficient decentralized learning without hurting convergence rate for both iid and non-iid data.
3 DESIGN OF DIGEST
3.1 PRELIMINARIES
Network Topology. We model the underlying network topology with directed graph G (V, E), where V is the set of vertices (nodes) and & is the set of directed edges. The vertex set contains V nodes, ie.. |V| V. and |-] shows the size of the set. The computing capabilities of nodes are arbitrary and heterogeneous. If node is connected to node j through communication link and can transmit data, then link ($..) is in the edge set, ie.. (i &. The set of the nodes that node is connected to and can transmit data is called the neighbors node i, and the neighbor set of node i denoted by Ng. We do not make any assumptions about the behavior of the communication links; there can be an arbitrary, but finite amount of delay over the links.
Data. We consider a setup where nodes have access to a subset of data samples D. Each node has local dataset De., where D, |D,, is the size of the local dataset and >V ===1 Da. The distribution of data across nodes is not identical and independently distributed (non-iid).
Stochastic Optimization. We assume that the nodes in the network jointly minimize a d- dimensional function f R + R. The goal of the nodes is to converge on model x*, which mini-
[(() == + DD fi(x)]. where fx(x): : Rd + IR is the loss function of model x associated with the data sample i. The optimum solu- tion is denoted by f" The loss function on local dataset D,, at node v (")x = D. SiE
mizes the empirical loss over D samples, i.e., x == arg minlee
We design DIGEST to solve x".
3.2 SINGLE-STREAM DIGEST
DIGEST has two functionalities; (i) local model update each node, and (ii) global model update and exchange among nodes. Next, we will first provide an overview of these functionalities and then provide detailed descriptions of DIGEST algorithms.
3.2. OVERVIEW
Local Model Update. We assume that the time is slotted, and at each slot/iteration, a local model is updated. However, a calculation of gradient may take more than one slot, vary over time, or not fit into slot boundaries. Thus, at each iteration i, any gradients which have been delayed up to iteration and not used in previous local updates are used to update the local model. We note that time slots across nodes do not need to be synchronized in DIGEST as each node can have its own iteration sequence and update local and global models over its own sequence. The only assumption we make is that the slot sizes are the same across nodes, which can be decided priori.
Let consider that L3 {1,' Jost<T is the set of the delayed gradient calculations at node v, where I/ shows that the local-SGD update of iteration / is delayed until iteration 17- For instance, Ey L means that the local-SGI of iteration t' is lagged behind and performed in iteration t 2 t'. Then, we define ui' = {t' 45 = t} to show all the updates completed at iteration t in node v. If we consider that there is no global update at node e, the local model is updated as x = X Exew: n/ V fig (x"), where 7) is the learning rate, i is a sample uniformly chosen
from D, in iteration z, and V sag (x") is the gradient. However, there may be global model updates
4

---

Under review as a conference paper at ICLR 2023
at node t, f.e. node v could receive global model update from one of its neighbors at iteration t. Such a global model reception should be reflected in local model updates, which we discuss next.
Global Model Update and Exchange. Let x, be the global model that is being transferred from from one node to another at time slot t. If node v receives the global model x, from one of its neighbors, global model update indicator se is set 8 = 1. Otherwise, i.e, when node does not receive the global model from its neighbors, the indicator is set to 8 =.
If s² 0, then node updates its model locally according to the update mechanism presented eaerlier in the "Local Model Update" section. If 35 = 1, i.e., when global model is received by node from of its neighbors, then the global model should be incorporated in the calculations. DIGEST sets the local model to the global model when there is global model update as follows.
x X,
Exeur
ne V fey (x")
if 0
x
if =
The global model is updated as
Dr D (xi-1-
x = x +
Σ To fig x x =EM7_1
(2)
where x is the global model received by node v at slot t- 1. The global model, ie.. X; is updated by using x as well as the local updates of node We use Tf to denote the last time slot up to t, when node v's model was updated with the global model, i.e, T = max(t' I' S t, = 1}. The equivalent of ( is & X E E ExENy no Vig (x"), where Xo is the initial model. As seen, the global model is updated across all nodes by taking into account all delayed gradient D.
calculations. We use D' ratio to give more weight to the gradients with larger data sets. Now that provided overview of DIGEST, we provide details on how DIGEST algorithms operate next.
3.2.2 ALGORITHM DESIGN
DIGEST is comprised of two algorithms; (i) local and global model update at node and (ii) sending global model from a node to its neighbor.
Algorithm 1 Local and global model update of DIGEST at node e E V.
1: Initialization: x = Xo, x",
Xo. Xy = visited = {,
pre node v, ST {0]o<esT, $
Local and Global Model Up- date. The local and global model update of DIGEST is pre-
2: for / in 0, .... T --1 do
3: Sample i uniformly from D,..
4: Compute the gradient V fc (x").
sented in Alg. | Every node 5: x"+ = - - Th V fay (x") Local model update.
keeps its local model x as well
6:
if Received new message from another node then
as x" which is copy of the local model in the latest global model update node X, is the global model. All of these mod- els are initialized with the same initial model Xp- We note that only one of the nodes, let say node vo, has the global model x; the start of the algorithm.
7:
(Ke, visited, pre pre. node, 0) + message.
8:
8141 =
9:
if 1 = then
10:
_ X, + D (x -xx+1-xx,)
11:
x-1 = X141 D Local model is updated using global
model.
12:
x" = =xx1
13:
if mod (1, H) 0 visited + V then Send message = (X++1, visited, pre_node, 0)
14:
We define visited as the set of nodes that are recently visited for the global model updates. It initialized as an empty set at node v. We define period of time, during which all the nodes in V are visited at least once, synchronization round. During a synchronization round, all nodes update their local models with a global model as they are visited at least once. More details regarding the visited set will be provided as part of Alg.
to a neighbor node by calling Alg. else
15:
16:
Pause global model update and exchange until mod (t, H) = 0 holds.
S
5

---

Under review as a conference paper at ICLR 2023
The node that node receives the global model from is defined by pre_node, where its initial value set to U as there is no previous node at the start. The set of global model update indicators, i.e, empty set, where T is the number of slots that Alg. rums. Assuming that to is the node where the global model update starts, $1 set to 1, i.e., s1
ST. = {s] JociST is initialized
At every iteration node first gets one data sample from the local dataset randomly (line 3), and com- putes a stochastic local gradient (line 4) based on the selected data sample and the current model at node v. i.e., x Then, node v uses all the gradi- ents whose computations are delayed until iteration f, and that are not used in local model updates so far for the local model update (line 5).
Algorithm 2 Sending global model from node E V. Input: message = (K++1, visited, pre pre_node, r)
1: if visited = =V then
visited = O
3: if o & visiled then
4: visiled visiled {a}
5: p" prre_node
6: C = E 1 $ visited)
7: if + then
8: select v' randomly from C.
If node receives "message" from one of its neighbors at slot t, then should update the global model. Each message contains information on the global model &t, the set of visited nodes, i.e., visited, the id of the node that sends this message to node e.g, v', and a parameter which is always set in single-stream DIGEST, but may take different values for multi-stream DIGEST. After the message is extracted (line 7), global model update indicator is set to (line 8), and global model updated (lines 10 12). In particular, the global model is updated using the most recent local model of node (line 10). The local model is updated with the global model (line 11). The current local model is stored at node and will be used in the next global update (line 12).
9: Send message = (R++1, visited, v, r)) to node v/.
10: else
11: Send message = (x++1, visiled, v, r) to node p".
If the global model is updated at node v, L.e., if 8 node v creates message and sends it to one of its neighbors if (i) visited * V: when not all nodes are visited in the current synchronization round; mod (t. H) 0: this is an indi- cator of the start of new syn- chronization round, which hap- pens periodically every / it- erations. In other words, global model synchronization continues until all nodes in V are visited. Then, global model update paused until new synchroniza- tion round (satisfied by line 16), which starts at every H iteration. We will describe how H should be selected later in the paper as part of our convergence analysis and evaluations. If one of the con- ditions in line 13 is satisfied, then node v sends the global model to one of its neighbors by calling Alg.
Algorithm DIGEST on node V with R synchronization streams.
1, then
1: Initialization: x = Xo, x" = Xo. queue ()-
2: for r in 0, .... R do
3: Xolr]
8-1 [r] = Xo. visiled[r] pre_node(r] = U, [r) (0)ociTT [r
0.
(ii)
4: for in
T T 5: Sample i uniformly from D...
do
6: Start computing the gradient V frr (x²)).
7:
x
x Σ=eap 1/2 Vig
8:
if queue + () then
9:
for any message in queue do
(x:[r), visited(y), pre node(r),r) message
11:
$++10 [r] =
Remove message from queue
13:
for r in 0, .... R do
14:
if s [r]
then
8 [r] [x D.
D (x. x") x = x= + (x xr))
16:
> Local
model update.
17:
x" ====x²=_ x²_
Last updated model at node
18:
|-1/r] = x++1[r] [r] > Last updated model at node
corresponding to stream r mod (1, H) = 0 or visited(r) * then Send message - visited(r) pre_node[r] , r to neighboring node by calling Alg else
19:
20:
Sending Global Model. Alg. describes the logic of DIGEST at node v for sending a global model to a neighboring node. Alg. 2 implements Depth-First
21:
22:
[1 =

---

Under review as a conference paper at ICLR 2023
Search (DFS) traverse all the nodes in the network in a synchronization round. If all nodes visited, i.e. at the end of a synchronization round, visited is set to an empty set (line 2). If is not visited before in this synchronization round, it is added to visited (line 4) and its parent node p" is set to pre node (line 5). The parent node is the node that node e receives the global model from for the first time in this synchronization round. C is set of nodes that node can possibly transmit. It includes all of the neighboring nodes which are not in the visited set. If C' is not empty, one of its elements o' chosen randomly (line 8) and message including the global model is transmitted to node v' from node v. If C is empty, ie., all the neighbors of node e are visited in the current synchronization round, the message sent to the parent of node v (p") (line 11). We note that all the nodes are visited in the network, Alg. I pauses global model update (line 16), and Alg. 2 is not called. We also add that Alg. and Alg. operate simultaneously; one does not need to stop and wait for the other as also illustrated in Fig. 1d
3.3 MULTI-STREAM DIGEST
The extended version of the local and global model update algorithm of DIGEST supporting multiple streams is summarized in Alg. 3 The following are the differences between Algs. and
There are multiple semi-global models in different streams, i.e., xx[r] corresponds to the semi-global model in stream r out of R streams. There are R models stored in each node, i.e., x x-1 [r] to represent the remi-global model corresponding to the last synchronization of stream node v. We define visiled[r]. pre_node(r), and [r] for each stream r.
Each node has queue to store all the messages that a node receives from its neighbors. It is initialized as an empty queue at the start. Whenever node e receives a message from one of its messages related to different
neighbors, it is added in the queue. Each node can receive up streams, so the size of the queue is R. In each message there is a stream index r (line 10).
Node e extracts all the messages in its queue (line 9-12). Then, it updates its semi-global and local models as in Alg. [ 1. The semi-global models are accumulated in the local models and add up to the global model. In particular, the local model is updated using semi-ght remi-global models (line 16), and just one semi semi-global models is updated for every spesific local update (line 15).
4 CONVERGENCE ANALYSIS OF DIGEST
We use the following assumptions for the convergengence analysis of DIGEST.
1. Smooth local loss. The function l is continuously differentiable and its gradient is L-Lipschitz for 1 S v S V,ie,, ie., [ (y) - f (x)]l S Llly - x||, Vx,y E Rdd.
2. Convexity. The function f is p-strongly convex, i.e., Vx.y Rd f(y) 2 f(x) (Vf(x).y
x) + fll [|l]-
3. Bounded local variance. The variance of the stochastic gradient is bounded for all nodes, i.e.,
0 < L T, S < V, Eay (1 (x(((()))1 < o².
Bounded second moment, The expected squared norm of the stochastic gradient is bounded, V
i.e., Egg (x,))l < G², 0 t < T.
5. Bounded lag. We assume bounded lag, i.e., max t E, O
Bounded synchronization interval. We assume that the interval between two subsequent syn- chronizations is bounded, i.., gap(S)) < H1 1 < v < V, where gap(S?) shows the maximum of the gap between two subsequent is in Sy.
Theorem 4.1 (Asymptotic result for single-stream DIGEST). Let assumptions 7 hold, and the learning rate be 1i- p(a+t) with a > max{ 16L H + E, 2}. The convergence rate of single- stream DIGEST is
E f(rrr ft 20 1 H+E
HH + E)3 ) x1
1po² +0
(3)
T
T3
V
Vp(H E)²
In(T 11 + E) G)
T
where XT
T 2 Et= Duwrx Wt = (a+ + 1)2, ST -ET- Wr, and P EV (Bz)2.
DST
Remark. The convergence rate to the optimum value f is (H)
and asymp- is data concentration coefficient that can take
totically approaches to zero, where p
7

---

Under review as a conference paper at ICLR 2023
values between & 1 p < 1. If all the nodes have the same amount of data, i.e., p v. then linear speedup in the convergence rate O( (pT) is observed. On the other hand, in the extreme scenario that p 1, where one node has all the data, the speedup is (
Sketch of Proof of Theorem 4.1 (The details of the proof is provided in the supplementary mate- rial.) We define virtual sequence (20 X,
V f-- Do fiy (x") following a similar idea in Stich 2019). We also define g: = EV= D.
==1 D. f
D
g7 = D. slot in all nodes. It can be seen that g: Er, gt, and g? is the real direction of optimal convergence
D' V (x.)).
(1] -...) denote the data samples selected randomly during time
every step. The virtual direction is updated as Xt+1 X 7.... We first illustrate how the virtual
sequence (x 320 approaches to the optimal solution in Lemma 4.2
Lemma 4.2. If assumptions
2 hold, and ' S I then E xx x 122 S (1+
5m) g + ((1 + 2n) + E +
jume) E |x+ - x 122 2 (E f(x+) - 8*) + 2m E E
21/ )1??)
Σ
V
D. E x2
-=
Lemma 4.2 indicates how the convergence criteria; E fx,) f is related E x E|
x 1|2 and
x 2_ which can be handled with some method like telescopic sum. E f|g l1 is related
to local variance and bounded Lemma 4.3 E. ||x, x I| shows the deviation between virtual and actual sequences and we find upper- bound for this term in Lemma 4.4
Lemma 4.3 (Bounding variance). If assumptions holds, then llg - -: S po²
Lemma 4.4 (Bounding deviation). If asssumptions hold, and n) S for SIST-1,
1 S v < V, then E D2 D X; - xx113 < 64V pn (H + E)
Now, we focus on the convergence of multi-stream DIGEST. We make the following assumptions.
7. Strongly bounded synchronization interval. We assume that the interval between two sub- sequent synchronizations for all streams are bounded, i.e., [ap(S)(r]) S H. S v < V. 1 S R. The duration between two subsequent synchronizations in node by any two H + 5 where 6 is constant to handle special cases where the R duration is longer due an uneven arrangement of streams, Note that Vosigi is defined as logical or of all A&s element-wise.
streams is gap( (r)) I
8. Efficient covering. We assume that LE Σ/= ( S cp. 0 where is constant. We define (t) ju' = 1, < t' < as the list of nodes that are visited by stream r after the last visit of this stream at node v until (repeated nodes may appear in the list).
Theorem 4.5 (Asymptotic result for multi-strean DIGEST), Let assumptions 75 and 7 8
hold,
and the learning rate is 1/-- m(a+t) with a > maxx 162 H + E, 2]. The convergence rate of both multi-stream DIGEST (hence single-stream DIGEST as special case) is
H+E T )oo + 0
+H}
Ef((r) f f
)|1xo - 12
(4)
T
TB
+ +0
p( 188+E)(( + elthmaz)
In(T + H F.
))) T
(1+
where hynr is the maximum value of h(u, v). which defined as the expected number of steps for random walk between and u. The details of the proof is provided in the supplementary material.
Remark. The convergence rate the optimum value f with R streams is if <
TR2 Ol1 Voelthmas and asymptotically approaches to zero. Note that if eRhmaa < O(V) we get
H H < O(v TTe that provides a linear improvement in R, otherwise we get improvement on the order of VR.
8

---

Under review as a conference paper at ICLR 2023
Syc per-roarllin
021
6.5
3.20
031
Jundor
SM www. 11:22
1 w.dscolepraa
0.9
3:30
035
0.5
3.20
024
1000
202
200
230
(a) 10-nodes/ / iid balanced
(b) 10-nodes / non-iid/ unbalanced (c) no0-nodes non-iid unbalanced
Figure Convergence results for w&a dataset in terms of global loss over wall-clock time.
5 EVALUATION OF DIGEST
We evaluate DIGEST in terms of convergence time as well as communication cost as compared to
the following baselines; (i) One link-Gossip (Koloskova al., 2020): At every slot, only di-
rected communication link is activated randomly, and a model is sent from sender to a receiver.
The receiver's model is updated with the received model: (ii) Uniform Random-Walk (URW) (Ay-
ache & Rouayheb 2021): This is random walk-based learning algorithm described in Fig. Ic (1lI
Real Avg-Gossip Gossip- PGA (Chen et al.] 202T): It adds Periodic Global Averaging (PGA) Gossip. To perform one global averaging step, the whole graph is traversed twice, to get all the models first and returning the averaged model. P is used to show the period, i.e., the global averaging happens every
P iterations; (iv) M Multi-Gossip-PGG PeesippPGAAaaa Berahas et al. (2019): One global averaging step is imitated via M multiple sequential Gossip steps; (v) Async-Gossip Lian et al. (2018)
examine the convergence mance of logistic regression, i.e. f(x) DI EE CrosEEntopyysottmxxxxaaa 6t) + [
We
perfor-
2645 50.0 1ha0
I
where a; E R&, and b; are the feature and label of the data sample i. The regularization parameter is consid- ered X = 2. We consider two network topologies, Erdös-Rényí graph of = 10 and V = 100 nodes with 0.3 the probability of connectivity. We use datasets w8a (Platt 1999) and MNIST (Lecun et al. 1998).
0:41
We use two different data distribution over nodes: (i) iid-balanced, and (ii) non-idd-unbalanced. In iid-balanced case, data set is shuffled and equally divided over differ- ent nodes. In ples based on their labels. Then, we follow geomet- ric series as the size of local datasets. For each run, we measure the global loss fxx during the optimization. We calculate the loss for different weighted averages of the models over iterations: the last model, the uniform av- erage, the average with linear weights, and the average with quadratic weights (such as in Theorem 4.Jp. Finally, the minimum is reported. Practically speaking, the final model could be adequate, but an auxiliary sequence might simply track the weighted average of the iterations, with- out having to store models in all previous iterations; some examples can be seen in Table I of (Stich) 2019).
we first sort data sam-
(a) Global loss
208 Hestt
Ago dasia
(b) Communication overhead
We run the optimization using the plots of convergence over time, we assume that each iteration of Local SGD takes millisecond. The commu- nication delay between every two neighbors is assumed to have exponential distribution where its average is ran- domly chosen from 0 to 10 milliseconds. The numeri- cal experiments were run on Ubuntu 20.04 using 36 Intel
10+1/1000 To derive
Figure 5: Convergence results and com- munication overhead for MNIST dataset in 100-nodes / non-iid / unbalanced set- ting with multiple streams.
Core 19-80E processors. For each experiment, we repeat 50 times and present the error bars

---

Under review as a conference paper at ICLR 2023
associated with the randomness of the optimization. In every figure, we include the average and standard deviation error bar.
Fig. 4 shows the convergence behavior of w&a dataset in 10-nodes and 100-nodes topologies. We see that PGA algorithms do not perform well such an environment, where global averaging and several Gossip steps take long time complete. Sync-Gossipy with H does not perform well as performing Gossip communications every iteration increases communication cost, hence conver- gence time. This observation we execute more local-SGDs by raising H to 200 in Syne-Gossip. One link-Gossip and and URW have similar performance. This observation suggests that for w8a. performing simultaneous compu- tations in all nodes (as in One link (nk-Gosspp) without a proper communication does not improve the convergence speed. DIGEST, Sync-Gossip with H = 200, and Asyne-Gove Gossip have similar perfor- mance in Fig. On the other hand, we observe that Gossip based algorithms and URW are suffering some slow convergence due to the data distribution in Figs, 4b. 4c while DIGEST performs better as it (i) supports non-iid data, and (ii) less communication overhead (so better convergence time in wall-clock time), which is amplified in Fig. 4c where there are more nodes.
supported by the fact that the results are significantly better when
Fig. 5a demonstrates the convergence time for non-iid-unbalanced data distribution over 100-node topology with MNIST dataset for multi-stream DIGEST. Using the multi-stream DIGEST Alg. have simulated the results for different values of R, i.e., number of streams in the network. Note that even after increasing number of streams, the overall communication overhead still low as illustrated in Fig. 5b thanks to local-SGD and periodic global model updates of DIGEST.
6 CONCLUSION
We designed a fast and communication-efficeeit decentralized learning mechanism; DIGEST by particularly focusing on stochastic gradient descent (SGD). We designed single- and multi-stream DIGEST to exploit the convergence rate and communication overhead tradeoff. We analyzed the convergence of single- and multi-stream DIGEST, and proved that both algorithms approach to the optimal solution asymptotically. The simulation results confirms that the communication cost of DIGEST is low as compared to the baselines, and has nice convergence properties; i.e. its convergence time is better than or comparable to the baselines.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Tomer Avidor and Nadav Tal-Israel. Locally asynchronous stochastic gradient descent for decen- tralised deep learning. ArXiv, abs/2203. 13085, 2022.
Ghadir Ayache and Salim El Rouayheb. Private weighted random walk stochastic gradient descent. IEEE Journal on Selected Areas Information Theory, 2(1):452 463, 2021, doi: 10. 109/ISAIT. 2051.305
T. Aysal, Mehmet E. Yildiz, A. Sarwate, and A. Scaglione. Broadcast gossip algorithms for consen- sus. IEEE Transactions Signal Processing, 57:2748- 2009.
Albert S. Berahas, Raghu Bollapragada, Nitish Shirish Keskar, and Ermin Wei. Balancing commu- nication and computation in distributed optimization. IEEE Transactions on Automatic Control, 64(8):3141-3155 2019. doi: 10.1 10.119//AA.222112280007
Dimitri P. Bertsekas. A new class of incremental gradient methods for least squares problems. SIAM J. Optim, 7:913-926, 1996.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-255 -5300, 2006a. doi: 10. 1..11099T..2000884451.
Stephen P. Boyd, Arpita Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory,
2006b.
Jianshu Chen and Ali H. Sayed. Diffusion adaptation strategies for distributed optimization and learning over networks. IEEE Transactions on Signal Processing, 60(8):4289-4305 2012. doi: 10.1109//SP.2012221998
Yiming Chen, K. Yuan, Yingya Zhang, Pan Pan, Yinghui Xu, and Wotao Yin. Accelerating gossip sgd with periodic global averaging. In ICML, 2021.
John C. Duchi, A. Agarwal, and M. Wainwright. Dual averaging for distributed optimization: Con- vergence analysis and network scaling. IEEE Transactions Automatic Control, 57:592-606, 2012a.
John C. Duchi, Alekh Agarwal, and Martin Wainwright, Dual averaging for distributed optimiza- tion: Convergence analysis and network scaling. IEEE Transactions on Automatic Control, 57(3): 592-606, 2012b. doi: 10. 10000TAA.2211111110011
Sanghamitra Dutta, Gauri Joshi, Soumyadip Ghosh, Parijat Dube, and Priya Nagpurkar. Slow and stale gradients can win the race. IEEE Journal on Selected Areas in Information Theory, 2:1012- 1024, 2021.
L. Giaretta and S. Girdzijauskas. Gossip learning: Off the beaten path. In 2019 IEEE Inter- national Conference on Big Data (Big Data), pp. 1117-1124, Los Alamitos, CA, USA, dec URL https: 2019. IEEE Computer Society. doi: 10.1 (tt/:///igDuu4790000099000000 20199. 9206216 //doi.
Jayavardhana Gubbi, Rajkumar Buyya, Slaven Marusic, and Marimuthu Palaniswami. Internet of things (iot): A vision, architectural elements, and future directions. Future generation computer systems,
2013.
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael G. L. D'Oliveira, Hubert Eichner, Salim El Rouayheb. David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang Hc, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramer, 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. Foundations and Trends in Machine Learning. 14(1-2): 1-210, 2021.
11

---

Under review as a conference paper at ICLR 2023
David Kempe, Alin Dobra, and Johannes Gehrke Gossip-based computation of aggregate informa- tion. In Proceedings of the 44th Anmual IEEE Symposium on Foundations of Computer Science, FOCS '03, pp. 482, USA, 2003. IEEE Computer Society. ISBN 0769520405.
Anastasia Koloskova, S. Stich, and M. Jaggi. Decentralized stochastic optimization and gossip algorithms with compressed communication. ArXiv, abs/1902.00340, 2019.
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. A unified theory of decentralized SGD with changing topology and local updates. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, vol- ume 1 119 of Proceedings of Muchine Leurning Revearch, pp. 5381-5393, PMLR, 13-18 Jul 2020. URL https: / http:///pccceedeeeoooooo
mlm presss. 11 11 ko
http///11//oooooooooooo www.oolokkaaaaa html
Jakub Konecný, H. B. McMahan, and Daniel Ramage. Federated optimization: Distributed opti- mization beyond the datacenter. ArXiv,
2015.
Y. Lecun, L.. Bottou, Y. Bengio, and P. Haffner. Gradient- based learning applied to document recog- nition. Proceedings of the IEEE, 86( 1):2788-2324, 1998. doi: 10. (0.1109/5.7269.
He Li, Kaoru Ota, and Mianxiong Dong. Learning iot in edge: Deep learning for the internet of things with edge computing. IEEE network, 32(1 (2(1):96-101, 2018a.
Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. Federated learning: Challenges, methods, and future directions. IEEE Signal Processing Magazine, 37(3):50-60, 2020a. doi:
10.11099MSP.2222229754444
Xiang Li. Kaixuan Huang, Wenhao Yang. Shusen Wang. and Zhihua Zhang. On the convergence of fedavg on non-iid data. ArXiv, 0tbs/1907.02189) 2020b.
Youjie Li, Mingchao Yu, Songze Li, Amir Salman Avestimehr, Nam Sung Kim, and Alexander G. Schwing. Pipe-sgd: A decentralized pipelined sgd framework for distributed deep net training. ArXiv, abs/1811 118811.00 103619, 2018b.
Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu. Asynchronous decentralized parallel stochastic gradient descent. In Jennifer G. Dy and Andreas Krause (eds.), ICML, volume 80 of Proceedings of Machine Learning Research, pp. 3049-3058. PMLR, 2018
Tao Lin, Sebastian U. Stich, and Martin Jaggi. Don't use large Abs/1808.07211 2020.
use local sgd. ArXiv,
H. B. McMahan, Fider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiieent learning of deep networks from decentralized data. In AISTATS, 2017.
H. Brendan McMahan, Eider Moore, Daniel Ramage, and Blaise Agüera y Arcas. Federated Learn ing of Deep Networks using Model Averaging. CoRR, abs/1602.055629, 2016.
A. Nedic and A. Ozdaglar. Distributed subgradient methods for multi-agent optimization. IEEE Transactions on Automatic Control, 54:48-61, 2009a.
Angelia Nedic and Asuman Ozdaglar. Distributed subgradient methods for multi-agent optimiza- tion. IEEE Transactions on Automatic Control, 54(1):48 61, 2009b. doi: 10. 10.0////AA.. 2009515.
Deanna Needell, Nathan Srebro, and Rachel Ward. Stochastic gradient descent, weighted sampling, and the randomized kaezmarz algorithm. In Proceedings of the 27th International Conference on Neural Information Processing Systems Volume 1, NIPS' 14, pp. 1017-1025, Cambridge, MA, USA, 2014. MIT Press.
John C. Platt. Fast Training of Support Vector Machines Using Sequential Minimal Optimization, pp. 185-208. MIT Press, Cambridge, MA, USA, 1999. ISBN 0262194163,
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal convergence rates for convex distributed optimization in networks. Journal of Machine Learning Research, 20(159):1-31, 2019. URL h wwwp:oogppppppp//////e. 9- 543. .html
12

---

Under review as a conference paper at ICLR 2023
Artin Spiridonoff, Alexander Olshevsky, and Ioannis Paschalidis. Communication-effitni SGD: From local SGD to one-shot averaging. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021. URL https://
openrevi eww www.rrvview.ne/foruuteeo
Sebastian U. Stich. Local sgd converges fast and communicates little. ArXiv, wwwp:absss1...0. 000.0000500777 2019.
Tao Sun, Yuejiao Sun, and Wotao Yin. On markov chain gradient descent. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 9918 89927, Red Hook, NY, USA, 2018. Curran Associates Inc.
John N. Tsitsiklis. Problems in decentralized decision making and computation. PhD thesis, Mas- sachusetts Institute of Technology, 1984.
Jianyu Wang and Gauri Joshi. Cooperative sgd: A unified framework for the design and analysis of local-update sgd algorithms. Journal of Machine Learning Research, 22(213):1-50, 2021. URL
org/ papers wtv.rs//v2222// v22 / 20 14 7..7.00 mt
Lin Xiao and Stephen P. Boyd. Fast linear iterations for distributed averaging. 42nd IEEE Inter- national Conference on Decision and Control (IEEE Cat. No.03CH37475), 5:4997-5002 Vol.5,
2003.
Kun Yuan, Qing Ling, and Wotao Yin. On the convergence of decentralized gradient descent. SIAM Journal on Optimization, 165)):18351184, 2016. doi: 10. 3399437793 URL https::/ doi ww..org/1..0 1137 111111111111011111
13

---

Under review as a conference paper at ICLR 2023
7 APPENDIX: NOTATION TABLE AND PROOF OF THEOREMS 4. AND 4.5
7.1 NOTATIONS
G
(V,E)
Graph representing the network
Number of nodes
D
The whole dataset in the network with size D
Do
Subset of DD at node u with size D.
f((x)
Loss function of model x associated with the data sample i
[(x)
Global loss function of model x
('X
Local loss function of model x at node t
f
minxeg2 fx)
x"
arg ge [xx
X
Initial model
7
Learning rate at iteration t
Completion time of local-SGD update started at
L7
Set of {4; jogt<T
x,
Local model in node v a
$8
Binary variable that shows if node receives the global model at in
single-stream DIGEST
Sy.
Set of {2] JoCTTT
Binary variable that shows id node receives the semi-global model from stream r in multi-stream DIGEST
[h[rl
{>"[r]o<rsT
visiled
Set of nodes that are visited for the global model update in the most recent synchronization round for single-stream DIGEST
visitedrr
Set of nodes that are visited for the semi-global model update in the most
recent synchronization round in stream for multi-stream DIGEST
X,
The global model received by node f single-stream DIGEST The semi-global model received by node t from stream in multi-stream DIGEST
pre_node
The node that node v receives the global model from in single-stream DIGEST
pre_node
The node that node e receives the semi-global model from in stream r for multi-stream DIGEST
The node that node e receives the (semi-)globa model from for the first time in the current synchronization round
h(u,0) 1))
The expected number of steps for the random walk between and
hmaz
Maximum value of h( uu, v) over all ordered pairs nodes
Constant that bounds the intervals between two subsequent visits of node by all streams
c
Constant that determines how efficiently the multiple streams are covering the whole network
(1)
List of nodes that stream r visits after the last visit of node until
7.2 SINGLE-STREAM DIGEST
Motivated by Stich 2019). virtual sequence (xch20 is defined as follows.
1-1 D. ΣΣ Pi
X0
(5)
We do not need calculate this sequence in the algorithm explicitly and it is only used for the sake of the analysis. We also define
D V faz (x(),
D V (xx),
D v
g:
B:
g
(6)
D
D
D
14

---

Under review as a conference paper at ICLR 2023
where fxx. fx() are global loss function and local loss function in node v, respectively.
Let us introduce i, = (it..... } to denote the data samples selected randomly during time slot in all nodes. Then, observe that g: Ei, ge. gi is the real true direction to go in opposite of in each step. We have X = X 7/gt.
First, we illustrate how the virtual sequence, {&t he2. approaches to the optimal in Lemma 1, and 2. Second, we depict in Lemma 3 that there is a little deviation from the virtual sequence in the actual iterates, x Finally, the convergence rate is proved in
7.2.1
Lemma 7.1. if is L-smooth and u-strongly convex and 1p:
S II' then
E xx+1 - x 112 < (1 + # 5リ
Tte (1 - pm)p)) E. 1|x - x 1|
2
The (EE (xx) -
(²)
(7)
5
2
V
+ 2n E lgg - 1 + ((1 + 1
n2) L + (8)
m== + 2n7 )4L²
Σ
Do E |x - x
5
D
Proof. We have
|x++1 x12 112 = ||x, 1/.. xx"1 = ||x 1)(g: x' -nigi + nig;l 1|
(8)
=|x: 17:8i" x=1
=11 + n/ lg: g. g: g7 2 + 23te (Zz- x :m.ii gi: - -i)
(9)
|x "igg"" x²1 + 112++22200 (llg: g + llg: gt 11²) + 27, (xt- -x" -7... g. gg), (10)
where (10 is based on the following inequality.
a 2 S
|a:11
(11)
Then we apply expectation get Eig..... ||xc+1 x 112 Based the law of total expectation,
for every two random variables a, B and a function y, Ea v(a) = Eg Ea (a) Considering a i0...,, èt and io, ..., 4-1, we get that
E Ei (Xe- - x" m.... gi -gi) = Eio...fe_ Big.....e - -x" - -mgi. gi - gi)
4 1]
(12)
Esg...te (x: - x" - mngi: gi E,, gi)
(13)
Eio...is (x, x" 11:8/ gi E,, gi)
(14)
Eig....i (xe X migi gg. gt).
(15)
In (13,, we used the fact that once we know io. ..., 4-11, the value of x", S u S V, and therefore
x, and gž are not random any more. From now on, we drop the subscript io ..., d for the ease of notation. Thus,
E R
x" 112
<(1
+
To
EX - mg. - x"1 12 + 20 Eg - -gll
(16)
5
5
+
2n
E - 13
/
where we used 15 in
10 and the fact that for x > 0.
b)a - A||a|| + |b61
(17)
We obtain
||x;- n:g!" -xx1' = =||x,- x²1 + 1/2 ||g. 1|2 - 21 (xx x", x²)
(18)
Dr
= || - x 112 + n2² ||g:
- -21
(x, - x + x; - x", fx({)))
(19)
D
1=1
= 1x - x" 1|2 + n
V
De
| (x - 2m
Σ
V
De
(x) - x", vf(xi))
(20)
D
D
w=1
w=1
V
Dr
2n
(x+ xx vf(x")),
15

---

Under review as a conference paper at ICLR 2023
Where in 20 we have used the convexity of II.112 that
V
D2
r²
gi
v
(21)
D
0=1
By L-smoothness we have
[V < 2T([(x)) - 1*)
(22)
So we can rewrite the second term in (20p as
V Σ
Do
- ff)
De
(23)
D
D
ju-strong convexity provides us with
(x)
- f³)
11 | x111
(24)
Following 17 to bound the last term in 20 we have
2(x, x", Vf(x)))
< 2L| - x + [V}(x,) - V)(('))1
(25)
2I.
< 2T - (f(x)) f*),
(26)
where 22 is used in (66).
We obtain the following result by applying these three estimates to 20
D
| n:87
x22 S xx x11 27/ Σ
[ x!'1
(27)
D
Du (mnL (+(())))) - f*) + ー [|x] x 113).
+2
1=1
we have (n-L-1)
11) 5 - as we assumed n S 4L Using coneavity of - xx11
for 3 < 0, we get
Dv (ImL 1 (1(((()) f²) + -14 |xx x1) S "h (f(x.) - -f*) -1r7 ||x:
2m
x11
2
(28)
By Applying the last incquality in 27
Dr
X 7.8," -x112 (1 pm x2 + 2 L
|x x, (f(x)) - fr). (29)
D
16

---

Under review as a conference paper at ICLR 2023
We obtain
V Du (V] v
I:
8il
(30)
D
==1
Du
Σ
(VF
(x:) VF((2)) (X)( {(("))))
(31)
D
Do
Do
< 2(1
Σ
(V) ( +1 Σ
(Vf' (x, v
(32)
D
D
V Dv
Du (V)(x)) - V]({)))1
S 2(1
Σ
(x) - +/
+1
Σ
(33)
D
D
==1
==1
V
Du
Du
2 2
(/(2)11 +2 Σ
[VV[(x}) -
(34)
D
D
==1
$ 21 Σ
Du
lxx] 1
1 222 Σ
De
||0 11
(35)
D
D
41,
Σ
De
D Dull x11
(36)
where in 32). we use
11
33 we have used the fact that ΣV= Do (x)) = f(x).
34
and
35 are due to the convexity of |.1 and L-smoothness, respectively.
Taking expectation of
29 and 36 and applying them into (16 provides
E 18+111xx 1| S (1 + n1 mmme E &
- - f²)
(37)
+ 21 E |ige Be 112 + ((1 + - m2) + (=m + 2n 2n 141
5
Σ
v
Dr
E |
x
D
1=1
Lemma 7.2 (Bounding variance). If Exg [x)((x)) - V) fo
1 S S V, then E [|g -: 2| S po?
Proof. We have by definition that
Dr Du
E lg:
3e12=
gell
E1
Σ
(V -
(38)
D
D
E (x)
(39)
V
D
2
D!
(40)
< po?
(41)
where (39p is based on the fact that variance of the sum of independent random variables equals sum of their variances.
Lemma 7.3 (Bounding deviation single-stream). If gap(S (St) < H, max 1) < E,
E, f. (x))) < G². and th < 24 for 0 - t - T - 1. 1 S 5 V, then
Σ D. E E xX|12 < 64V (H + E.G D
17

---

Under review as a conference paper at ICLR 2023
Proof. For every there exist 7J', such that x x Considering to = minfr", ..., 7 we have t To H. we know that all the updates of all of the nodes up to iteration To, aggregated in XT. We have
x,;
Sro
Σ ΣE hE t'=Ta
Dr
(42)
where H" = {// Tp Stih and NTo = X0 E EV Exeu, Bo (xy)
Lets use 11 to decompose the the deviation term as depicted in the following:
| x|| S 4(1xx - , 112 + 1| & 112 + ||x - =00011== + 1|x, - -x,01?).
(43)
based on the fact that 8- -8¹ S HI, we can obtain
E ||x] X 1| = E |x_ 11
(44)
= E
Σ
n V (x:)1²
(45)
M= sEu"
= =E Σ
N7 Vey (x1)
(46)
=EU "
S n -El U U
Σ
(x,
(47)
xEU 2-
S nेद - (t - (T: - G2
(48)
< V E H1 + G²
2
(49)
where we have used -E--E S. Tro E. For the second term, using the same approach, we have
Dr D
E X 11
E
Viy
(x!))
(50)
hEF P==oo zEuy
T. Σ
Dr
$ |
Σ
nhe fzy
(51)
REH
P= =Eag
Dh D
Σ
HH + E
(52)
D
NEH
D
S 1 (H + GV
Σ 2=1
(53)
D
- + E)
(54)
18

---

Under review as a conference paper at ICLR 2023
The third term can be bounded like
To
Dr
V T--1
De
E
To
x
11
E
D 9 Viy(()))))
(55)
== REW
$ E
Σ
D
D. D
(56)
==
V
V
Do D
E 2
Σ
n
(57)
==1
V
D
2
E
Σ
(58)
1/w0
S v B VV.. For the last term, using the same logic, we can obtain
(59)
|| x x S n H²V
(60)
Considering that - S 21/ and adding up the previous four estimates, we have
| =x'1? < 64V p 6n
E)
(61)
Observe, that Lemmas 7.1 and 7.2 hold regardless of how to synchronize the nodes. Lemma 7.4 that limits how far the local sequences can deviate from the virtual average, is also still valid for the multiple synchronization streams. This obvious the first sight as having multiple streams helps further reduce the gap between the local sequences and the virtual iterates ( [|x; xx]l?).
7.2.1 COMPLETING THE PROOF OF THEOREM
By replacing results of lemmas
7.2 and 7.4 in lemma
7.1
we obtain
E X x²1 < (1
" T/ pmmp E X
Tl (I ((x)) 1*) + And + A2ti + Asni:
5
2
(62)
where A = - A2 = 128V P (1+ 101 and As = 128V PL +44L)
Observe that
W/ (1 + セ/ n1 - mmm))= = 11
11
(a + t)s
16
(a+ t)2
16
5 (a +1)
(63)
1/x 5
4
5
< 1 (a (a+1) 1)3 - 3(a + 1)2 + 3(a + 1) 3
(64)
w
(65)
M--1"
where (64) is correct for a 2 2. By multiplication of (62 and wt and using the last inequality we qf"
have Wt
E
x"1 1|2
Wh-1
E
x11
We
(E
ft) + Awam. + A Aguini
T)
17
2
(66)
So we can recursively substitute the first term of the right hand side of the inequality to get
wr-1
E
|X
x"11 x11
Wg (1 + H
770 5 mo) -
- x² 100
We
(E
((x)
fr)
(67)
---
2
1=0
T-1
T-1
+ A
Σ
Wilt + A₂
Σ
winh + As
Σ wmm
1=
1=0
1=0
19

---

Under review as a conference paper at ICLR 2023
By rearranging the terms and considering that (1 + 51 umm) 1 1, we have
T-1
T
f*) =
2wo
|xا - x
11 x=11
2A1
Welh + 2A₂
Σ
wiTh
Th + 2As
Σ
wiTh
770
t=0
t=0
t=
t=0
(68)
Based on the convexity of f we have
f(XT) fr -
ST wi W1 f(x))
(69)
2w0
2A1
T-1
24₂
T T-1
2As
T-1
|x0 - x x²112
Wo
+
Welli
+
Σ
winh
(70)
ST70
ST
ST
ST
t=0
t=0
We next aim to bound the terms on the right hand side of the inequality:
4(a +1)
27(2a + T --11 1)
WOTT
(71)
1
1
T-
16
16T
WiTh
(72)
422 42
T-1
T-1
64
64 T-2 dt
64
Σ WiTh
Σ
(a + I 1& |_ (a+ I
In(a + T 2)
(73)
1=
1=0
T-1
T (2T + GaT - 3T + 6a 6a + 1) >
T
ST
(74)
6
3
1=0
Where 77
is correct due to 2 2. Using the above bounds we can write 70 as
3
12(2a + T -
96
384 In (T +
2)
E f( f S
[D
x2
A
A2
As.
27
4T
T
1
(75)
This completes the proof of Theorem 4.1
7.3 MULTI-STREAM DIGEST
Notice that Lemmas 7.1 and 7.2 hold for the multi-stream scenario. Hence, we need a modified version of Lemma 7.4 which limits how far local sequences can depart from the virtual in the multi-
stream DIGEST.
Lemma 7.4 (Bounding deviation multi-stream). If gS [r)) < H. gap(Visr<RS*br) < # +6, < cp, max(ly - -t} < E, E, | (x 2 < G?, and m S 2 for
ΣR E D
D
0 S 8cRhmax).
R, then MV
Da E & x < 4 +
D
Proof. We 7." (r] denote the last time slot up I, when node v's model was updated with stream r, Le. 7 [r) = max(!' 1'' < 1, (r) = 1}. Lets use 11) to decompose the the deviation
term depicted in the following:
n
R
| - 211 < 2(11x)
Σ
[ - (R - 1)xol1 +|x
Σ
x (R- 12))
(76)
Lets assume 71) max (7](1), +8 (R)) For the first term we can obtain
20

---

Under review as a conference paper at ICLR 2023
R
E |
Σ
x - (R - 1)xoll = =E El
fe (xt)]
(77)
1'=T" zEu?
H
1
+ + E) T77 2
(5) G²
(78)
R
H
(79)
R
For the second term in (76) we again use
11 to expand it to two terms as
mmll (R l)xo
2 s 2(1x
Σ
[
(R 1)x011
(80)
y=1
R [x (x(+))))))
+|
Now we bound two terms on the right hand side of (80) in the following. The first term shows the difference between the virtual sequence and the sum of the updates in all nodes aggregated in global models. In fact, the difference shows all the updates that has not been seen by any stream pulse the updates that are lagged. we difine To min ( .... 7 (t))-
E X
[rl 1=1
R
(R- 1)xol 12 = E Σ
Σ
L-1
Σ
Dr
(x)(x)1
(81)
D
v=1
1- (1) =E
H
+ + E) E GVV
(82)
R
H + +
(83)
R
Where (83 can be found with the same approach as (54). Here we define (t) = 1/ [r]
7 [r] t). as the list of nodes that are visited by stream r after node v (Repeated nodes may appear in the list). Note that E (B) < 2hmaz.
R [x 2211111
E| [ - ( S RE
Σ
(84)
r=1
< RE Σ
Σ
Σ
Dn
DA
n Vi
(85)
D
KEBA()) (f(h)) sEaB
R
[
< 2oz
maz
E
Σ
Σ
(
Dr D
(86)
B1)
+((r)) sEu
11
Di D
< 2Rhmaz
+6++E)2 E
(87)
R
Bt
H
D
< 2ax
+6 E)² E
v fig
(xb))
D
B1)
(88)
H <2h
Dap
+6 2 1/ H- G E
L
(89)
D
11
< 2Rhmaa
+ + E)² H-E G2pp.
(00)
R
21

---

Under review as a conference paper at ICLR 2023
where (84 85 86 87
are based
and the fact that the duration between two subsequent visit pf
node from different streams is at most R + (90) follows from the assumption of not too many
streams in companions to V.
By using
79/0083190 in 76) we get
H
|
x
+ E) - G p(VV + 8cltmaaz)
(91)
H
s 4
+ E² p(VV + 8cRRmazz)
(92)
R
22


Reviews:
[{"review_id": "rdS661snI8", "reviewer": "Reviewer_cXkn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a new communication efficient decentralized optimization algorithm for stochastic gradient descent. The algorithm still has the comparable convergence rate compared with non communication efficient case. ", "summary_of_the_review": "The paper proposes a new communication efficient decentralized optimization algorithm for stochastic gradient descent. The algorithm still has the comparable convergence rate compared with non communication efficient case. The main concern of the paper is its assumptions seem restrictive. \n", "strength_and_weaknesses": "+ The algorithm achieves communication efficiency and fast convergence simultaneously. \n+ Both theoretical analysis and extensive experimental results are presented. \n\n-  The set of assumptions seems restrictive. \n-  The notation of the algorithm is not easy to follow.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "QRT5NVD7jsD", "reviewer": "Reviewer_j1sH", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to improve the communication efficiency in decentralized learning. They propose a novel algorithm, DIGEST, which uses local SGD and random walk to reduce communication costs. The random walk communication can be extended to multi-stream. They provide  a standard convergence results and provide empirical evaluation. ", "summary_of_the_review": "The DIGEST algorithm looks interesting but I still have concerns about the theoretical rates mentioned above. I hope that the authors can address my concerns.", "strength_and_weaknesses": "Strength:\n- The design of DIGEST looks interesting.\n- The assumptions and theoretical results seem reasonable.\n\nWeakness:\n- It is claimed in page 8 that linear speedup O(1/VT) can be achieved provided $H+E\\le O(\\sqrt{T/V})$. However, the synchronize interval H can be as large as $2V$ ---- take a chain topology for example. Then the inequality means $T\\ge V^3$ where the time for convergence increasings dramatically with the number of nodes. \n\n- It is unclear from the theoretical results how the graph topology influences the convergence.\n\n- Only simulation experiments are provided.\n\nMinor weakness:\n- While it seems true that DIGEST is independent of the non-iidness of data, it is not reflected in the main theorem 4.1 due to the current assumption 4 (bounded second moment). \n\n- The claim of \"time-varying\" network topology is not justified in the paper.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "DWKpdTaT_5l", "reviewer": "Reviewer_yt5V", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes an alternative approach to Gossip and Random-Walk decentralized algorithms. Synchronous Gossip algorithms require agents to communicate their models to their neighbors and then wait for all of their neighbors' updates before aggregating the updates. This setup has two significant flaws. The first is the large communication overhead. The second is that mismatched computational ability among nodes and communication delays can further increase the convergence time. Asynchronous Gossip algorithms, where nodes communicate without waiting for their neighbors, aim to resolve the second issue. However, the communication overhead issue remains, and the delayed updates require strict assumptions to assure global convergence. Random-walk algorithms operate by having one agent update a global model with its local data and then passing the global data to one of its neighbors to repeat the process. While this approach offers significantly less communication overhead, there is a trade-off in increasing convergence time. \n\nThis paper builds upon random-walk algorithms by having nodes perform local steps instead of idling and by having nodes that receive the global model perform an aggregation step, including the prior local steps. Analysis is performed on this algorithm to show how its convergence and experimental results demonstrate the algorithm's superior performance compared to other decentralized methods in terms of wall-clock time.", "summary_of_the_review": "The paper proposed a variant of Random-walk decentralized algorithms that have agents perform local steps instead of idling. Convergence analysis and experimental results are provided to show the feasibility of this algorithm. The analysis is questionable due to the use of the bounded gradient assumption in the strongly-convex setting. In addition, the algorithm requires knowledge of the proportion of the data held by each agent. The experiments do not detail the optimization of the various algorithms that are used to compare against the author's proposed algorithm.", "strength_and_weaknesses": "The strength of this paper is that the proposed algorithm is an intuitive and novel extension of Random-Walk decentralized algorithms. Having agents be active by performing local steps when not hosting the global model limits the downtime of Random-Walk styled algorithms and closely mirrors the plethora of works that incorporate local steps in between gossip communications. The use of local steps in gossip communications has been well-studied empirically to reduce communication costs and the benefits should be transferable to Random-Walk style algorithms.\n\nUnfortunately, the analysis of the algorithm is done using the assumption of bounded gradients (Assumption 4) and that the proportion of data held by each agent relative to the total amount of data is known. The bounded gradient assumption for unconstrained strongly convex minimization cannot be satisfied. This makes the analysis of the algorithm questionable considering the analysis is applied to the strongly convex function class. In addition, using the bounded gradient assumption makes any interpretation of gradient dissimilarity meaningless, as then the following holds\n\n\\begin{equation}\n    \\lVert \\nabla f_i (x) - \\nabla f_j(y) \\rVert \\leq \\lVert \\nabla f_i(x) \\rVert + \\lVert \\nabla f_j(x) \\rVert \\leq 2G.\n\\end{equation}\n\nClearly, the measurement used to gauge the dissimilarity between functions is not refined. In addition, it is quite confusing as to why the bounded gradient assumption is even required. For the i.i.d. case the quantity is unnecessary. For the non-i.i.d. case, non-bias corrected methods uses the average of the norm of the local gradients evaluated at the global solution while bias-corrected methods require no assumptions. Another aspect of the algorithm that is not mentioned as an assumption but should be included is the use of the quantity $\\frac{\\mathcal{D}_v}{\\mathcal{D}}$ which is the proportion of data held by agent $v$. Knowing this quantity is extremely powerful because it allows for decentralized algorithms to account for the data dissimilarity between agents as we know what weight each of the local objective functions contribute towards the global objective function. However, for decentralized algorithms, it is uncommon to possess any global information regarding the data. \n\nAnother aspect of the algorithm that is not well defined is the relationship between the quantity $H$ and $V$ where $H$ is the bound on the interval between two synchronizations and $V$ is the number of agents. In the remark, the authors use the fact that $H + E \\leq O (\\sqrt{T/V})$. For Random-Walk styled decentralized algorithms, it is intuitive that the interval between two synchronizations increases with the size of the network. To account for this, an increasing number of synchronization streams $R$ would be required therefore increasing the communication cost. However, the relationship between $H$, $R$, and $V$ is not detailed.\n\nComparing the behavior of the various algorithms under the i.i.d. balanced case makes very little sense as communication is oftentimes much more expensive than local computation. Thus, performing more local computations is always preferred as local computations will inexpensively push all agents towards the global solution. In the non-i.i.d and unbalanced case, it is clear that DIGEST has the best performance. However, it is unclear what hyperparameters are used for the other algorithms. In addition, DIGEST has the benefit of knowing the proportion of data held by each agent. Thus, the validity of these simulations are questionable.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject