Asynchronous Decentralized Online Learning
Authors: Jiyan Jiang
Wenpeng Zhang
Jinjie GU
Wenwu Zhu
Venue: NeurIPS 2021 Poster (2021)
Keywords: online algorithm
distributed online learning

Abstract: Most existing algorithms in decentralized online learning are conducted in the synchronous setting. However, synchronization makes these algorithms suffer from the straggler problem, i.e., fast learners have to wait for slow learners, which significantly reduces such algorithms' overall efficiency. To overcome this problem, we study decentralized online learning in the asynchronous setting, which allows different learners to work at their own pace. We first formulate the framework of Asynchronous Decentralized Online Convex Optimization, which specifies the whole process of asynchronous decentralized online learning using a sophisticated event indexing system. Then we propose the Asynchronous Decentralized Online Gradient-Push (AD-OGP) algorithm, which performs asymmetric gossiping communication and instantaneous model averaging. We further derive a regret bound of AD-OGP, which is a function of the network topology, the levels of processing delays, and the levels of communication delays. Extensive experiments show that AD-OGP runs significantly faster than its synchronous counterpart and also verify the theoretical results. 

Asynchronous Decentralized Online Learning
Jiyan Jiang" Tsinghua University scj jy95@ottookk.cooomm com
Wenpeng Zhang" Ant Group
changwenpengQ@gmail.com
Jinjie Gu Ant Group jinjie.gut mujjjaggrouu.coo
Wenwu Zhu Tsinghua University wwzhu@tainghua. edu.
Abstract
Most existing algorithms in decentralized online learning conducted in the synchronous setting. However, synchronization makes these algorithms suffer from the straggler problem, i.e., fast learners have wait for slow learners, which significantly reduces such algorithms' overall efficiency. To overcome this problem, we study decentralized online learning in the asynchronous setting, which allows different learners to work at their own pace. We first formulate the framework Asynchronous Decentralized Online Convex Optimization, which specifies the whole process of asynchronous decentralized online learning using sophisticated event indexing system. Then we propose the Asynchronous Decentralized Online Gradient- (AD-OGP) algorithm, which performs asymmetric gossiping com- munication and instantaneous model averaging. We further derive a regret bound of AD-OGP, which is function of the network topology, the levels of processing delays, and the levels of communication delays. Extensive experiments show that AD-OGP runs significantly faster than its synchronous counterpart and also verify the theoretical results.
Introduction
Decentralized online learning has recently received increasing research attention due to its capability of processing large-scale streaming data in decentralized computational architectures (c.g.. mobile
networks and CPU/GPU clusters). Many different algorithms have been proposed [3I 32 22 15 28
16
24
and successfully applied in various application scenarios, such as recommendation systems
29
energy management (5) and cooperative navigation (21)
Most of the existing decentralized online algorithms are investigated under the synchronous setting, where all the learners are restricted to communicating their updated information (e.g., model param- eters, gradients, dual variables) with each other at the same pace. However, this synchronization mechanism incurs the straggler problem, which can markedly deteriorate the efficiency of the algo- rithms [30 [7.3. J. In more detail, at each iteration, the fast learners have to wait for the slow learners, ie., the stragglers, to finish their update and communication. Consequently, their speeds will be dragged down by those of the stragglers, which may dramatically reduce the algorithms'' overall efficiency as the speeds of different learners in decentralized system usually vary widely owing varying computing powers, storage capacities, network bandwidths, etc.
As is well acknowledged, designing the asynchronous counterpart of synchronous algorithm is the most common way to resolve the straggler problem. However, compared to the well-studied
Equal contributions.
*Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

centralized online 18 and decentralized stochastic [27] 3 23 learning in the decentralized online setting remains largely unexplored. The major obstacle is its intrinsic hardness. In asynchronous decentralized online learning, each learner has five basic types of actions, namely prediction, weight update, message sending, message receiving, and model averaging. Due to asynchronization, each learner executes its own actions independently. Hence the orders of the actions of different learners are intermixed together, which results in very complex interaction dynamics. By far, even no formal framework exists that can accurately describe the whole process of asynchronous decentralized online learning, not to mention algorithm design or theoretical analysis.
settings, how to do asynchronous
In this paper, we conduct a systematic study of asynchronous decentralized online learning. To begin with, we formulate the framework of Asynchronous Decentralized Online Convex Optimization (AD-OCO). We first specify the action sequence of each learner using its own indices, then propose a novel event indexing system, which delicately characterizes the complete orders of actions of all learners by mapping them into single time axis. To the best of our knowledge, this is the first formal framework that gives a complete characterization of the whole interaction dynamics of asynchronous decentralized online learning.
Based on the proposed AD-OCO framework, we develop the Asynchronous Decentralized Online Gradient-Push (AD-OGP) algorithm. AD-OGP consists of two key modules. The first module is a gossip-based communication scheme, in which each learner is only allowed to communicate with its immediate neighbors. In general, there are two major types of gossiping strategies in decentralized
algorithms, namely symmetric gossiping 13 77 and asymmetric gossiping [9 3. In asymmetric
gossiping, the gossiping sender does not need to wait for the response message from the gossiping receiver after it sends out its message. Hence asymmetric gossiping does not require any local synchronization among learners, which is needed in symmetric gossiping. This makes asymmetric gossiping more suitable for asynchronous online learning. In particular, we adopt the push-sum strategy [14 19) which is the most common way to realize asymmetric gossiping. The second module is a local update scheme, which builds upon online gradient descent (OGD) 33 When combining push-sum with OGD, if we directly apply the standard projection operation, the resulting algorithm crashes as it may generate predictions outside of the feasible region. To resolve this problem, devise a novel weighted projection operation, which makes its local update compatible with push-sum. Moreover, in AD-OGP, we allow each learner to perform model averaging as long as it is unoccupied and its receiving buffer is not empty, which effectively reduces the communication delays. We emphasize that the above innovations, namely weighted projection and instantaneous model averaging, are two special designs when tailoring asynchronization to the online setting.
We further conduct the first regret amalysis of asynchronous decentralized online learning. In particular, we extend the graph augmentation technique [10 to the online setting to handle message delays, then disentangle the complex effects of predictions, weight update, and model averaging via our proposed event indexing system. We derive non-trivial regret bound of AD-OGP, which captures the effects of the network structures, the levels of processing delays, and the levels of communication delays. Our bound is in the same order O(v as that of its synchronous counterpart [27]. In addition, we make extra contribution the convergence analysis of push-sum. Specifically, we reduce factor of /n (n is the dimension of model parameters) in the convergence rate of push-sum compared to that in 22, and our final bound is now independent of n.
Experimental results on two large-scale real-world datasets show that AD-OGP runs substantially faster than its synchronous counterpart, with nearly negligible loss in performance. We further design elaborate experiments to verify the effectiveness of the two innovations of asymmetric gossiping and instantancous model averaging in AD-OGP. Specifically, with either innovation removed or weakened, the reduced algorithm will be incffective in some specific settings. The theoretical results of AD-OGP's regret bound on different graphs and delay levels are also well confirmed.
Asynchronous Decentralized Online Convex Optimization
In this section, we formally describe the AD-OCO framework. Our framework is defined over an undirected graph 9 = (V, E) with vertex set V = (1...., m) and edge set E C V x V. Each node i E V represents an individual learner which maintains a local model w; E K. where K. is convex compact decision set. Each learner i can only communicate with its immediate neighbors Ai(i) (j E V (i,j) E}.

---

We first illustrate the whole process of AD-OCO, As the process is very complex, we divide its description into two parts: (i) Individual view, which specifies the action sequence of each individual learner; (ii) System view, which characterizes the interaction dynamics among different learners.
Individual View Each learner E V is selected adversarially by the environment to make predic- tions at certain time points. We index the prediction rounds of learner i as T = -..... N₁. At each round 7, learner i predicts with its most recent model w. Then the environment reveals convex loss function ff : K + R. and learner i suffers the loss (w]) When receiving the feedback, learner i begins to calculate the gradient V.f. (w: ). After finishing the calculation, it uses the gradient to update its model w0 < U( V f. (w])) where U is the local update scheme. Then it selects a subset of neighbors, and sends a copy of its updated model to each of them. Besides sending out its own model copies, learner i will also receive its neighbors' model copies at certain time points. These copies will be stored in its receiving buffer B,. Whenever learner is not occupied with gradient calculation or local update, and its buffer is not empty, it can average its model with the model copies stored in the buffer, i.e., un; < A(w,; B.), where A is the model averaging scheme.
System View Due to asynchronization, each learner executes its actions independently. Hence the orders of actions of all learners are intermixed. To precisely characterize the interaction dynamics among learners, we need to specify the complete orders of the actions of all learners by mapping them into a single time axis. To this end, we propose novel event indexing system. We view either a prediction or a local update of any learner as an event, and use virtual counter t to index these events, which will increase by one each time some learner makes a prediction or completes local update. Let T = Eiev V N; be the total number of predictions of all learners, then the total number of local updates is also T. For each event t E {1,.... 2 we use 6, E {0, 1} to distinguish the event type: (i) 8, 0 if it is prediction event, and (ii) 6, if is a local update event. We further use it to denote the learner that executes the event t, and fe to denote the associated feedback; then there exists some T E {l...., N..) such that ft f7.
In particular, if event t is a local update event (i.e., 6, = 1), we denote 4, as the index of the associated prediction even{" and rd (1) = - 1 as the gap between these two indices. Since any prediction must occur before its corresponding local update, here we have i 2 2, 4 < 1 and do (t) > 0. Let card A) denote the cardinality of set A. Now we introduce quantity of fa called the processing delay dP c4 <a s < t 6_- J.. which measures the number of local updates that occur between the prediction and the local update associated with fc. Note that our definition of processing delay is in line with those in other asynchronous frameworks for stochastic optimization [7
Recall that, after any local update event t, the learner it that executes this event will send out its model copy to a subset S of its neighbors (oabbborsNN(i (i.). We focus on the copy sent to any neighbor j E St- We assume such copy is used to average learner j's model between events Tıj and (rty + 1) for some Mty 2 f. For the message sent from learner é, to learner j after event f, we introduce a quantity termed the message delay dh (t) = rtj f, which measures the number of events that occur while this copy is in transmission or learner j's receiving buffer. Note that in the asynchronous stochastic setting 3 [23], the message delay is measured by solely counting the number of local updates. In the online setting, we also count the predictions because whether model averaging occurs before or after a prediction will affect the gradient calculation, which further affects the corresponding weight update.
With the above event indexing system, we can characterize the evolution of model w,. For each learner i, we denote wx(t) as its most recent model before event t, and u, (t(t) as its model immediately after event f. We first give the detailed characterization of local updates. Specifically, for each local update event f, it is executed by learner it. The associated gradient was computed w.r.t. learner i, 's model w. (1+) at prediction event 4, So the local update on i, can be characterized as
u (t) = Ld ((w,,, (t); V fi, (w., (4)).
The models of other learners do not change at it's local update event, so (1) = w (() for j A i.
We then give a full description of model averaging. Recall that, in our indexing system, model averaging operation is not regarded as an event. Hence we need to specify it using the indices of its nearby events. Concretely, for each learner i, we consider its model averaging during the interval
Note that in our indexing system, when 6, = 1, the feedback and its associated learner can be represented by the index of either the prediction event (, the local update event t, i..., fi. and it, is.
3

---

Protocol Asynchronous Decentralized Online Convex Optimization (AD-OCO)
1: Input: Time horizon T, convex set K., local update scheme U, and model averaging scheme .A.
2: Initialize: Local models wy(1) E IC, Vj E V.
3: for = 1, 1,...,27 27 do
4: if 6; = then
for a prediction event learner i V is selected by the environment adversarially predict with ws, (L). Learne i, receives a convex function fe from environment, and suffers the loss fi(ws; (4)).
5:
6:
7:
Learner i, starts compute the gradient (i, (4)).
8:
else
for local update event
9:
Learner it performs local update:
un (t) = U( (t); Vf,, (wa, (4)).
Learner it selects subset S of its neighbors ((4) and sends u. (f) each j E St.
11:
end if
for E do
13:
Learner performs model averaging using model copies B (1). ,,, (1) is inoccupied:
w: + 1) = (t), s 0:
A(- (4A-
$21.
14: end for end for
between event / and / + 1. If it is not occupied in this interval, we assume it performs model averaging operations for some 2 0, each time using copies (.)...... B (t). Recall that learner i's models the beginning and the end of such interval are (t) and w, + 1) respectively. Hence the overall effect of model averaging on learner between event t and + can be expressed as
w; (t + 1) = (t), s=0; 0;
A( (AAA( (()), s s2
Regret Definition In AD-OCO, the regret w.r.t. an arbitrary reference learner j E V is defined as Regret, = Σ (lw - Σ fi(w")
(EPT
LEPT
where Pr = ft E {1...., 6, 0} denotes the set of all prediction events, and w² e argmin Eiep, f:(w) denotes the best fixed model hindsight. The goal of the learners is to make sequence predictions (t))eeP so that the regret w.r.t any reference learner j is sublinear in T, i.e., limy Regret, /T O. Note that our regret is in line with the regret defined in the synchronous setting [27 31 where all the losses (fr t E Pr} are evaluated by fixed reference learner j.
Asynchronous Decentralized Online Gradient-Push
In this section, we first present the AD-OGP algorithm, then provide theoretical analysis for it.
3.1 The Algorithm
AD-OGP consists of two core modules: a local update scheme and a communication scheme. The
local update scheme builds upon OGD [3). The communication scheme based on push-sum [19]. We introduce two novel algorithmic designs when combining push-sum with OGD, namely weighted projection and instantancous model averaging. The complete pseudo-code of AD-OGP is given in
Algorithm
Push-Sum Communication Before presenting the details of push-sum 14 we first give some
background knowledge to help understand the rationale of it. In most decentralized algorithms,

---

Algorithm Asynchronous Decentralized Online Gradient-Push (AD-OGP)
1: Input: Time horizon T, convex set K. and learning rate 1/-
2: Initialize: Push-sum model x1( + Wo E I and push-sum weight y5(1) t 1, E
3: for t = 1, 1....,27 do
4: if 6, = then
for a prediction event
5: Learner i predicts with w. (4) Di, (1) /i, (l).
6: Learner i, starts to calculate the gradient V Se(ws, (1))
7: else
I/ for local update event
8:
Learner in performs weighted projected online gradient descent:
(xr), (t), (t) = (Y. Ti (t) v)V ft. (wi, (W)), (t)bi(t))
Vi, (t)
9:
Learner is sends x²,, (t) and Vl, (t) to each of its neighbors j E (
10:
end if
11:
for E V do
12:
Learner performs model averaging using model copies (1). (1)
(1) is unoccupied:
(or + 1), se(1 +)) (a/(1)
Σ
x', s( Σ Σ v)
(ac (())((()
r=1 (a' (1)
13: end for
14:
end for
communication is based on distributed averaging [26 [ i.e., computing the average model 1 Σiev 2; of all learners V = {l...., m) over network G. In general gossip- basedp approaches, at step 1 E {1..... L.}, each learner i E V accesses the models of its neighbors and averages these models with its own model obtain x2 1) Ejev Piş (1)zz (1), where (t) 2 0 the averaging weight. In particular, Pty > 0 only if learner accesses learner j's model. The model averaging of all learners has compact matrix form X(1 + 1) P()) (I), where the i-th row of (1) denotes learner i's model x; (l), and the entry at the i-th row and j-th column of P(I) is Piy (I).
In symmetric gossiping 8 17 it is a common practice to design communication schemes such that the corresponding (() doubly stochastic, i.e., P( (1)) T 1, where the m x all-one vector. Then by the property of Markov chain, lim I P()) = _11" which implies that the local model of each learner i will approach ar, (x0)
The doublý stochastic property is often achieved by letting (t) = (t), which requires local synchronization between the gossiping pair (i, In asymmetric gossiping, however, we typically have (ty(() # (1). So in general, it is very hard or even impossible to design a scheme in which P() is doubly stochastic (2). The usual way 20 to bypass such harsh requirements is design communication scheme whose P()) only satisfies the column stochasticity, i.e., P(I) = 1. Then it can be proved that lim I P(I) I for some E IRM, which implies that each learner i will converge to n; Push-sum strategy [19 removes the bias т; via very light extra communication. Specifically, each learner i maintains positive scalar y; termed the push-sum weight, initialized as y1 (1) 1.
Then it applies the same averaging operation of æ; to y, at each step I, i.e., y + 1) = (()) By the property of Markov chain, lim yi = क, for each learner i. Thus the ratio 2; (1) (1)) approximately approaches æ.
Given the above background knowledge, we provide the details to implement push-sum in the asynchronous online setting. The core is to assign the averaging weights Pty (t) at each step t to make P(t) column stochastic. For simplicity, we first assume there is no message delay. After each local update event f, learner i can only send its model copy to its neighbors (t.). Hence Pks,, (t) > 0 only if l (()) U (i.). To ensure VEE Pki, (t) = natural choice is to assign the same weight Pki, (1) %i for all & E (it))) U { where Ti, 1/(l)(i.)) + 1). Our implementation satisfies this condition: After each local update f, learner & first multiplies its model D;, and push-sum weight yr. by Mig i.c.. o Di and v/, Yi, Vi, Then it sends copy of æ and vl, to each neighbor
j E (ix).. In the corresponding model averaging, learner j adds x', and v/, its own parameters,
5

---

i.e., Zy f- 2 + 2', = = %/ "i and yj + 9; +V, = Vj + Ni.i.. The model averaging operation
of learner using buffer Bi can be summarized as
A((a,, y:); = 2 +
Σ (7)3))788))8B;
Jo y1 +
7685) (188),75
Σ
Note that when there are message delays, our scheme can still induce column stochastic P(t) on the augmented graph [0]] each step f E (I....,,2]] (see detailed proofs in supplementary materials).
Weighted Projected Online Gradient Descent Recall that, in push-sum, each learner has two types of parameters, namely the push-sum model æ; and the push-sum weight y;: and it always predicts with w; = 0;/y;- Learner i is initialized by H; < we E IC and yı: + 1. In OGD's update with gradient g. learner i first performs gradient step its model 2;, i... Z, æ; ng. where 17 is the learning rate. However, its next prediction æ./ //: may lie outside of the decision set iC, which violates the feasibility. To ensure feasibility, OGD executes a projection operation Th on the model F; after the gradient step, i.e., [T;();) denotes the L. norm. However, if we directly apply the standard projection operation, we may still have w; = 1lx (2:)// & IC after projection, because yi can be less than 1. Hence we need special design of the projection operation. Notice that when y/i O, 0;/9; K. is equivalent to I; E yuK = {yow w E K.). Since y;K. is also convex, we can project æ; onto y,K. instead of K. Then we have (x,) argmin || - xell = y/s argmin w- tu.-z/pm 1z.y.ll = (x, (v.) y.). which can be viewed as the standard projection II (xx) distorted by weight y/+ The above local update procedure can be summarized as æ, < y; ((z; ng)/ /2:) and + The feasibility of the iterations of AD-OGP strictly proved in supplementary materials.
V
xrg ||a: 2;ll, where ||
Recall that, in our implementation of push-sum, we multiply learner i's parameters æ; and y by a factor of y immediately after its local update. This multiplication operation can be combined with the above local update form, which gives a compact expression
(( g)):g = (Try ((x; - ng) /2), wy.).
Instantaneous Model Averaging In the asynchronous online setting, another design issue, namely when to perform model averaging for each learner, should be considered carefully. The learner is unoccupied only when it completes local update and waits to be selected by the environment to make the next prediction. Hence the learner can only perform model averaging during this period. However, the learner may receive messages any time. Each message will be stored in the receiving buffer until the learner performs the next model averaging. The waiting time of this message also contributes message delays. To effectively avoid increasing message delays, we allow each learner to perform model averaging as soon as possible. (i) If the learner receives any message during gradient calculation or local update, it will use this message for model averaging as soon as it completes the local update. (ii) If the learner receives any message during its unoccupied period, it will perform model averaging immediately.
We remark that instantaneous model averaging is a novel design specific to the online setting since when perform model averaging does not constitute problem in stochastic optimization. In fact, in asynchronous decentralized stochastic optimization [3, 23 when to calculate the gradient and perform the local update is actively decided the learner itself, as the data instances do not come in streaming manner. Particularly, the learner can begin to process the next instance immediately after it completes any local update. Hence the learner is always occupied, and the time available for model averaging is only when it finishes a local update. In the online setting, however, the time points of making predictions are adversarially decided by the environment, and thus there may be some time lag between any local update and its subsequent prediction, during which the learner stays unoceupied. Therefore, when to perform model averaging during such unoccupied period needs to be decided. In AD-OGP, we design instantaneous model averaging, which allows each learner to perform model averaging immediately when enters the unoccupied period.
3.2 Theoretical Analysis
In theoretical analysis, we only need to consider the case of m 2 2. In fact, when m = 1, there only one single learner in the network and hence there no communication. In this case, the push-sum weight of the only learner is always (t( 1 and its local model simply evolves as

---

21 11) [x(())(t)))----)-)))))))))))>))) - fi which reduces to the standard OGD B3). Therefore, in the following analysis, we assume m 2 2. Now we introduce two mild assumptions that are commonly usdd in the analysis of asynchronous distributed algorithms 3 23
Assumption 1. (a) The message delays are bounded by some integer Drasg 2 (b) Each learner performs local updates at least once every Ta steps for some integer Ld > 0.
Before presenting the regret bound, we first give some necessary notations. We use 2r {t < 27 5, = 1} to denote the indices of all local update events, then equivalently Qr = ".I.....,T]]] Pr. We further use Qe Qr n (s. t) to denote the local updates that occurs between events and t. Now for any local update event & E 2r, the processing delay d (1) is exactly 1Qr,a Moreover, denote the gradients associated with each local update event
9, Vi,, (a:, (4)/v:, yi, (4+)), 9.
Si, (ax (1)//;((4) their I.2-norms as 9t = |lgell, St = 1| the total processing delay of all feedbacks Deroe= Eieor (t), and the diameter of the underlying network as D.
Theorem 1. For any reference learner j E V, AD-OGP attains the following regret bound
Regret, 1 1w00
m
w w²11²+ 21
Σ
Σ
9h9s +1
Σ
gi
2n
m
Vi. (t)
tEQT oE Qi,,t+1
LE DEQT
+ +29 Σ Σ
21 J (gt + 2((r
Os
21
Σ
Al gb.
9s Vi. (t)
yi, (t)
LE #EL14
LE tE sEQi.e-1
where x = 1- 1 a = (1/m) == (D + De ra).
Proof sketch Our proof consists of three major steps. First, we extend the graph augmentation technique I00 to the online setting to handle message delays. Specifically, we add D virtual nodes for each node E V. and derive a column stochastic Pt)) on the augmented graph at each event t E {1...., 2T communication of all learners via our proposed event indexing system. Then we derive a general regret bound in terms of the transition matrix P()) at each event and the gradients Ir: 9: at each local update event. Third, we analyze the asymptotic properties of P()) induced by our push-sum strategy. Although this part is enlightened by prior research 22 23), we make an extra contribution to the convergence analysis of push-sum. Specifically, when analyzing the diffusion of any model copy over the network, we tackle all of its n dimensions simultancously by utilizing the fact that the rank of the updating matrix A (t) = g is at most one. In this way, we save a factor of vn in the convergence rate compared to the previous analysis 2 As consequence, our bound is now independent of
Second, we sort out the complex effects of predictions, local updates, and
The above bound can be further simplified under the bounded gradient norm assumption 277.
Corollary 1. Suppose 9& S G. S G E Qr for some G < co. Then AD-OGP attains the regret
Regret, S mT 1w-0- w01l2+ 20 G2 DProo)+ 2n m α
8 + +a BBCT,
2n
m
for any reference learner j E V, where a = (1/m)) B, B (D+ + ra).
Remark (a) Suppose the diameter of the decision set K. is bounded by F. Set
T +CCTT)-1 1/2, where C = (8 + /aa then the bound will attain O(CCBT + T Drroc) 1/2). It will be larger with more learners (larger m), heavier processing delays (larger Doroc), heavier message delays (larger mesg), and "less connected" graphs (larger diameter D).
(b) When the processing delays (l) are upper bounded, then Deree ( Now the above derived bound reduces to ((CB)))//) which is sublinear O(VT) w.r.t. T.
(c) The second term in the bound captures the effect of processing delays Eis dt)... This term is in line with the delay effect term in the asynchronous centralized online setting [8].
(d) The third term in the bound captures the effect of decentralization. Note that the factor a represents
a lower bound of the positive entries in any B-hop transition matrix P(I+ B ... P(L+)) e
(1...., 2T - B). which is commonly seen in the analysis of push-sum 1 20 2
(e) When there is no delays, namely Deroe = magg = O, the bound reduces to that of its synchronous
counterpart [1 (for fair comparison, we remove the assumption of strong convexity in M).
7

---

Average Loss
D-OUP AD-OGP
D-OGP OGP
D-OGP AD OGP
Average Loss
1.0
ADP
D-OUP
1.05
Avarage
1.05
1:35
1.05
1.00
1.00
1.00
1.00
100
200
500
1000
500
1000
1500
1000
2000
Time 15]
Time (5)
Time (5)
Time i5)
(4)
(b)
10, D
(0)
D
(d) DP
10, D
Figure I: Illustration of the benefit of asynchronization. The four plots compare AD-OGP and D-OGP on 64-node Watts-Strogatz graphs on pokerhand under varying delay levels.
4 Experiments
In this section, we evaluate AD-OGP on two large-scale real-world online classification tasks. We first compare AD-OGP with its synchronous counterpart show the advantage of asynchronization, then design elaborate experiments to verify the effectiveness of asymmetric gossiping and instantaneous model averaging in our algorithm design, and finally verify our theoretical regret bound.
4.1 Experimental Setup
We select two large-scale real-world datasets. (i) The higgs dataset is a benchmark dataset in high- energy physics 4 for binary classification, which consists 11 million instances with 28 features. (ii) The poker-hand dataset is commonly used dataset in automatic rule generation [6[7]] for 10-class classification, which has I million instances with 25 features. For binary classification, we use the logistic loss; for multi-class classification, we use the multivariate logistic loss 11 definitions in supplementary materials).
(see detailed
In our experiments, the process of asynchronous decentralized online learning is simulated as follows. Given dataset, the data instances are fed the learners one after another each prediction event in streaming manner. We simulate three types of time intervals: (i) the computation time for each learner to calculate the gradients of data instances and perform local updates, (ii) the transmission time for each message to reach its gossiping receiver, and (iii) the waiting time for each learner to wait for the next prediction after it finishes a local update. Note that the waiting time unique to the simulation of our online learning setting, which is not needed in that of stochastic optimization. Similar to the simulation method in [25]. the computation time of learner i follows the exponential distribution Exp(u)) with mean value μ4 |ا|| + 2, where ç is sampled from the standard normal distribution (ormal 1). The transmission time of each message is independently sampled from Exp(0.6). The waiting time is independently sampled from Exp(o) (the mean value ó will be specified later). The units of all time are milliseconds. Note that we also examine other time distributions, such as uniform distributions, and observe similar results, which are omitted due to the page limit.
We use the average loss as the performance metric, which learning experiments [18, 31 24]. Specifically, we randomly select reference learner j E V and measure ΣtEr, (e (O)/ where the model at each prediction event / E Pr given as (t((t) æz (t)/u,()) Moreover, we adopt the commonly used L2-normm balls as decision sets and set their diameters as 100. The learning rate 1) is set as what the corresponding theory suggests (see more details in supplementary materials).
common practice in most online
4.2 The Benefit of Asynchronization
We compare AD-OGP with synchronous decentralized online gradient-push (D-OGP) (.. which synchronizes the local updates and communication of all learners at each round. We conduct the comparison three representative types of graphs with varying connectivities 88 31I. i.e., the complete graph with high connectivity, the Watts-Strogatz graph as a kind random graph with medium connectivity, and the ring graph with low connectivity (see detailed descriptions in supplementary materials).
We also investigate the effects of processing delays and message delays on the comparison of algorithms. We simulate different levels of delays via a technique commonly used in experiments of asynchronous decentralized stochastic optimization [7] 233. Specifically, for the reference learner

---

Averaqe Loss
push-sum
symmeeefff
Averrape Loes
1.04
symmerrc push sum
Average Loos
1.04
blocked
Instant
Avergge Loss
1.04
Di brocked Instant
1.02
1.02-
1.00
1.00
1.00
1.00
500 Instance 18)
1000
500
1000
500
1050
500
1000
Instance (5)
Instance
Instance
(b) D 100
(a)
(b) D 100
Illustration of the effectiveness of asymmetric gossiping. The two plots compare push-sum and symmetric gossiping [17] 64- node Satts-Strooatz graph on pokerhand. We en- large the transmission time of any message sent from/to the reference learner j by D times.
Figure 2:
Figure 3: Illustration of the effectiveness of in- stantaneous model averaging. The two plots com- pare AD-OGP and its counterpart with blocked averaging B on a 64-node Watts-Strogate graph pokerhand. We enlarge the waiting time of the reference learner j by D' times.
we first enlarge its computation time by DP times throughout the learning process, where DP is parameter that controls the level of processing delays. Then we randomly select neighbor k (j) of learner j and enlarge the transmission time of any message from j to &c or k to j by D times, where D is a parameter that controls the level of message delays. Similar [17] we set D = and Dm = 1 to represent a weak delay level, and set D = 10 and D 10 to represent strong delay level. As for the waiting time, we set the mean value compared to the processing time and the transmission time. In this way, the effect of waiting time on the total running time of both algorithms is almost negligible, and the running time difference merely due to synchronization asynchronization.
0.01 to make it relatively small
Figure plots the performance of both algorithms on a 64-node WtttssStrogatz graph on pokerhand under varying levels of processing delays and message delays. The results on higgs as well as other types of graphs are qualitatively similar and deferred to supplementary materials due to the page limit. From the results, we draw two main observations.
(i) AD-OGP runs substantially faster than D-OGP, which is in accord with our intuition that asynchronization eschews the straggler problem and hence saves considerable time. Moreover, the gap in the total running time dramatically increases as the delays become stronger. (ii) In all the examined settings, AD-OGP yields comparable performance to D-OGP, implying that asynchronization significantly improves the efficiency while hardly sacrificing the performance.
4.3 The Effectiveness of Asymmetric Gossiping and Instantaneous Model Averaging
We verify the effectiveness of the two innovations in AD-OGP by showing that, with either removed or weakened, the reduced algorithm will become less effective in some specific settings.
4.3.1 The Effectiveness of Asymmetric Gossiping
We consider a scenario where the communication of certain learner E V is slow. In symmetric gossiping [17], each time learner i sends model copy to any of its neighbor k E ((), it must wait until receiving the response message sent back from & before it can proceed to the next action. Thus its processing speed is slowed down. In contrast, in our asymmetric gossiping, the processing speed of such learner not much affected since empirically, we enlarge the transmission time of any message sent from/to the reference learner j by nd times. We compare AD-OGP and the counterpart algorithm using symmetric gossiping (with implementation) on 64-node Watts-Strogges 2 show that symmetric gossiping will make the algorithm much less effective as message delays increase, which verifies the effectiveness of asymmetric gossiping.
fully asynchronous. To verify this point
graph under varying 1 Results in Figure
4.3.2 The Effectiveness of Instantaneous Model Averaging
We consider scenario where a certain learner i E V is seldom selected by the environment to make predictions. this scenario, each time learner completes a local update, may wait for a long time until it is selected to make the next prediction. During this period, learner i stays unoccupied and may consecutively receive model copies from its neighbors. In AD-OGP, these copies are used for model averaging immediately after they anrive. In contrast, if we directly apply other asynchronous

---

Average Loss
1.02
m044
m0:1
1.02
Stropatz ting
comppltte
1.52
0f-10
Average Losp
1.02
0%-1
p%
1.01
Average
1.01
1.01
101
1.00
1.00
1.00
100
0.99
6.99
0.99
0.99
500
1000
500
1000
500
1000
500
1000
Instance [K]
Instance (K)
Instance (K)
Instance (K)
network
(b) network topology
(6) processing delays
message delays
Figure 4: Verification of our regret bound. The four plots show AD-OGP's performance on poker- hand with varying characteristics. (a) Varying network sizes. (b) Varying network topology. (c)
Varying levels of processing delays. (d) Varying levels of message delays.
stochastic algorithms 3 23
to online setting, these copies will be stored in learner i's receiving buffer until makes the next local update, which essentially magnifies the message delays and will harm the performance of the algorithms. To verify this point empirically, waiting time simulation and enlarge the waiting time on the reference learner j by D' times. We compare AD-OGP and the counterpart algorithm without using instantaneous model averaging (with BI's implementation which we term as blocked averaging) on a 64-node Watts- Strts--trogatz graph under varying D'. The results in Figure 3 show that the counterpart algorithm will become much less effective when some learners need to wait for model averaging, which verifies the effectiveness of instantaneous model averaging.
set 6 0.6 in the
4.4 Verification of the Theoretical Bound
We finally verify our derived regret bound by examining the effects various factors on the perfor- mance of AD-OGP. Specifically,
AD-OGP under varying network sizes, varying network topology. and varying levels of processing delays and message delays. Figure presentss the results on poker-hand. The results show that AD-OGP will incur higher losses with more learners, less connected networks, heavier processing delays, and heavier message delays, indicating an excellent agreement between empirical behaviors and theoretical results.
5 Conclusions
In this paper, we present the first systematic study of asynchronous decentralized online learning. We begin by formulating the framework of Asynchronous Decentralized Online Convex Optimization. Then we devise the Asynchronous Decentralized Online Gradient- -uss algorithm. which is fully asynchronous and includes two novel innovations, i.c., weighted projection and instantaneous model averaging. Theoretically, we provide the first regret analysis paradigm for asynchronous decentralized online learning. Finally, we conduct extensive experiments demonstrate the benefit of asynchro- nization, verify the effectiveness of the two innovations, and corroborate the theoretical bound. Our work paves the way for future research investigating asynchronous decentralized online learning.
Limitations
As the first step of studying asynchronous learning in the decentralized online setting, our framework formulation and theoretical analysis are conducted in the convex setting. Although such limitation does not affect its usage in the non-convex setting, would like to establish formal non-convex analysis in the future.
Acknowledgements
This work was supported by the National Key Research and Development Program of China No. 2020AAA0106300 and the National Natural Science Foundation of China (No. 620501 10, No. 61936011, No. 62102222). This work was supported by Ant Group through Ant Research Intern Program. We thank Steven C. H. Hoi, Peilin Zhao, and Tong Zhang for introducing us to the fascinating research areas of online learning and distributed optimization. We also thank anonymous reviewers for their insightful and valuable comments to help improve the quality of this work.
10

---

References
[1] Mohammad Akbari, Bahman Charesifard, and Tamás Linder. Distributed online convex optimization time-narying directed graphs. IEEE Transactions on Control of Network Systems, 4(3):417-428 2015.
Mahmoud S. Assran, Nicolas Loizou, Nicolas Ballas, and Mike Rabbat. Stochastic gradient push for distributed deep learning. International Conference on Machine Learning, pages 344-353, 2019.
[J Mahmoud S. Assran and Michael G. Rabbat. Asynchronous gradient push. IEEE Transactions on Automatic Control, 66(1):168- 183, 2020.
[4] Pierre Baldi, Peter Sadowski, Daniel Whiteson. Searching for exotic particles in high-energy physics with deep learning. Nature communications, 5(1 (:308, 2014.
[5] Yixin Bao, Yanghua Peng, Chuan Wu, and Zongpeng Li. Online job scheduling in distributed machinc learning clusters. In IEEE Conference on Computer Communications, pages 495- 5035,,0,250 2018.
[6] Robert Cattral, Franz Oppacher. and Dwight Deugo. Evolutionary data mining with automatic rule generalization. Recent Advances in Computers, Computing and Communications, 1(1):296-300 2002.
[7] Dheeru Dua and Casey Graff. UCI machine learning repository, 2017.
[8] John C. Duchi, Alekh Agarwal, and Martin J. Wainwright. Dual averaging for distributed optimization: Convergence analysis and network scaling. IEEE Transactions Automatic Control, 57(3):592 590-66.9 2011.
[9] John C. Duchi, Michael Jordan, and Brendan McMahan. Estimation, optimization, and parallelism when data sparse. In Advances in Neural Information Processing Systems, pages 2832-22400, 2013.
[10] Christoforos N. Hadjicostis and Themistoklis Charalambous. Average consensus in the presence of delays in directed graph topologies. IEEE Transactions on Automatic Control, 596))7733-768 2013.
[11] Elad Hazan and Haipeng Luo. Variance-reduced and projection-free stochastic optimization. In Interna- tional Conference on Machine Learning, pages 1263-1271, 2016.
[12] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. Accelerated decentralized optimization with local updates for smooth and strongly convex objectives. In International Conference on Artificial Intelligence and Statistics, pages 897-906, 2019.
[13] Zhanhong Jiang, Aditya Balu, Chinmay Hegde, and Soumik Sarkar. Collaborative deep learning in fixed topology networks. In Advances in Neural Information Processing Systems, pages 5906 5916, 2017.
[14] David Kempe, Alin Dobra, and Johannes Gehrke, Gossip-based computation of aggregate information. In IEEE Symposium on Foundations of Computer Science, pages 482-491, 2003.
[15] Alec Koppel, Santiago Paternain, Cédric Richard, and Alejandro Ribeiro. Decentralized online learning with kernels. IEEE Transactions Signal Processing, (6(12):3240- 3255, 2018.
[16] Jinlong Lei, Peng Yi, Yiguang Hong. Jie Chen, and Guodong Shi. Online convex optimization over Erdös- Rényi random networks. In Advances in Neural Information Processing Systems, pages 15591-15601, 2020.
[17] Xiangru Lian, Wei Zhang, Ce Zhang, and Liu. Asynchronous decentralized parallel stochastic gradient descent. International Conference on Machine Learning, pages 9049-3058, 2018.
[18] Brendan McMahan and Matthw Streeter. Delay-tolerant algorithms for asynchronous distributed online learning. In Advances in Neural Information Processing Systems, pages 2915-2923, 2014.
[19] Angelia Nedié and Alex Olshevsky. Distributed optimization over time-varying directed graphs. JEEE Transactions on Automatic Control, 60(3):601-15. 2014.
[20] Angelia Nedić and Alex Olshevsky. Stochastic gradient- maddient-push for strongly convex functions on time-varying directed graphs. IEEE Transactions on Automatic Control, 61(12):3936-39) 2016.
[21] Santiago Patemainn Soomin Lec, Michael M. Zavlanos, and Alejandro Ribeiro. Distributed constraincd online learning. IEEE Transactions on Signal Processing, 08:3486-3499 2020.
[22] Shahin Shahrampour and Ali Jadbabaie. Distributed online optimization in dynamic environments using mirror descent. IEEE Transactions Automatic Control, 63(3):714-7255 2018.
11

---

[23] Artin Spiridonoff, Alex Olshevsky, and Ioannis Ch. Paschalidis. Robust asynchronous stochastic gradient- push: Asymptotically optimal and network-indeeendeet performancc for strongly convex functions, Journal of Machine Learning Research, 21(58)11-47, 2020.
[24] Yuanyu Wan, Wei-Wei Tu, and Lijun Zhang. Projection-free distributed online convex optimization with O(VT) communication complexity. In International Conference on Machine Learning, pages 9818-9828, 2020.
[25] Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H. Sayed. Decentralized consensus optimization with asynchrony and delays. IEEE Transactions Signal and Information Processing over Networks, 4(2):293-307, 2017.
[26] Lin Xiao and Stephen Boyd. Fast linear iterations for distributed averaging. Systems & Control Letters, 53(1):65-78, 2004.
[27] Feng Yan, Shreyas Sundaram, S.V.N. Vishwanathan, and Yuan Qi. Distributed autonomous online learning: Regrets and intrinsic privacy- spreeerirnn properties. IEEE Transactions on Knowledge and Data Engineering, 25(1 1):2833-2493, 2013.
[28] Xinlei Yi, Xiuxian Li, Lihua Xic, and Karl H. Johansson. Distributed online convex optimization with varying coupled inequality constraints. IEEE Transactions on Signal Processing, 68:731-746, 2020.
[29] Chi Zhang, Peilin Zhao, Shuji Hao, Yeng Chai Soh, Bu Sung Lee, Chunyan Miao, and Steven C. H. Hoi. Distributed multi-task classification; decentralized online learning approach. Machine Learning, 10744)7777-747 2018.
[30] Ruiliang Zhang and James Kwok. Asynchronous distributed ADMM for consensus optimization. In International Conference on Machine Learning, pages 1701-1709, 2014.
[31] Wenpeng Zhang, Peilin Zhao, Wenwu Zhu, Steven C. H. Hoi, and Tong Zhang. Projection distributed online lcarning in networks. In International Conference on Machine Learning, pages 4054-4062, 2017.
[32] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter W. Glynn, and Claire Tomlin. Countering feedback delays in multi-agent learning. In Advances in Neural Information Processing Systems, pages 6171-6181, 2017.
[33] Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Interna- tional Conference on Machine Learning, pages 928-936, 2003.
12


Reviews:
[{"review_id": "htOJF6CikfY", "reviewer": "Reviewer_8TCf", "summary": "This paper proposes an asynchronous decentralized learning protocol. The motivation is to remove the need for computation nodes to synchronize broadcasting their local models (e.g., to a server), which improves efficiency and brings the setting closer to practical scenarios. The main contributions include (1) an event indexing system; (2) an projection scheme to ensure weight aggregation does not exit the feasibility region; (3) an instantaneous averaging scheme that aggregates neighboring models as soon as each node goes idle and (4) a regret bound analysis.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "--Clarity\nThe paper is clearly written although the descriptions can be a little dense. In my opinion, some diagrams would help to explain the details more efficiently. Minor questions:\n\n1. Is line 5 in Protocol 1 supposed to be outside the if/else block? Else, how does learner i_t gets picked to perform local update?\n2. For the averaging scheme after line 139, does the order of broadcasted copies matter? For instance, when we do pairwise naive averaging, the result would be different from one-shot naive averaging, e.g., (a/2 + b/2)/2 + c/2 != (a + b + c)/3\n3. Seems like a typo in line 203 with the update for y_i, which I think should be y_i \\leftarrow \\gamma_i y_i\n4. What exactly does it mean by \"adversarially chosen by the environment\"? \n\n--Significance & Originality\nI think the problem is important and the solution is well designed. However, I feel like the related work (Appendix) could be more extensive in reviewing other lines of works. Explicitly:\n1. It seems that the related work section only focuses on decentralized literature. I believe a fair review has to include asynchronous centralized learning too.\n2. When it was claimed that the event indexing system is superior because it \"takes both prediction and local update into account\", what are previous indexing systems designed to achieve and what exactly is the implication of this innovation? Also, apart from the computation delay, why do we have to index prediction events if they do not make any weight update? Can't they be modeled under the message delay component?\n3. It was claimed that the weighted projection & instantaneous model averaging component makes the analysis more complex. To me, this feels like a consequence of incorporating these designs, rather than a contribution. \n\n--Quality\nThe strength of this paper is the thorough theoretical treatment. I find both the main results and the remark (line 256-268) very insightful. One thing I find somewhat unintuitive is that to achieve sublinear regret bound, the learning rate is set to \\eta = (mF/2G)\\mathcal{O}(T^{-1/2}), which seems excessively large on scenarios with massive number of nodes. How would this affect the quality of local update in practice? \n\nRegarding experiments: I find the overall quality of the empirical study somewhat disappointing for many reasons:\n1. Why is there no classification error plot? I only see average loss plots, for which the loss value does not seem to improve much (i.e. on the order of 0.00x).\n2. No error bar on the average plot. It would be interesting to see if different nodes have similar learning pattern, which is implied by the regret bound holding universally on every reference learner.\n3. Not enough comparison to existing methods. The proposed method is only compared with its own counterpart, which doesn't say much. I think it needs to be compared with several methods from synchronous decentralized online learning as well as asynchronous federated learning to verify all the claims. \n\n---- Post-rebuttal review ----\n\nThanks for the detailed answers. Most of my concerns have been clarified and I will upgrade my score. I would still recommend the authors to acquire more benchmarks to improve the empirical study section.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The author did not discuss any broader impact of this work, but I believe there is no potential negative impact to society.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "b9O0ImNNEB6", "reviewer": "Reviewer_S1nK", "summary": "This work considers decentralized online learning in the asynchronous setup. Precisely, the learners do not make predictions at the same time and both the local updates and message transmissions incur delays. To account for this situation, the authors propose to index the time by two types of events: predictions and updates. Under this framework, an asynchronous push-sum algorithm is studied and its regret bound is established. The experiments do not only demonstrate the benefit of asynchronous method but also investigate several design choices of the algorithm.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This work makes an important step towards a better understanding of the asynchronous online optimization problem. Indeed, I agree with the authors that a complete description of an asynchronous online learning framework is inherently more intriguing than its offline couterpart, and the methodology considered in the paper paves the way for future research that tackle similar problems.\n\nThe algorithm itself is very similar to the original push-sum method, but the analysis in the new framework also turns out to be challenging. Moreover, I also find the papers to be well-written and easy to follow, despite the complexity of the underlying setup.\n\nOne potential concern is that the online learning part seems to be missing from the experimental section. In fact, it is not specified how the loss sequence is generated and how and when a learner is selected for making a prediction. Without the latter information, I do not really know what time measures in Figure 1. Moreover, how can we ensure that this difference is caused by the implementation of the algorithms? As for the losses, I imagine that samples are sampled uniformly at random. Indeed, stochastic optimization is frequently viewed as a special case of online learning (notably through online-to-batch conversion), but these experiments do not justify the choices to focus on the online framework. Similarly, the authors plot the average loss and not the (average) regret for the experiments.\n\nOther remarks:\n\n1. Pointing the readers to appendix B at the bottom at page 5 can be helpful, since, as claimed by the authors, the feasibility of the methods is not that immediate. Similarly, pointing the readers to the appendix for the complete pseudo-code can also be helpful.\n\n2. With Assumption 1, I believe it always holds $D^{proc}\\le\\Gamma_{d}T$.\n\n3. $\\boldsymbol{\\hat{g_t}}$\ndepends on the choice of $j$ and I recommend explicating this in the notation (such as $\\hat{\\boldsymbol{g}}_{j,t}$).\n\n4. Adding dashed lines in Figure 1 can help illustrate the fact that the two algorithms achieve the same average loss.\n\n5. [Hsieh et al. 2020](https://arxiv.org/abs/2012.11579) also studies asynchronous decentralized online optimization, though through a totally different approach. I suggest the authors include it in related work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations are discussed in the conclusion. Another limitation that I find about this work is that the learners cannot make predictions when they are occupied by the computation of the gradients. This is slightly different from the usual delayed online learning setup [Quanrud and Khashabi 2015](https://papers.nips.cc/paper/2015/file/72da7fd6d1302c0a159f6436d01e9eb0-Paper.pdf).", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LBZVAZDqbP", "reviewer": "Reviewer_ec5A", "summary": "In this paper, authors propose asynchronous algorithm for convex optimization in decentralized distributed model. In contrast with other algorithms, the averaging procedure is asymmetric that leads to faster convergence comparing to the synchronous updates.", "questions": "", "limitations": "", "rating": 7, "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": "In this paper, authors consider distributed decentralized model with asynchronous communication between nodes. However, in this setup there is no one to one correspondence between nodes and loss functions.\nFirst, authors explain their framework that is following: 1) some learner(node) is selected to predict with its own predictions. 2) some loss function is sent to the learner to calculate the gradient. 3) learner shares its update with some of the neighbors. 4) then all learners, who are not busy (see calculating the gradient) are performing the model averaging.\n\nThis setup allows to solve the common problem of synchronous algorithms, when some machine can be slow and all the others should wait for it to finish to perform their updates.\n\nThen authors present the weighted projected online gradient descent that is based on the push-sum communications: instead of using doubly stochastic gossip matrix for averaging only the column stochasticity is required. \n\nThen authors describe the main contribution of the work; however it is hard to follow since there is no algorithm in the paper. Furthermore, I was lost in the theoretical result.\n\nIn the experimental part, authors provide the comparison of the symmetric and push-sum algorithm that proves the interest of push-sum algorithm for big delays that makes the asymmetric gossiping more robust. However, I think that this comparison is not good enough and some other algorithms should be added. Furthermore, some additional figures were provided to show the dependence of the efficiency of the push-sum algorithm of network size, network topology, and delays. Actually, I missed the message of these plots since I find these comparisons quite useless. Moreover, these plots are not colorblind-friendly so it was impossible for me to read them.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"ethical_concerns": "no", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1-2 hour"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agree that this generally a good paper although not entirely without (minor) flaws. Please take the reviewers comments in consideration when preparing a revision. The answers provided by the authors were given due consideration. 
Decision: Accept (Poster)