DADAO: Decoupled Accelerated Decentralized Asynchronous Optimization
Authors: Adel Nabli
Edouard Oyallon
Venue: Submitted to ICLR 2023 (2023)
Keywords: Decentralized Asynchronous Optimization
Convex Optimization
Time-Varying Networks

Abstract: DADAO is a novel decentralized asynchronous stochastic first order algorithm to minimize a sum of $L$-smooth and $\mu$-strongly convex functions distributed over a time-varying connectivity network of size $n$.  We model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, decoupling the computation and communication steps in addition to making the whole approach completely asynchronous. Our method employs primal gradients and does not use a multi-consensus inner loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or a Proximal operator. By relating the inverse of the smallest positive eigenvalue $\chi^*_1$ and the effective resistance $\chi_2^*$ of our graph to a necessary minimal communication rate between nodes of the network, we show that our algorithm requires $\mathcal{O}(n\sqrt{\frac{L}{\mu}}\log \epsilon)$ local gradients and only  $\mathcal{O}(n\sqrt{\chi_1^*\chi_2^*}\sqrt{\frac{L}{\mu}}\log \epsilon)$ communications to reach a precision $\epsilon$. If SGD with uniform noise $\sigma^2$ is used, we reach a precision $\epsilon$ with same speed, up to a bias term in $\mathcal{O}(\frac{\sigma^2}{\sqrt{\mu L}})$. This improves upon the bounds obtained with current state-of-the-art approaches, our simulations validating the strength of our relatively unconstrained method.

Under review as a conference paper at ICLR 2023
DADAO: DECOUPLED ACCELERATED DECENTRALIZED ASYNCHRONOUS OPTIMIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
DADAO is novel decentralized asynchronous stochastic first order algorithm minimize a sum of L-smooth and jı-ttrongly convex functions distributed over a time-varying connectivity network of size n. We model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, decoupling the computation and communication steps in addition to making the whole approach completely asynchronous. Our method employs pri- mal gradients and does not use a multi-consensus inner loop nor other ad-hoc mechanisms such Error Feedback, Gradient Tracking, Proximal operator. By relating the inverse of the smallest positive eigenvalue xi and the effective resistance X2 of our graph to necessary minimal communication rate between nodes of the network, we show that our algorithm requires (n (l) local
gradients and only D(n/xixxs glog( communications to reach precision c. If SGD with uniform noise o² is used. we reach a precision with same speed, up to a bias term in O (ur) (( This improves upon the bounds obtained with current state-of-ther of-the--rttttttt approaches, our simulations validating the strength of our relatively unconstrained method.
INTRODUCTION
With the rise of paghly-parlllllizable and connected hardware, distributed optimization for machine learning is a topic of significant interest holding many promises. In a typical distributed training framework, the goal is to minimize a sum of functions (ft)egn split across n nodes of computer network. A corresponding optimization procedure involves alternating local computation and com- munication rounds between the nodes. Also, spreading the compute load is done ideally obtain linear speedup in the number of nodes. In the decentralized setting, there is no central machine aggregating the information sent by the workers: nodes are only allowed to communicate with their neighbors in the network. In this setup, optimal methods (Scaman et al., 2201 7g Kovalev et al (02 have been derived for synchronous first-order algorithms, whose executions are blocked until a sub- set (or all) nodes have reached a predefined state: the instructions must be performed in specific order (e.g., all nodes must perform local gradient step before the round of communication begins), which is one of the locks limiting their efficiency practice.
This work attempts to simultaneously address multiple limitations of existing decentralized algo- rithms while guaranteeing fast convergence rates. To tackle the synchronous lock, rely on the continuized framework (Even et all 202 introduced initially to allow asynchrony in a fixed topol- ogy setting: iterates are labeled with continuous time index (in opposition to a global iteration count) and performed locally with no regards to a specific global ordering of events. This is more practical while being theoretically grounded and simplifying the analysis. However, in Even et all (2021a), gradient and gossip operations are still coupled: each communication along an edge re- quires the computation of the gradients of the two functions locally stored on the corresponding nodes and vice-versa. As more communications steps than gradient computations are necessary to reach an é precision, even in an optimal framework (Kovalev et all 202 Scaman et all 2017), the coupling directly implies overload in terms of gradient steps. Another limitation is the restric- tion to fixed topology: in a more practical setting, connections between nodes should be allowed to disappear ones appear over time. The procedures of Kovalev et al. (2021c): Li & Lin

---

Under review as a conference paper at ICLR 2023
(2021) are the first obtain optimal complexity in gradient steps while being robust to topolog- ical change. Unfortunately, synchrony mandatory in their frameworks as they either rely on the Error-Feedback mechanism (Stich & Karimireddy, 2020) or the Gradient Tracking one (Nedic et all 2017). Moreover, they both use an inner loop to control the number of gradient steps at the cost of significantly increasing the number of activated communication edges. To our knowledge, this is the first work to tackle those locks simultancously.
In this paper, we propose novel algorithm (DADAO: Decoupled Accelerated Decentralized Asyn- chronous Optimization) based on a combination of similar formulations to Kovalev et al (2021a); Even et al. (2021b) Hendrikx (2022) in the continuized framework ofEn al. (2021a). We study:
inf ZER
Σ f(())
where each R&d R is ju-strongly convex and L-smooth function computed in of the n nodes of a network. We derive a first-order optimization algorithm that only uses primal gra- dients and relies on a time-varying Point-wise Poisson Processes (P.P...s (Last & Penrose. 2017h) modeling of the communication and gradient occurrences, leading to accelerated communication and computation rates. Our framework is based on a simple fixed-point iteration and kept mini- mal: it only involves primal computations with an additional momentum term and works in both the Gradient and Stochastic Gradient Descent (SGD) settings. Thus, we do not add other cumbersome designs such as the Error-Feedback or Berward-Bacwward used in Kovalev et al. (202 which are intrinsically synchronous. While we do not consider the delays bound to appear in practice (we as- sume instantaneous communications and gradient computations), gradient and gossip steps can be variable, removing the coupling lock.
show that the ordering of the
Our contributions are follows: (1) first, we propose the first primal algorithm with provable guarantees in the context of asynchronous decentralized learning with vire-ng connectivity. (2) This algorithm reaches accelerated rates of communication and computations while not requiring ad- hoc mechanisms obtained from an inner loop. (3) Our algorithm also leads to an accelerated rate (4) We propose simple theoretical framework compared to concurrent works, and (5) we demonstrate its optimality numerically.
with SGD with minor modification.
The structure of our paper is follows: in Sec.
describe work hypothesis and model of a decentralized environment, while Sec. 3.2 describes our dynamic. Sec. 3.3 states our convergence guarantees whose proofs are fully detailed the Appendix. Then, Sec. compares our work with its competitors, Sec. 4.2 4.2 explains our implementation of this algorithm, and finally, Sec. 4 verifies our claims numerically. All our experiments are reproducible, using PyTorch (Paszke et al. 2019) and our code can be found in Appendix.
3.1
2 RELATED WORK
Tab. I compares our contribution with other references to highlight the benefits of our method.
Table This table shows the strength of DADAO compared to concurrent works. n is the number of node, |8| the number of edges, X1 the smallest positive eigenvalue of fixed stochastic Gossip matrix, P the eigengap and X2 X1 the effective resistance. Note that under reasonable assumptions VXiX2n = ((ElVp) (Sec. D. D. Async., Comm., Grad., M.-C. and Prox. stand respectively for Asynchrony, Communication steps, Gradient steps., Multi-consensus and Proximal operator.
Method
Asyne.
Varying Topology
Decoupled
Inner Loop (M.-C. or Prox.)
Total
Orccle
# Comm.
# Grad
MSDA (Scaman et al., 2017)
X
VAE
AGT (Li & Lin, 2021)
X
X
xale|
ADOM+ (Koaaeev et al, 2021a)
X
X
X
/
xale
Continuized (Even et al., 2021a)
X
V
x
VXIxa
VXixan
ADES (Hendrika al, 2021)
X
d
X
vÆEly
(Hendrix,, 2022)
Al
DADAO (ours)
V
vxuxam
2

---

Under review as a conference paper at ICLR 2023
Continuized and asynchronous algorithms. We highly rely on the elegant continuized frame- work (Even et all 2021a)), which allows obtaining simpler proofs and brings the flexibility of asyn- chronous algorithms. However, in our work, we significantly reduce the necessary amount of gra- dient steps compared to Even et all (2021a) while maintaining the same amount of activated edges. Another type of asynchronous algorithm Nesterov's 's accelerated rates for lack of momentum. We note that Leblond et al. (2018) studies the robustness to delays yet requires shared memory and thus applies to a different context than decentralized optimization. Hendrikx (2022) is promising approach for modeling random commu- nication on graphs yet fails to obtain acceleration in a neat framework that does not use inner-loops.
also be found in Latz (2021). yet it fails to obtain
Decentralized algorithms with fixed topology. Scaman et al. (201 2017)> is the first work to derive an accelerated algorithm for decentralized optimization, and it links the convergence speed to the Laplacian eigengap. The corresponding algorithm uses dual formulation and Chebychev accel- eration (synchronous and for a fixed topology). Yet, as stated in Tab. 2 still requires many edges to be activated. Furthermore, under relatively flexible condition on the intensity of our P.P.P.s, show that our work improves over bounds that depend on the spectral gap. An emerging line of work following this formulation employs the continuized framework (Even et all 2020; 2021 b), but is unfortunately not amenable to incorporating a vime-narying topology by essence, as they rely on a coordinate descent scheme in the dual (Nesterov Stich, 2017). Finally, we note that Even et all 2b incorporates delays in their model, using the same technique as our work, yet transferring this robustness to another setting remains unclear. Reducing the number of communication has been studied in Mishchenko et al. (2022). only in the context of constant topology and without obtaining accelerated rates. Hendrikx et all (2021) allows for fast communication and gossip rates yet requires a proximal step and synchrony between nodes to apply momentum variable.
Decentralized algorithms with varying topology. We highlight that Kovalev et al. 12)
Li Lin 1202)); Koloskova et al. 2020) are some of the first works propose framework for decentralized learning in the context of varying topology. However, they rely on inner-loops prop- agating variables multiple times through a network, which imposes complete synchrony and com- munication overheads. In addition, as noted empirically in Lin et al (2015), inner-loops lead to a plateau effect. Furthermore, we note that Kovalev et al. (2021b); Salim et al (2021) employ a formulation derived from Salim et al. (2020); Condat et al (2022). casting decentralized learning as a monotonous inclusion, obtaining linear rate thanks to a preconditioning step of a Forward- Backward like algorithm. However, being sequential by nature, these types of algorithms are not amenable to continuized framework.
Error feedback/Gradient fracking. A major lock for asynchrony is the of Gradi- ent Tracking (Koloskova et al. 2021; Nedic et al. 2017: & (021) or Error Feed- back (Stich & Karimireddyl 2020 Kovalev et all 20211). Indeed, gradient operations are locally tracked by a running-mest mean variable which is updated at each gradient update. This is incompati- ble with asynchronous framework as it requires communication between nodes. Furthermore, multi-consensus inner-loop seems mandatory to obtain accelerated rates, again not desirable.
Decoupling procedures Decoupling subsequent steps of an optimization procedures traditionally leads to speed-ups (Hendrikx et all, 2021] [Hndrikx (2022 Belilovsky et al., 2020 (021). This contrasts with methods which couple gradient and gossip updates, such that they happen in a predefined order, i.e. simultaneously (Even et all (202 or sequentially (Kovalev et al. 202 Koloskova et all (020). In decoupled optimization procedures, inner-loops are not desirable because they require an external procedure that can be potentially slow and need block-barrier instruction during the algorithm's 's execution C.g...Henrrike et al. 20211 2019)).
3 FAST ASYNCHRONOUS ALGORITHM FOR TIME- VARYING NETWORKS
3.1 GOSSIP FRAMEWORK
We consider the problem defined by Eq. Min distributed environment constituted by nodes whose dynamic is indexed by a continuous time index t E R Each node has a local memory and can compute local gradient V.J, as well as elementary operations, in instantaneous manner. As
3

---

Under review as a conference paper at ICLR 2023
said above, having delay is less realistic, yet adding them also leads to significantly more difficult proofs whose adaptation to our framework remains largely unclear. Next, we will assume that our computations and gossip result from independent in tn-homogeneous piecewise constant P.P.P. with no delay. For the sake of simplicity, we assume that all nodes can compute a gradient at the same rate:
Assumption 3.1 (Homogeneous gradient computations). The gradient computations are re- normalized to fire independently at a rate of I computation per time unit. For the i-th worker, we write Nt( the corresponding P.P.P. of rate as well as N(t) (N,(t))sg.
Next, we model the bandwidth of each machine. For edge (i.j) E Et), we write Mty(t) the P.P.P. with rate (t) 2 O. When this P.P.P. fires, both nodes can potentially share their local memories. The rate Xe (t) adjustable locally by machine which can decide to speed or slow down its local communication. While (t) and (t: may refer to different quantities, we highlight that this communication process is symmetrie, and we denote by {t) the corresponding undirected graph. Given our notations, we note that if (i.j) & {t),, then the connexion between (i,j) can be thought as P.P.P. with intensity O. We now introduce the instantaneous expected gossip matrix of our graph:
A(t) &
Σ (L)))E()
Ae((t(e -e)((e - -
We also write (1) - ((S)EEE()) Ag(()(e; e,)(e; -e,) its tensorized counter-par that will be useful for our proofs and defining our Lyapunov potential, and A + (f) its pseudo inverse. Following Scaman et al. (2017), we will further compare this quantity to the centralized gossip matrix:
1
-11
e - -
ee
n
2n
We introduce the instantaneous connectivity of A(t), as in Kovalev et al. 2202
1 A inf -1 x A(t)a
(I)
We might also write X1 [t)) to avoid confusion, depending on the context. Next, we introduce the maximal effective resistance of the network, in Even al. 2021a) Ellens et al (001)):
X2 (t A
sup (e: (G=-e)"A(((GG-- -c) (1.))E(()
We remind the following Lemma (proof in Appendix D.2), which will be useful to control (1), Xt(t) and compare our bounds with the ones making use of the spectral gap of graph:
Lemma 3.1 (Bound on the connectivity constants). The spectrum of A(t) non-negative. Further- more, have Xi (t) +o0 E(L) is not connected graph. Also, if the graph is connected, then n-1 S min(xi (1), x2())) Furthermore, we also have 2x2 inf Aig(t) < 1. TrA
The last part of this Lemma allows to bound Xz(t) when no degenerated behavior on the graph's connectivity happens: we assume the networks not contain arbitrarily slow communication edges. The following assumption is necessary to avoid oscillatory effects due to the variations of A(():
Assumption 3.2 (Slowly varying graphs). Assume that A(t) is piece-wise constant on time intervals.
In particular, it implies that each (t) is pisce-wise constant. Next, following Kovaley et all (0021a), we bound uniformly the connectivity to avoid degenerated effects:
Assumption 3.3 (Strongly connected topology). Assume that there is xi > Ouch that (i $ xi-
We might write this quantity [A] to stress the dependency in A(t). From supra, it's clear that xt( S (1) so that under 3.3 x2( () is upper bounded by X2 xi-
4

---

Under review as a conference paper at ICLR 2023
3.2 DYNAMIC TO OPTIMUM
Next, we follow a standard approach (Kovalev et al. 2021 caa Salim et all 2022: Hendrikx 2022) for solving Eq. (see Appendix for details), leading to, for 0 < v < pr:
1 (...) 2 [|=]l² (x, v)
inf aERd For F(x) - f((z;) - || the saddle points ,0,,"") of this Lagrangian, are given by:
fi(x)=
inf zERuxd V.
sup
|1 vl12.
2v
(F(x") '¹ =0 5/ +m=" + x
TV
0.
Contrary to Kovalev et al. (2021a), we do not employ a Forward- harrddBawwwrdd algorithm, which re- quires both an extra-inversion step and additional regularity on the considered proximal operator. Not only does this condition not hold in this particular case, but this is not desirable in a continuized framework where iterates are not ordered in predefined sequence and require local descent each instant. Another major difference is that no Error-feedback is required by our approach, which allows to unlock asynchrony while simplifying the proofs and decreasing the required number of communications. Instead, we show it is enough to incorporate a standard fixed point algorithm, without any specific preconditioning (see Condat et all (2019)) We consider the following dynamic:
dx. = Tf(ā; xx)dd - ((.))) - 9.) (N)
dē; T( -t (V)(()) 5.) dN
dğ A(ye 2t + vī + +6 ())()((())) (.)
(3)
dy: = aUr yt)
dz, = a(, dt - (essesso - e,)(c, ej) + 21 (ty) (v)
dž, = a(z; ddll - Eosseero) - e,) o5)
+ e
(1)
where v, ñ. 1) Y, a, a, 0, 0, 3 are undetermined parameters yet. As in Nesterov (203)), variables are paired to obtain a Nesterov acceleration. The variables (I, y) allow decoupling the gossip steps from the gradient steps using independent P.P.P.s. Furthermore, the Lebesgue integrable path of tht does not correspond to a standard momentum, as in a continuized framework (Even et al 2021 however, turns out to be crucial component of method. Compared Kovalev et 1 no extra multi-consensus step needs to be integrated. Our formulation of an asynchronous gossip step similar Even et al] (2021a) which introduces stochastic variable on edges; however, con- trary to this work, our gossip and gradient computations are decoupled. In fact, we can also consider SGD (Bottou, 2010), by replacing V F(x) by an estimate F(,, E), for & E E, some measurable space. We will need the following assumption on the bias and variance of the gradient:
Assumption 3.4 (Unbiased gradient with uniform additive noise). We assume that:
F { = VF(x),
and that its quadratic error is uniformly bounded by > 0:
E3 (= (F())|
Next, for SGD use, we modify the three first lines of Eq. 3 replacing the stochastic terms (VF(x;;- úe) dt) by FL(VF(( ūt) (t. {). see Appendix C for the complete dynamic. Simulating those SDEs (Amold, 1974) can be efficiently done, explained in Sec. 4.2 and Appendix
3.3 THEORETICAL GUARANTEES
We follow the approach introduced in Even et al. 2021a) for studying the convergence of the dy-
namic 3
To do so, we introduce X (a, ã. 0), Y
(y, 2, ă) and the following Lyapunov potential:
(1, Y) A Ardr(1, + Å.
x x=1 B, 1ly - 112 B.lli " 112
+ G+ll= + -- - y 1|2 + C+ = =1
5

---

Under review as a conference paper at ICLR 2023
where A,, Bi, Ct, C.. Dr are non non-negative functions to be defined. We will use this potential to control the trajectories of X, - (2t, Tt, Bt), Y, _ (yt, 2e, žt), leading to the equivalent dynamic: dX; a1 i dt + by (X))dN
dY, = o, di + [(s)EEE by (Y))d,;(())
where 01, 02. bj = ): (62) )5 are smooth functions. We prove the following in Appendix D.3
Theorem 3.2 (Gradient Descent). Assume each fi is p-strongly corvex and I-smooth. For any
(t), assume 3.7 3.3 and that xi[A]xž[A] S Then there exists some parameters for the dynamic
Eq. 3 (given in App.
such that for any initialization Tu E Rdd and To Fo, Yo Do
(rn); 20 30
n V (1O),, we get gor RR+ and [(x) = Ei S((xi):
E[f(zd f(x') S (2(f(zo)- - f(x")) + 8 + -1 I stEVE.
Also, the expected number of gradients is vul and the expected number of edges activated is: %///
)u(u) du) 1 f/" A(]]] du.
B
Σ
(1.))
We can obtain the following corollary with a minor modification of our current proof: Corollary 3.2.1 (SGD with additive noise). Under the same assumption as Thm. 3.2 as well as 3.4 for the SGD- D-D-dynamic Eq. & the same parameters Thm. 3.2]allows obtain for E Rt:
([(()))-(()) s (2(((r)) - f(=))) + 1 8 |0o x*1))e
BUT V
50²
VuL
Following Even et all (2021a), allows to adjust the trace-off bias-variance of our descent.
4 PRACTICAL IMPLEMENTATION
4.1 EXPECTED COMPUTATIONAL COMPLEXITY
For a given graph (t), multiple choices of (t) are possible and would still lead accelerated and linear rates as long as the condition 2x1 [x][A|]]A)) < 1 is verified. Thus, we discuss how to choose our instantancous expected gossip matrix to compare to concurrent work. To get a precision
C,
- /lo/lll())) local gradient computations is required per machine. More details can be found in Appendix F on our methodology for comparing with other methods, and particularly the way to recover the order of magnitudes we mention. In the following. each algorithm to which we compare ourselves is parameterized by Laplacian matrix with various properties. Systematically, for an update frequency f and a family of Laplacians (Lg), (which can be potentially reduced to a single element) given by concurrent work, will set:
= TT=
(tt) v 2x1[5)x3(4AAun A ((r)
(5)
where X* can be understood as a lower bound on the instantaneous expected communication rate. In this case, A(t) satisfies the conditions of Theorem 3.2 or Corollary 1..2. From a physical point of view, it allows us to relate the spatial quantities of our graphs to a necessary minimal communication rate between nodes of the network; see Appendix [ for a discussion on this topic.
Comparison with ADOM+. In ADOM+ Kovaley all 2021a), one picks xi(4) 2 and f Xi(C). Then, the number of gossip steps of our algorithm is at most:
L
log( ) = XVxx44xx111 (loett)
Vxi(4)x((4 sup Tr(Cg)
Then, the expected communication of ADOM+ is potentially substantially higher than ours (see Appendix[.I F.I.
T
xi(C]1801 2 ol ol 1)

---

Under review as a conference paper at ICLR 2023
Comparison with standard Continuized. If L is Laplacian picked such that Tr L 2 (thus f = -O, as in Even et al. (2021a), then Even et al. (2021a) claims that at least Ol (oooogt)
gradient and gossip iterations are needed. The number of gossip it- erations is the same as ours, yet, thanks to Lemma 3.1 the number of gradient iterations can be substantially higher without any additional assumptions, as 1 S 2 2 (see Appendix F22. Furthermore, the computations of Even al. (2021a) still use the dual gradients and are for fixed topology.
Comparison with methods that depend on the spectral gap. For instance, MSDA relies on Tchebychev acceleration of the number of gossip steps (possible because because(Scaman Scaman et al (011)) uses fixed gossip matrix) which allows getting the number of edges activated of about / log( ) where p² is the spectral gap. For our algorithm, the number of gossip writes (with = 0):
V 1 S
L
log( ()))
OlV olvorll
where the details of this bound can be found in Appendix F.3 3 and relies solely on an assumption on the ratio between the maximal and minimal weights in the Laplacian. We highlight tcamann et al. (2017): Kovalev et all (2021a) claimed that their respective algorithms are optimal because they study the number of computations and synchronized gossips on a worst-case graph; our claim is, by nature different, we are interested in the number of edges fired rather than the number of synchronized gossip rounds. Tab. 2 predicts the behavior of our algorithm for various classes of graphs encoded via the Laplacian of stochastic matrix. It shows that systematically, our algorithm leads to the best speed"] We note that the graph class depicted in the Tab. 2 were used as worst- case examples of Scaman et al. (2017); Kovalev et all (2 The next section implements and validates our ideas.
Table 2: Complexity for various graphs using a stochastic matrix. We have, respectively for star / line cyclic/ complete graph and the d-dimensional grid: xi -(1), p (()) xi O(n²). O(?)), X5 0(1) 0(1), 0(1) xi (/2), p O(2 X2 0(1)
Method
# edges activated
total gradient iterations
Graph
Star
Line
Complete
d-grid
Star
Line
Complete
d-grid
(Kovalev et al, 202 ADOM+
71
71
rt²
n 1424
n
71
Seaman al. 2017) MSDA
n/22
n1
n22
n 1+//
(venn al. 2021a) Continuized
72
2
73
1+//
n
n1
73
n
1+1/d
Centralized
71
DADAO (ours)
71
222
4.2 ALGORITIIM
We now describe the algorithm used to implement the dynamics of Eq. and, in particular, simulator of P.P.P. Let us write ( < IT(") <.. < T( < the time of the k-th event on the i-th node, which is either an edge activation, either a gradient update. We remind that the spiking times of a specific event correspond to random variables with independent exponential increments and can thus be generated at the beginning of our simulation. They can also be generated on the fly and locally to stress the locality and asynchronicity our algorithm. Let's write X, (x!")) and Y, (Y(1)) );, then the i-th node and at the k-th iteration, integrate the linear Ordinary { [dx; a1 (X,, Yi)dt
Differential Equation (ODE) on ( 2414 given by dY, = a2 Xx, Y.)di'
to define the values
right before the spike, for A the corresponding constant matrix, thus have:
= exp (T T(e) T())
2009
(6)
For the case 2-grid, the logarithmic term should appear, yet decided to neglect them.
7

---

Under review as a conference paper at ICLR 2023
Next, if one has gradient update, then:
x 24
-x +
b1
(x
T(())
Otherwise, if the edge (i.j) or (j, i) is activated, a communication bridge is created between both nodes and j. In this case, the local update on writes:
yl T
y(( T
y
yr T.
b2
T.
Note that, even if this event takes place along edge (i.j), and j by making sure they both have events T(()) = TT(), for some ki k E N, corresponding to this communication. As advocated, all those operations are local, and we summarize in the Alg. [ the algorithmic block which corresponds to implementation. See Appendix H for more details.
write it separately for nodes i
Algorithm 1:
This algorithm block describes our implementation on each local machine. The ODE routine is described by Eq. 6 and Ping is instantaneous routine.
Input: On each machine i E {1...., n1., gradient oracle fi. parameters μ., L, Xi max Initialize on each machine E [[..... n.::
Set ( ( T() to and set AA via Eq. 105
Synchronize the clocks of all machines;
In parallel on workers E {l,..., n.. while < fmax continuously do:
+ clock();
Ping surrounding machines and adjust Aty(t); if there an event at time then (X(), Y ODE(E,, T(), (X19, Y())
the event to take a gradient step then X(1) +x(+) + by (x(()))
10
else if the event is communicate with then
(() -- ( + (
// нapрens at j simultancously.
TW)) t1;
14 return tomas Disign the estimate of x² each worker i.
4.3 NUMERICAL. RESULTS
In this section, we study the behavior of our method and compare it to several settings inspired by Kovalev al. (2021a); Even et al. (2021a). In our experiments, we perform the empirical risk minimization for both the decentralized linear and logistic regression tasks given either by:
m
1 m m
f((x)
Σ log(1 + exp(- (1)3))))))))) + m ;=1
1 |= or f((x)
Σ
Ia
Giyli
(7)
where diy E Rdd bij E 1-1,1] and Gj R correspond to local data points stored at node For both varying and fixed topology settings, we follow a protocol similar to Kovalev et all (202aa): we generate n independent synthetic datasets with the make_classifice cassificaiion and make_ reke__regresion functions of seikit-leam (Pedregosa et all (211)) each worker storing m = 100 data points. We recall that the metrics of interest are the total number of local gradient steps and the total number of individual messages exchanged (i.e., number of edges that fired) to reach an e-precision. We systematically used the proposed papee-prrraeters of each reference paper for our implementation without any specific fine-tuning.
Comparison in the time-varying setting. We compare our method to ADOM+ Kovaley et all 2021a) on sequence of 50 random geometric graphs of size 20 in Fig. II To construct the graphs, we sample n points uniformly in [0, 1]2 C. IR² and connect each them to all at a distance less than some user-specified radius, which allows controlling the constant xi (we consider values in
8

---

Under review as a conference paper at ICLR 2023
{3, 33, 180, 233)). We ensure the connectedness of the graphs by adding minimal number of edges. exactly as done in Kovalev et al. (202 We then use the instantaneous gossip matrix introduced in Eq. [5] with = Xi- We compare ourselves to both versions of ADOM+: with and without the Multi-Consensus (M.-C.). Thanks to its M.-C. procedure, ADOM+ can significantly reduce the number of necessary gradient steps. However, consistently with our analysis in Sec. 4.1 our method is systematically better in all settings in terms of communications.
Average distance
Average distance opt.
Average opt.
Average distaroee
10"
10"
10
ADOMI M.-C
10"
10"
10"
10"
ADOM- DADAO
10"
16
10
16
15
10"
20000
40303
0.0
0.5
1.0
20000
40000
0.0
0.5
1.0
Total number grad.
Total rumber of comfes
Totai number of grad.
Total number of comd 66
Figure 1: Comparison between ADOM+ (oovlev et al. 2021a) and DADAO, using the same data from left to right: binary classification, linear regression) and the same sequence of random con- nected graphs with xi 180 linking n = 20 workers.
Comparison with accelerated methods in the fixed topology setting. Now, fix the Laplacian matrix via Eq. [ to compare simultaneously to the continuized framework (Even et al. 2021a) and MSDA (Scaman et al. 2017h. We reports in Fig. 2 results corresponding to the complete graph
with n = 250 nodes and the line graph of size n = 150. While sharing the same asymptotic rate, we note that the Continuized framework (Even al 2021a) and MSDA (Scaman all 2017) have better absolute constants than DADAO, giving them an ad advantage both in terms of the number of communication and gradient steps. However, in the continuized framework, the gradient and communication steps being coupled, the number of gradient computations can potentially be orders of magnitude worse than our algorithm, which is reflected by Fig. for the line graph. As for MSDA and ADOM+, Tab. D showed they do not have the best communication rates on certain classes of graphs, as confirmed to the right in Fig. for MSDA and the communication plots for ADOM+.
distance
Average cistance
10"
10"
10'
ADOW- M.C.
Do- x
10"
10"
ADOM- Continuzed MEDDA
10
10
-l/710 10
<WV7
10
10
10
10
10"
16"
100200
200000
0.5 Total number of conde?
100000
200000
0.5
1.0
Total number grad.
Total numoer grad.
Total number cont
Comparison between ADOM+ Kovalev et al., 2021a), the continuized framework (Even et all (021a), MSDA (Scaman et all 2017) and DADAO, using the same data for the linear regression task, and the same graphs (from left to right: line with n 150, complete with 250).
Figure 2:
In conclusion, while several methods can share similar convergence rates, ours is the only one to perform at least as well as its competitors in every setting for different graph's topology and two distinct tasks, as predicted by Tab.
CONCLUSION
In this work, we have proposed novel stochastic algorithm for the decentralized optimization of sum of smooth and strongly convex functions. We have demonstrated, theoretically and empirically, that this algorithm leads systematically to a substantial acceleration compared to state-of-the-as works. Furthermore, our algorithm is asynchronous, decoupled, primal, and does not rely on an extra loner-loop while being amenable to varying topology settings: each of these properties makes suitable for real applications. In future work, we would like to explore the robustness of such algorithms to more challenging variabilities occurring in real-life applications.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ludwig Arnold. Stochastic differential equations. New York, 1974.
Eugene Belilovsky, Michael Eickenberg, and Edouard Oyallon. Decoupled greedy learning of CNNs. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 736-745.
PMLR, 13-18 Jul 2020.
Eugene Belilovsky, Louis Leconte, Lucas Caccia, Michael Eickenberg, and Edouard Oyallon. De- coupled greedy learning of cnns for synchronous and asynchronous distributed learning. arXiv preprint arXiv:2106. 06401, 2021.
Léon Bottou. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010, pp. 177-186. Springer, 2010.
S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Transactions on Information Theory, 52(6):2508-2555 22300, 2006. doi: 10.1 1t..10099...200.874444444. 874516.
Laurent Condat, Daichi Kitahara, Andrés Contreras, and Akira Hirabayashi. Proximal splitting algorithms for convex optimization: A tour of recent advances, with new twists, 2019.
Laurent Condat, Grigory Malinovsky, and Peter Richtárik. Distributed proximal splitting algorithms with rates and acceleration. Frontiers in Signal Processing, pp. 12, 2022.
Wendy Ellens, Floske M Spicksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E Kooij. Effective graph resistance. Linear algebra and its applications, 435(10):2491-2506, 2011.
Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié. Asynchrony and acceleration in gossip algorithms, 2020.
Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Hadrien Hendrikx, Pierre Gail- lard, Laurent Massoulié, and Adrien Taylor. A continuized view on nesterov acceleration for stochastic gradient descent and randomized gossip. A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a.
Mathieu Even, Hadrien Hendrikx, and Laurent Massoulie. Decentralized optimization with hetero- geneous delays: a continuous approach. arXiv preprint arXiv:2106.03585, 2021b.
Hadrien Hendrikx. A principled framework for the design and analysis of token algorithms, 2022.
Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. An accelerated decentralized stochastic proximal algorithm for finite sums. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buu E. Fox, and Garnett (eds.), Advances Neurul Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Hadrien Hendrikx, Francis Bach, and Laurent Massoulié. An optimal algorithm for decentralized finite-sum optimization. SIAM Journal on Optimization, 31(4):2753-2783 2021. doi: 10.1137/ 20M134842X.
Douglas Klein and Milan Randic. Resistance distance. Journal of Mathematical Chemistry, 12: 81-95, 12 1993. doi: 10. 10.10//
Anastasia Koloskova, Nicolas Loizou, Sadra Boreiri, Martin Jaggi, and Sebastian Stich. unified theory of decentralized sgd with changing topology and local updates. In International Confer- ence on Machine Learning, pp. 5381-5393. PMLR, 2020.
Anastasiia Koloskova, Tao Lin, Sebastian Stich. An improved analysis of gradient tracking for decentralized machine learning. Advances in Neural Information Processing Systems, 34: 11422-11435, 2021.
Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtárik. Lower bounds and op- timal algorithms for smooth and strongly convex decentralized optimization over time-varying networks. In A. Beygelzimer, Y. Dauphin. P. Liang, and Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, 2021a.
10

---

Under review as a conference paper at ICLR 2023
Dmitry Kovalev, Alexander Gasnikov, and Peter Richtárik. Accelerated primal-dual gradient method for smooth and arXiv:2112.15199 2021b.
saddle-point problems with bilinear coupling. arXiv preprint
Dmitry Kovalev, Egor Shulgin, Peter Richtárik, Alexander V Rogozin, and Alexander Gasnikov. Adom: accelerated decentralized optimization method for time-varying networks. In Interna- lional Conference on Machine Learning, pp. 5784-5793, PMLR, 2021c
Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7. Cambridge University Press, 2017.
Jonas Latz. Analysis of stochastic gradient descent in continuous time. Statistics and Computing, 31(4):1-25, 2021.
Rémi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien Improved asynchronous parallel opti- mization analysis for stochastic incremental methods. arXiv preprint
2018.
Huan Li and Zhouchen Lin. Accelerated gradient tracking over time-varying graphs for decentral- ized optimization. arXiv preprint arXiv:2104. 02596, 2021.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. universal catalyst for first-order optimization.
Advances in neural information processing systems, 28, 2015.
Konstantin Mishchenko, Grigory Malinovsky, Sebastian Stich, and Peter Richtárik. Proxskip: Yes!
local gradient steps provably lead to communication acceleration! finally! arXiv preprint 09935 2022.
Angelia Nedic, Alex Olshevsky, and Wei Shi. Achieving geometric convergence for distributed optimization over time-varying graphs. SIAM Journal on Optimization, 27(4):2597-2333, 2017.
Yurii Nesterov. Introductory lectures on convex optimization: A basic course, volume 87, Springer Science & Business Media, 2003.
Yurii Nesterov and Sebastian Stich. Efficiency of the accelerated coordinate descent method on structured optimization problems. SIAM Journal on Optimization, 27(1):110-12) 2017.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vetito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang. Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Bus Buc. E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 8024 8035. Curran Associates, Inc., 2019.
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
Adil Salim, Laurent Condat, Konstantin Mishchenko, and Peter Richtárik. Dualize, split, randomize: Fast nonsmooth optimization algorithms. arXiv preprint arXiv:2004.00 02635, 2020.
Adil Salim, Laurent Condat, Dmitry Kovalev, and Peter Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. arXiv preprint arXiv:2 /02./ 1079, 2021.
Adil Salim, Laurent Condat, Dmitry Kovalev, and Peter Richtárik. An optimal algorithm for strongly convex minimization under affine constraints. In International Conference on Artificial Intelli- gence and Statistics, pp. 4482-4498. PMLR, 2022.
Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Tat Lee, and Laurent Massoulié. Optimal algorithms for smooth and strongly convex distributed optimization in networks. In Doina Precup and Yee Whye Teh (eds.), Proceedings the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 3027-3036. PMLR, 06-11 Aug 2017.
11

---

Under review as a conference paper at ICLR 2023
Sebastian U. Stich and Sai Praneeth Karimireddy. The error-feedback framework: Sgd with delayed gradients. Journal of Machine Learning Research, 21(237)11336 2020.
12

---

Under review as a conference paper at ICLR 2023
A NOTATIONS
For positive semi-definite matrix A, | _ x ATA f = Ogg) means there is constant C > 0 such that [f] S Clg)) hil the canonical basis of R d E N. the vector of I the identity, A+ is the pseudo-inverse of A and for a smooth convex function F.
(x v) a F() F(w) - (VF()) y)
its Bregman divergence. We further write e; - e; @ I.
B SADDLE POINT REFORMULATION
With < < j and introducing an extra dual variable L, we get:
inf TER
Σ f((x)
inf Z.ERR=X ===
f((x))
V 11==11 + 11
inf xndd
sup V.sERaxd
Σ fi(x;)) 2 ||=:11
2 || + (y, 5 - x) + (2, πτ.
TI
inf
inf ed SERuXd
sup
Σ f((x;) - + 2/ $1151 + (y, &. x) TT)
zERaxa
inf
sup ER
f((z;) ~ |1,012 2 (x,
2v || + y11
zeRoxd
1=1
C
SGD DYNAMIC
The dynamic considered when using stochastic gradients is given by:
dx, Tf sz)dd (V ū.) (1,
dē, i) 3z)dl - (.)
dū: = Alve + 2t + vūt)dtt + (5 + (VF -..)dN(t.
(8)
dy: = ax (ūi y:)dt
dæ; = ax( & 2, dt B Eii.DEe (e: - e;)(e: - T + 2))dM;;(1)
dā, = (zz - ž, ddl - 3 EasneEe - e;)(e: - e,)T(r
(vr + zx)dM;,(1)
D PROOF OF THE THEOREM
D.1 PROPERTIES AND ASSUMPTIONS
The following properties will used all along the proofs of the Lemmas and Theorems and are related to the communication of our nodes.
Lemma D.1. Under the assumptions of Theorem 3.2 if 20, 2o e span(I), then 24, &o span(T)) almost surely.
Proof. It's clear that for any i.j. get:
π T(e e,)(e, - e,)
T = (e, - ee - e,
Thus, the variations of (2x, &)) belong to span(T).. and so is the trajectory.
We derive the following Lemma, similar result from Boyd et al. 2006
13

---

Under review as a conference paper at ICLR 2023
Lemma D.2 (Spiking contraction). Under the assumptions of Theorem 3 (t((t [I(e: - ey)(e; - -ey)² - -xx=|² || = A(t)
3.2
we have:
|
Xi
(.)))
Proof. If = j. then Au = 0. For given (i,j), we get if j:
II(e: -c) , nx||²
|| + ||:;; xz|1
(9)
2(T((x), -c,)(c, -0,) -,)
|| (z. (e: - -c)((e: e,) x)
(10)
And this allows conclusion by sum.
Lemma D.3 (Effective resistance contraction). For Fori,j and any x E R", we have:
[I(e; -e,)(e - -ej) ex)"=11200r S Sxillee
e,)((, - =Il
Proof. Indeed, we note that:
II(e: - ee) - ez) = -e, -;) (()) -e; -,)(0; - -0,)²x
(11)
s $2x2= (c: - e,)(e: -c,]
(12)
= =x2l(e - -e,((e, 0,) ) rxl
(13)
Lemma D.4 (Min and max voltage values, see, egg. Klein & Randic (1993)). ). For any i, ATA(t) ey) 2 e[A((t) (e: -ey).
Proof. Let us call v & A(t)+(e+ ey), and for a vertex k (k) the set its neighbors in Et). Note that k & (k). We want to prove that os A e! v is greater than Uk. In fact, we will prove that Vk, v 2 Uk Vy. Recall that (())A(()+ I ग. meaning that A(I)U e - ej. Thus, Ak & {i,j}.
we have (A(t)u)& 0, leading to:
0 0= Uk Σ
(t)x + (p)(t)) KEN(()
Σ (tR + (erk()))oR
K(EN(K)
This allows to write:
(NtEN EMeNUy (Aw (1) + {xx(())eww
Uk
EMEN(H) (tx (vv
meaning that Us is a convex combination of the values of v of its neighbors. As such, for any k & (i, the value Uk is inside the convex hull of the {uw, k' E N(k)) and cannot be strictly superior to the maximal nor strictly inferior to the minimal value of v among its neighbors. The only case where eg is maximal or minimal when the (vk, k' E [K)) are all equal. This means that the only two coordinates of v that are allowed to be strictly maximal or minimal among their neighbors are i and j. Thus, the graph being connected, there is a path beginning at any l and leading to i or j made by iterating arg maX UW or arg min Uh steps, hence max, Uk e,) A(t)+ eg) 2 and U, 2 Uj- and ming 2h in (vs; v.). But, we have es- Fj (e. (e)=-)))Tee
Thus, max; UA- = my and min; Uk= = Uÿ.
L
Lemma D.5 (Bound effective resistance). For any i, we have ())
1
Proof. AS A(()A(I)+ =I n, for any j. we write:
2 2 (e: - (T-,,)TA()AA A(t)A(t)* (e. -e,)
(14)
Σ Au(()(e - -e,) (ex - ei)(Ex - A(t) (e. 166--0 -e).
(15)
14

---

Under review as a conference paper at ICLR 2023
As have, for any 1, k. l:
if = i and | 1
k * i and = ]
1 if k =j and + i
(e: - (e)e - e()
if * j and i 2 if k = i and
(16)
| =
k = j and i 0 otherwise
and applying the fact that Aa((() = Of (k: 1) & E()), we can expand Eq. 15
2
-2) (e-e))
ey))
(1)(1) (eIA(1)) -e) -e) -MM (es e2))
E (EE((TE e₁) eTA(())( e4))
(17)
E Aut(t) (C[A((t)) eÿ) ATA - c,))
+ ()) e2) A(1)+ - ej)
21);(1((e) - A - ej)
Using Lemma D44 the facts that )(;(() 2 0 and A()+ is positive semi-definite, all the terms in Eq. 17 are positive, giving:
(t,(t)(e - - (c. 52 2
(18)
Next, we set such that:
L
2T. [VF()) VF())) dr(w, v) S 51 v11
and
11 2112 < dz (z. v) - 2v
V
1 [F(x)) VF(W).
and we remind that:
Eedp(,s) 4) = ((.)))))))))))))
(19)
D.2 PROOF OF THE LEMMA 3.
Proof of Lemma 3.1 First, we note that A(t) is symmetric and has non-negative spectrum, as:
x A
Σ (=(0)===1,11 (3))
From this, we also clearly see that X1 (t) = +oo iff the graph is disconnected. Next, assuming that the graph is connected, an eigenvalue of A(t) with multiplicity 1 and by definition of x (t), we have TrA(!) 2 n-1 As we also have:
(I
Σ
A0s(0(e - (A) -e) es) = Tr(A (((+())(()) = n 1
(L))EE())
we can write:
n 11 5 Σ
= - x2(TTA(()
(L,))E(()
15

---

Under review as a conference paper at ICLR 2023
n-1 min((1(t),xx2())) x2(t)). Finally, for any (i.j) E(t,, using Lemma and get TrA(d)
get that:
Ac(t)(e= - At -0,) I
Thus,
As(tt) (e; e - -e,) 11
inf (1L)EE(
leading to:
2x2(t) S (i.))e)) (ty
D.3 PROOF OF THEBRREM 3.2 AND COROLLARY 3.2.
Proof Theorem 3.2 Because + is smooth and E(t) is constant on intervals, we get via Ito's for- mula (Lstt & Penrose 2017) applied to the semi-martingale (Xx, Yr), gluing intervals where {(t is constant (as well as the weights (()) that:
(t, = No, 1o) (( (VD(t, Xi) (1(X,, Yi) /tt a2 Y.:)
(1, +, $1,, Xz, Y.))
L' (,
Y, + *(1, Xx, Y.)) (i)((tt) + θr,
(1))
where:
n / Σ
Or 2
(olt, X, y b(,())))) X,, - dt)
i=1
Σ
(0 + -x) ((
(1)(()
(BJ)EE())
We will use the following technical Lemma, which is also difficult to prove and whose proof is deferred to Appendix D.4
Lemma D.6. There exists some parameters U 2,,,,,,,,,,,,000 and e > 0 such that:
(X,, ( (22 Yi)
(V,
x) Xt, Y())
(,)(1)((1,, X,, Y (2)) -X,,,, Y.) < aas..
(1,))E())
with A1 -4=00 /-=///A with Ao 1.
Following the lemma above, we get that:
0 s Et Yi) < E[0 Y))
We thus know that A, = e.VE E, which implies that:
E[A,dy (2,, < E[ Yo)
and we will obtain the conclusion of our theorem by expliciting all the constants the following.
We note that the expected number of activated edges between [0, is by of the Poisson Process
Ie Tr(A(t) dt, and given the gradient fire at rate 1, the expected number gradients computed is n...
[T
16

---

Under review as a conference paper at ICLR 2023
Proof of Corollary 3.2.1 We remind the SGD version of our Lemma:
Lemma D.7. There exists some parameters v, M, 7, R, a, a. 0,8,0,888,88 and > 0, C > 0 such
that:
X,,,),
(i((x)))) (2(X),
(0(t,x)+ (tt, Xe.
Xx, Y + o(,, Xi) s SCA, 1
Σ
a.s.
(00)
(K)))E())
with A, CVT.A, with Ag 1.
The proof follows the same path, except that we have an extra term that writes for any T > 0:
A = C
1
(21)
cVVL
which leads to the conclusion following an identical path. The constants will be explicited in the
next Lemma.
D.4 PROOF OF THE LEMMA D.6 AND LEMMA D.7
We first state a couple of inequalities that we will combine to obtain bound on our Lyapunov
function.
Proposition D.8. First:
ΦΛ a Ac(dr(x* (x))===,======))))"" - dx(xxxx)))))
Al -211 11 x=11 113) - -F(x)-VF(r))) + A - 5r 3 - xx)
+ A/ - x,
(22)
< VVF(x) "1 At L12
- + A,52
2
+A((FF(z) - 0.4² -i) - -2 (ÿ- -²,ā=="
(23)
25/A, + ( x))
- -nAa(ds ( (. +
x²)) - A - x112 + Acollo - x=1
Proof. First, we have to use optimality conditions and smoothness:
dr(x=, ,x)) dF (x, x*) dz ,,) - (x+ x, - VF(z))
(24)
< lot x|| -, VF(x))
(25)
2
In2
11ū
2
<VFF() - ÿ. v² -))
(26)
Next, we note that, again using optimality conditions:
||
x= 1
|
x=
211 1|
2(a -,
(27)
-,
(28)
-22/VV(()--V((77)---))))))
+29(0- -F)
(29)
= -+(()r((,""))((((")==)))-- -f)
+27(5- - 10="""""="" -=="")++((V[(2> - 51
(30)
Momentum x associated with the term x=) gives:
( xr Fx - vF(=")) (dr dr dr( dr x²))
(31)
17

---

Under review as a conference paper at ICLR 2023
and momentum in ã associated with || x=1 leads to:
(z v, σ - x²) = -2f 5 - x²11 + 27 x², - x²) -ūilë x=11² + + - x²1 (32)
Corollary D.8.1. Under Assumption 3.4 have:
कa - [e(Ar(dr(x
(0 + A.(1Ea+ - x²112 -1 - x x11)
+ 7,,(5 - II VF(a) -F(x)))F(2")) + Ar -. x²)]
(33)
Φ 02 In²
2 AAy Ang)
(34)
Proof. Using the same computations and the Eq. 36 we next note that:
(1,,) -yl = B [1 | (z., E)1 - ((. +1
(35)
S VVF +
(36)
Proposition D.9. Next, we show that if oB Br:
Φn A B. - 8²12 [yy - y" "01²²) + Bl - 1012 110 y²11²)
+ 2a (y - y2, v) - 20 (y + + vē, T5 y")
+ 2a - y, + y yf" - ==")
(37)
$ 2
8
Bellü - 112 - B.llyy
6
1JR-2.B.(VF ". 15)
+ +...1VFFF)) - VF(x")] (15+ -) 6) B.llVF(x) y/1²
(y 3'' - ==" --) - 20v B₁ (5- x 9ー)
+ 2a - y, + y" 2²)
(38)
Proof. Using optimality conditions:
11 y" 1|2 - l/ = 1 -0 0|
(39)
+ 23(VF(x) 5. v²)
(5 ()+)) - 01|
(40)
-)((V((()) ÿ.y" 1
+8)VVF(z) - VF(==) )12 51/ y01
(8 + 8)2 6) |VF((=) 011
(41)
The momentum in ý associated with the term ||ğ y" 112 gives:
(y + vž, y²) 28 B, (y 3 2-. v²)
20vB (ā x² 1 - yy)
(42)
The momentum in y associated with the term 11y 112 gives:
B. y. y²) = aB Iy 11 - aB, 11 1/12 + B - 12 and the one associated with ||y + y² 1|?
(43)
2aC (0- y, 2 y y² =
(44)
18

---

Under review as a conference paper at ICLR 2023
Corollary D.9.1.
Under Assumption 3.4 we have:
き - E - -²11-- - 1ly ,-1 + (1l - y011² - -1 y 11²)
+ (y -1) + = +
vž. -y))
(45)
S ΦB + ( (6 B))
(46)
Proof. Exactly as above.
Proposition D.10. Finally, assuming 0B, = 3C; = aC,, letting 1 > 0, 2/ = 3(e, -e, (e, - -e,) T (y + 2) and 2/} = B(e; - e,)(e: - -e,)² (y + 2), then:
Pct0D - 20 (y + 2 n - x" 1 - 4¹) -
Σ Ct) (1y 1 -
(a(t))c(111++0)
212 - |1 + - -v²
V-= - 12
+ Σ Ny(()) (12 1|- - =91p) + 2āc((z - -2,2-2") A(1++
(47)
15
+ 2aC +0
3² -) - -20 (y --- y¹ - =0 y²)
S -230,18- x2" 2)) +
XxIO Σ
Xn((t)](ee - e,)(e, - -e,) [0 + +)1l²
(L.))E())
B Cill((y + =)1 + B(3 1)Cr Σ )x(()](ee=
- 0,)(es - e,) (y + =)12
xi
(i)))E(()
- -CCily+ +2 - y²¹ - 21 + axić.ll== - 201 - -acill - 21
$2 O - 112 + - v 2af
1 M
Belly - 11
(48)
T, 8
Proof. Having in mind that xty" + +2*) = 0 and A(1)+ = ग, we get, using Lemma D. and
Lemma D33 on the inequality 52
A _
Σ A0(0 ='1 - 1|2 - ==1122(0++
(49)
(())
Σ 2r(())(E- - -"' 2 - A0)+ + +11ž - -21(2
(50)
((J)E
-23 Σ \²
(00)3-2',00 ,e, ee, - -e,) (2)
+ 8² -²-=")) =2²))aup x(1)+
(1))EE())
+ Σ )y(t) cz)(e= -c;)
(v= + =)]12a00+
(51)
(L.))
< 23 - 2., A(t)* A(t) + 2)}
+ +x
Σ (t((t)((e: - -e;)(e - -z (y + 2)12
(52)
(1J)EE())
= -23 - (T + 2)) + x23²
Σ
Ag(t)l(e: - e,)(ee- -e,) + 2)1?
(53)
(1)))8((
19

---

Under review as a conference paper at ICLR 2023
We also have, as y* y and using Lemma D.2
4 A
Σ
{ly(t)((1** + - - 1f" - -2 2=1 1
-lyy + 112--1y-
of - 2- =01
(54)
(())E(()
2
Σ X,(1)(y+ + -
- 2, + + 1f =n)
(()))
+ Σ Ab(1)l + 22 - y- =||
(55)
(LJ)EE())
= --2
Σ
(ee - -,;(ee, - e,) 8² z²)
(())EE()
+ E
B (B))(())((e= -e,)(e, e,)[( [(y 2)12
(56)
())EE(()
Σ )1)(1)
B|, - e,)(e, e,)² T
(y + z]|| - BI| =)13
(())E(()
+ B]](e: e;)(ee e + =) M(y + 2)|
+ flee, e,)(e: e,) (y + =)({²
(57)
s B IT + 2)1 + B(B - 1) Σ - - -e) + 2]11
(58)
xi
(L)))
The momentum in å associated with ||ž 2² =0)2(00) gives:
2aC - (
=")A(1)= S sāxi ==111 - -aC:l - == ==1aa
(59)
And the one in 2 associated with l1y -y" y² - = gives:
2aC, 2, y - 3² 2²
(60)
Then, assuming that 0B, =BC aCt, have:
(ū - y, = + - n² - =²) - -B3 - - 3² - =²)) 20 (y + y² ==" 55) + 2aCr -,=- 1² 2n)
(61)
=-2aCilly +2 2
(62.)
At this stage, we split the negative term remembering that S and introducing
62 in two halves, upper-bounding one of the halves by 2 7 >0 0:
-aColly+2-- 22 201 aCilly
3² 2012
(63)
- + 2-- y² 21
(64)
< - +134 --100112
Cill - 2 + v
Čilly - 1²12
(65)
2 I L
L
1/ 2af
- 3-3"Cillz
2 21
--
Belly - v²11
(66)
2 L
L 8
Keeping in mind that 0B, = BC, = aC, and SB, = aB, we put everything together. Defining
V/ ΦA + on + dC + ΦD. we have:
20

---

Under review as a conference paper at ICLR 2023
LT
V S (VF()) - 8/l
A
Ar + +A77 + (0)+0) - B.
(67)
2
+ 2|2 2' 2'I
(-ãC; + +t))
(68)
6
+ 110 - s- BP
Bi)
(69)
2
+ 1| - 2- (A, À 17
(70)
+ - x1 - AnT)
(71)
3. Av)
+ +IVE(()) - VF
(72)
2L
+ +[
+ +) - =(V" + +2))1((- Ct)
(73)
Xi
+ Σ >,(())((e= e;)(e; - -e;)-e;; evy + =)1?? (1330C, 3(3 -18--));;
(74)
(()))
+ I| x ="
2 -C
.
(75)
+ llv 3/ [BB; - (1 - 20
LB 8 oBBi)
(76)
+ +1y++ - y¹ 2'1 aCi)
(77)
+dr(I,=")(4 mAA)
(78)
(c + +27A))
(79)
+ +dr(t,z")ANn - -22.))
(80)
+ (VF((z)- -- + Add)
(81)
+ - x²) (2%A,, -20vB.)
(82)
Resolution GD
Proof of Lemma D.6 and make the factors of positive quantities (norms or divergences) less equal to zero. Given relations, we guess that each exponential has the same rate. Thus, with 7 > O, we fix 3 = ń = 1)
Our goal is to put to zero all of the terms appearing next to scalar products
ā ā= =VTV I. which leads to 7 Vul.
2r using Eq. 70 Also, from Eq. 80
AA, = VA.
Next, from Eq. 72 and Eq.
82
it's necessary that:
2LS = 0v,
thus 44 v. From Eq. 82 we get:
L.
A, = BL.
21

---

Under review as a conference paper at ICLR 2023
Combining this previous equation with Eq. 81 as 4A, vA, have g 4Ly. Next. Eq. 67 gives, with the equations above:
1, 2 -7) + 2,52 + (16+8)2
-6) B: A;
LT
A + 1/ 4
2
(82 + 8
8L
L
7 47²
A,
2
vL
"."" + 47 V
11
+ 1
+ A.T V
L
8L
5
7
V2T
Ae(7
2 7 +
8 T
We thus pick y= 4T then get:
1
and r = ./8 so that = 1. Via Eq.
76
we fix i = 8
< 1. With Eq.
7
we
B = 2xi 2
We also put 27 2 H. and only one last equation, Eq. 1.
74 needs to be satisfied, for which we pick
X C 3(3 - 1)C, (X 11
This implies that X2x I 3. Finally, it's clear that all the equations are satisfied if we consider Ar, Ae, Bi, Be, Cr, Co as exponentials proportional to eVVi. Let's pick Ao 1.
Now, we remark that:
(00 Xo, Yo) Andr (xo, x* =1 yo y
C -=== - -=
(zu) and ău - V then, given the linear relation between A,, A,, BG, Bi, Ct, Ce, the T. smoothness and the fact orthogonal projection, get:
If un Fu. yo
( Xo, Yo) < ( x + V 1110 - =1 + z _d (x) + ds (wo, x²) + (10, x*)
16
4
(83)
1 (0)
32 Xi de (z0.
(84)
Now, we use that -= < L and as (0) S xi. we get:
$00, Xu, Yo) $ 2d + 11 - 11
Given that dr(2, f(x) - f(x*), ) this implics in particular that:
B[f(x:)) - fxx) s (2d x²) + f 11 x0(13)e +VE
Resolution SGD
22

---

Under review as a conference paper at ICLR 2023
Proof of Lemma D.7 All the previous computations hold, except that the term in front of o² is given by:
(8+ + (Ar Ina ArT + A,7) = (8² + (6 8)2)
4
7L
+ (A
LT²
Ary 1111)
A
(85)
2
5
At
(86)
8L
Thus, we obtain, by integration of the potential that:
5
(t, X,, Y2) < @ Xu. Yo) + o
Au du
(87)
8L
Now with Ac, Ae, Be, Be, Ct. Ct as above and all the constants as above, we get the result, since: Jo 5 88 Au du ViTe
E PHYSICAL INTERPRETATION
To gain more insight on the condition 2x1[A|xa[A] < 1, we can write A(t) as the product of two more interpretable quantities:
2A(t)
A(t) = Σ (t)
(88)
Tr A(t)
(WE)(()
AAO
(A(C)
In this setting, X(t) is the instantancous expected rate of communication over the whole graph at time i, while (t)) can be interpreted as the Laplacian of {() with each edge weighted with its probability of having spiked this instant given an edge fired at time
Being normalized, (()) only contains the information about the graph's connectivity at time / while X(1) is the global rate of communication. We have:
(x( A(t)
xx(A(t)] xa(A(1)
xi(A(t)
(89)
A(t)
we make the following assumptions, Assumption F.1. There is X* such that, all time I, A(1) 2 X². Assumption E.2. There are Xi 0, X5 > 0 such that, for all t, x1 xa(ā(t) s Xi and x2 xe(A(1) s Xi-
meaning we assume bounds on the worst rate of communication and on the worst graph connectivity, Xi we immediately have XI [At]] < 전 and x2[A(t) < F leading to xi < x and X2 < E Then, the following condition on the worst rate of communication is met
V 2 X
(90)
meaning that the instantaneous global communication rate is always larger than some spectral quan- tity quantifying the graph's 's connectivity, it directly implies 2x [A < and the convergence of our method,
F COMPARISON WITH OTHER WORKS
We now explain the results of Sec. 4.1
23

---

Under review as a conference paper at ICLR 2023
F.1 COMPARISON WITH +DOM+
Using the notations of Kovalev et al (2021a), we know that gossip matrices satisfy, for q N:
1 )|a/|1
[[
=11² - (1
for some 2 1. It implies that:
sp(W(g)) C V T X 2], - 2x"
and for x large enough, Xi [i]
Consequently, up renormalization factor, have
2x and:
Tr)) 2n.
F.2 ACCELERATION OF THE CONTINUIZED FRAMEWORK
Under the notation of Even et all (221a)) we note that, an additional simplification holds: AARG =
ARG. We remind that L = AAT and that Acow = Peww(Ce Gw). Next, we note that by definition:
Ryw TT A+ Acew Pow
(91)
Pow
c At Cw)
(92)
VPowc
(A+T (vw)
((ew))(( (Eex - Ew)
(93)
VPow
((AAT)+TAc (er - Ew)
(94)
VPew
(ev - -ww ( -ew)
(95)
so we can directly relate their bounds to ours. Next, as LL+ I n, we observe that:
n - 11TTT([CT)
(96)
= Σ Pijle- (t eg)
(97)
(NI)EE
< 2xx[4] Σ Pij
(98)
(15)EE
= TrL,
(99)
which, together with the fact that Xi [C] 2
a-1 Trc
(see Lemma 3.I).
leads to:
n- 1 < 2 x
in the setting of Even et al. (2021a) where Tr L =
F.3 COMPARISON WITH METHOOSS THAT USE THE SPECTRAL GAP
We note that: (P( = (A()))((((()) Further, we assume suer (g
O(1) as n
inf (a) (t)
grows. This condition can be understood way to prevent degenerated behaviors in the network's 's connectivity: the worst case communication rate should always be greater than some fraction of the largest rate, with fraction value not growing with the network's size. This condition is always met we assume there are both a lower and upper bound on the communication rate of the channels linking the nodes, which seems reasonable in physical setting. Then, using Lemma 3.1 recalling
24

---

Under review as a conference paper at ICLR 2023
that Tr(A(t)) = 2 (()EEE)))) (t)(t) & (( (t((t and Tr(A(t)) S (n 1)]IA(t]]I,
obtain:
1
vxxTr(A(t)) S
TrA(E)
(100)
2inf (L))EE()) (i)(t)
vx)T(A()) <
1
2(E(()) sup (T((O/(TA()) (65)EE1))
(101)
/2inf (t)
SuP(N)EE()) Ne) (t)
VIE(t]l 1)
(102)
inf(LS)EE()) (t)
SUP(LS)EE()) )g) (t) (L))EE))))))) (t)
(E())V/
(103)
G FURTHER EXPERIMENTS
In this section, we present additional numerical results comparing our method DADAO to ADOM+ (Kovalev et al. 2021a) in the time-varying setting and report our results using SGD.
G.1 TIME- VARYING SETTING
In this section, we study the effect of the parameter Xi on the convergence speed of ADOM+ (Kovalev et al. a0) and DADAO by varying it between xi E (3,33, 33, 180, 233} for random geo- metric graphs of size n 20 on the decentralized linear regression task with time-varying topology. To visualize the difference connectivity these changes in Xi represent, we plot four graphs of the said types with varying values of xi in Fig. 3 In Fig. 4 we show the different convergence speeds entails.
Figure 3: Examples of random geometric graphs of size 20 with xi taking values in, from left to right, xi E {3, 33, 180, 233).
As expected, we observe in Fig. that varying xi does not affect the number of gradient computa- tions of both ADOM+ M.-C and DADAO, but the smaller the Xi, the better the slope for ADOM+ terms of gradient steps. We also confirm for all three methods that the smaller Xis the less com- munication is needed to reach an e-precision.
G.2 STOCHASTIC GRADIENT DESCENT WITH DADAO
In the SGD setting, we randomly sample mini-batch of size B data points on each worker and compute the losses and stochastie gradients V.((,,, w.r.t these samples. To study the effect of the quadratic error o² of our gradients the resulting biases of our parameters, we fix both the data (for linear regression) and the communication network (graph star of size n = 20) and try different values of B. To monitor our results, we plot the mean distance to x² of the running average over time of our local parameters. Then, taking the notations introduced in Sec. we can write:
(8)
j=1
where k; designates local event counter. We report results in Fig.
25

---

Under review as a conference paper at ICLR 2023
303 100 BRG
200 450 2010 900 100
120 400 100 1O00
DO0 40 000 000 BAT
5
55
5.
Aergee
Avece paane apeetinte
+V
Figure 4: Comparison between ADOM+ (Kovalev et al 202 and DADAO, using the same data for linear regression on n = 20 workers and the same sequence of random connected graphs with
varying topology and x² taking values in, from the left to the right column, X1 {3, 33, 180, 233).
Average distance to optimal value
1
10
10
Distance to x
50
10"
1
50000
100000
150000
200000
Total number of stochastic gradients
Figure 5: Effect of the batch size B on the convergence of our method DADAO. Recall that the full batch size equals 100.
confirm that the less variance on our stochastic gradients, the less our estimates are biased.
1 R. Σイ= x
G.3 COMPARISON BETWEEN DADAO AND MSDA ON THE STAR GRAPH
For star graphs of size E {10, 20, 70, 200, 300, 1000, 2000), ran DADAO and MSDA on the task of distributed linear regression. We considered the evolution of the average distance to the optimal with the number of gradient steps and commmunication steps in log scale for each run, and computed the slope of each line. For each graph size, we report in Fig. 6 the rate between the slope for MSDA and the slope for DADAO. We remark that the rate between the gradient complexities
26

---

Under review as a conference paper at ICLR 2023
Rate
slopes MSDA DADAD scale graphs
Compuration rate
Communication rate
20
measure 44
15
10
1000
1500
2000
500
1000
2000
graph.
graph.
Figure 6: Rate between the slopes of MSDA and DADAO for star graphs of size
(10, 20, 70, 200, 300, 1000, 20003.
of DADAO and MSDA is indeed O(1) (with a constant value of 14) while MSDA indeed O (())) worse than DADAO for communications on the star graph, as stated in Tab. 2
H PRACTICAL IMPLEMENTATION
In this section, we describe in more detail the implementation of our algorithm. As we did not physically execute our method on compute network but carried it out on single machine, all the asynchronous computations and communications had to be simulated. Thus, we will first discuss the method we followed to simulate our asynchronous framework before detailing the practical steps of algorithm through pseudo-code.
H.1 SIMULATING THE POISSON POINT PROCESSES
To emulate the asynchronous setting, before running our algorithm, we generate independent sequences of jump times at the graph's scale: for the computations and one for the communi- cations. As we considered independent P.P.Ps, the time increments follow a Poisson distribution. At the graph's 's scale, each node spiking process is n. Following the experimental setting the Continuized framework (Even et al. (021a)) we considered that all edges in E() had the same probability of spiking between t and + dt. Thus, given the sequence of graphs (() and L(() their corresponding Laplacians, we computed the parameter X* of the communication process as such:
rate of 1, the Poisson parameter for the gradient steps
C(t) [8(t)]
C(t) [E(1)]
X = sup X1
sup
(104)
Having generated the sequences of spiking times at the graph's scale, we run our algorithm playing the events in order of appearance, attributing the location of the events by sampling uniformly one node if the event is a gradient step or sampling uniformly an edge in E(() if is communication.
H.2
PSEUDO CODE
We keep the notations introduced in Eq. Appendix D.4
3 and recall the following constant values specified in
7 $ V
7= nI
8 8
a I 3=
0 = 1
n 3
3 AVol
8=1
b= V 3- 3-2xiTA1
V=
27

---

Under review as a conference paper at ICLR 2023
For the sake of completeness, also specify the matrix A describing the linear ODE
0
0
0
7j
-1j
A
0
0
0
0
0 8
(105)
0
Bv
8
0
0
0
0
As described in Appendix H call PPPspikes the process mentioned above, returning the ordered sequence of events and time of spikes of the two P.P.Ps. Then, we can write the pseudo- code of our implementation of the DADAO optimizer Algorithm
Algorithm 2: Pseudo-code of our implementation of DADAO on a single machine.
Input: On each machine i E (1,...,,.) an oracle able to evaluate Vf,, Parameters
H. L, Xi fmax: nI, X The sequence of time-varying graphs {t).
Initialize on each machine E {1. ........ n.:
Set (1) (2,, Ft U.) and y (y), 24,
24) to
Set constants v, 9. 17 a,a, ā, 0 5, 3,8, 3, using μ, L, Xi:
Set A;
T() 0:
ListEvents, ListTimes PPPspikes(n, (lmx)
Nevents + |ListEvents]:
for k E [L. Revenss do
if Listttvttsss [k] is to take a gradient step then
10
i~ ([1,n]]))
X
(
11
y()) + exp
((())
(
24 6 2, - (VV((()) va, - ū.):
12
ã ã; (V)((()) wr; W.)::
14
5 + 8 (V/((=;) von 0:): (i,j) ~ ((((LiistTimms(())
T + ListTimes[k]]
15
16
else if Li sistEventss))) is to take a communication step then
X(
(110
cxp ((p(((itTimme [k] A()
Y(0)
y())
((6)
(x())
exp ([s)stTiimeee] (())AA)
Y
y())
mij
(U: 2 Uj -2)):
// Message exchanged.
21
2, + 2 3miji
2, 2 3miji
23
- + 3miji
2, 2 + Bmizi
7(O ListTimes(k]:
25
TO + ListTimes(k]:
26
27
return (ms) the estimate of x² on each worker
28


Reviews:
[{"review_id": "zSnKW03ZOBo", "reviewer": "Reviewer_R4MY", "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 work proposed a decentralized asynchronous stochastic first order algorithm to minimize a sum of L-smooth and µ-strongly convex functions distributed over a time-varying connectivity network of size n. The authors model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, to decouple the computation and communication steps. The proposed method is differ from the majority of works since it does not use a multi-consensus inner loop nor other ad-hoc mechanisms such as Error Feedback, Gradient Tracking, or a Proximal operator.\n", "summary_of_the_review": "The authors model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, which differ from the majority of works. The experiment is too simple for verification. The convergence analysis is lacking some important factors.  ", "strength_and_weaknesses": "strength: the proposed approach is differ from the majority of works since it model the local gradient updates and gossip communication procedures with separate independent Poisson Point Processes, to decouple the computation and communication steps. \n\nweakness: \n- the experiment setting with decentralized linear and logistic regression tasks is too simple to validate the effectiveness of the approach. \n- many importance factors of convergence rate are not clear, such as communication latency and linear speedup ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TEI0vrEeo98", "reviewer": "Reviewer_gkNG", "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 proposes a decentralized asynchronous stochastic first-order algorithm DADAO to minimize the sum of strongly convex functions over time-varying decentralized networks. This paper develops the theoretical performance guarantee of a related ODE system and tests the empirical performance by numerical simulations. ", "summary_of_the_review": "This paper proposes an algorithm to solve decentralized strongly convex optimization and establishes some new complexity results. The results are developed for continuing-time frameworks, but the guarantees for implementable practical frameworks are absent. The theoretical claims are also only applicable to a restrictive class of problems. The overall contribution seems to be limited. ", "strength_and_weaknesses": "Strength: \n\n1. The proposed algorithm achieves new performance guarantees in both communication edges and gradients.\n\nWeaknesses:\n\n1. Theorems 3.2 and Corollary 3.2.1 provide guarantees for the ODE system Eq.(3) and Eq.(8), respectively. However, because ODE considers a continuous-time regime, it is not obvious whether these results still hold in practical discrete-time implementations. The discrete-time performance guarantee has been shown in prior works (i.e., Theorem 4 of [1]). It would be beneficial if the performance guarantees of discrete-time GD and SGD algorithms can be provided, which is provided in prior work. \n\n2. Theorem 3.2 considers the case where $\\chi_1^* \\chi_2^* \\leq 0.5$. This assumption seems to be a bit restrictive because the constants $\\chi_1^*$ and $\\chi_2^*$ depend on the network itself. It looks that ADOM+ in [1] does not need such a restrictive assumption to ensure convergence. It would be helpful if an additional explanation can be provided to justify why such an assumption is required. It would also be beneficial to discuss whether similar assumptions are required to the mentioned benchmark algorithms. \n\n3. Theorem 3.2 shows the existence of the parameters $\\alpha,\\gamma$ but does not specify how these parameters should be chosen in real networks. It would be helpful to specify the choice of these parameters. Also, does  $\\gamma$ refer to the same quantity in Table 1? \n\n4. Corollary 3.2.1 introduces an additional bias term $\\frac{C_1}{\\sqrt{\\mu L}}$ to characterize the SGD system (8) in a continuous-time regime. It is claimed that \"$L$ allows to adjust the trace-off bias-variance of the descent\". This seems to be a bit confusing because $L$ represents the fixed Lipschitz constant. If one considers a larger $L$ to reduce this term, the decay rate of the term $C_0 e^{-ct\\sqrt{\\mu/L}}$ would deteriorate as well. It would be helpful if the authors could elaborate more on this. \n\n5. When comparing DADAO with ADOM+, it is claimed that ADOM+ has potentially substantially higher expected communication than DADAO. It would be beneficial if the paper can specify the referred scenarios. \n\n6. Various benchmark algorithms are tested in the numerical part. However, it seems that MSDA also has comparable performance with the proposed DADAO algorithm in most of the scenarios. Could the authors provide additional numerical experiments to demonstrate the efficiency of DADAO? It would be helpful if numerical experiments in some special cases such as star or complete networks can suggest DADAO's superior performance.\n\nMinor Issues: There are some typos and some quantities are undefined. \n\n1.  In the abstract, the $O(n \\sqrt{\\frac{L}{\\mu}} \\log \\epsilon)$ gradient complexity is confusing. Should it be  $O(n \\sqrt{\\frac{L}{\\mu}} \\log \\frac{ 1}{ \\epsilon} )$ where $\\epsilon$ is the precision? \n\n2. In Table 1, $\\gamma$ is undefined so that a fair comparison between $\\sqrt{\\chi_1\\chi_2} n $ and $\\chi_1 |\\mathcal{E}|$ is not obvious. \n\n3. When defining $\\chi_2(t)$ in page 4, the quantity $\\Lambda^+(t)$ is undefined. \n\nReferences: \n[1] Kovalev, D., Shulgin, E., Richtárik, P., Rogozin, A., and Gasnikov, A. (2021). ADOM: Accelerated decentralized optimization method for time-varying networks. ", "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": "LvVR0lB3T10", "reviewer": "Reviewer_c2yc", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "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 studied asynchronous decentralized SGD for strongly convex problems. The authors provide theoretical analysis for the convergence rate and conduct experiments to verify its performance. But the writing is not very clear. It is not easy to follow.", "summary_of_the_review": "This paper studied asynchronous decentralized SGD for strongly convex problems. The authors provide theoretical analysis for the convergence rate and conduct experiments to verify its performance. But the writing is not very clear. It is not easy to follow.", "strength_and_weaknesses": "Strength:\n1. Theoretical convergence rate is established.\n2. Studying the convergence from the continuous perspective.\n\n\nWeaknesses:\n1. The convergence rate in the abstract is wrong. \n2. Why is it necessary to study the convergence rate from a continuous perspective? Is there any benefit? For strongly convex problems, the traditional analysis can also establish the linear convergence rate. Moreover, in the appendix, I didn't find the authors use continuous tools to investigate convergence. Why do you introduce Eq.(3) and that in Section 3.3?\n3. What's the meaning of $\\chi_1$ and $\\chi_2$? How do they relate to the spectral gap?\n4. How does the communication latency affect the convergence rate?\n5. How does the spectral gap affect the convergence rate?\n6. Can the convergence rate achieve the linear speedup with respect to the number of devices?\n7. The experiment is too simple. More complicated models and datasets should be used to evaluate the performance. \n8. Asynchronous decentralized SGD has been studied before. But the authors missed some important literature, e.g., http://proceedings.mlr.press/v80/lian18a.html ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "3265l6RWCs", "reviewer": "Reviewer_L3mL", "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 authors study the decentralized asynchronous optimization problem on a time-varying network with n nodes where the main purpose is to minimize the sum of  L-smooth and \\mu-strongly convex functions distributed on the nodes. The authors decouple the computation and communication steps in the asynchronous optimization problem by modeling this problem as a union of two independent Poisson Point Processes and consider primal gradients in their proposed method. They show convergence results for this problem under the proper assumptions. They also present numerical results corroborating their findings in the convergence results.\n", "summary_of_the_review": "A new study on decentralized asynchronous optimization on time-varying graphs is made in this paper. By modeling the problem via Poisson processes, the authors present communication and computation complexity for their proposed algorithm. Some improvements in Subsection 3.3 are required to clarify the findings for stochastic optimization.\n", "strength_and_weaknesses": "Strengths:\n-The authors can achieve communication rounds and convergence complexity results by decoupling optimization (computation) from communication via two independent Poisson processes.\n-The authors provide a clear statement of contributions and comparisons to the literature.\n-A novel analysis of asynchronous communications via is provided in Section 3.\n\nWeaknesses:\n-The optimization results in Subsection 3.3 do not contain information on bounds for hyperparameters in the proposed dynamic in Subsection 3.2.\n-The stochastic result (Corollary 3.2.1) shows a non-vanishing error in the rate. It is conventional to tweak the hyperparameters (e.g., a decreasing learning rate) to make this term vanish over time. It is unclear why this term is a constant and if it can be improved. The current format undermines stochastic optimization results.\n-Numerical comparisons are limited to the ADOM+ algorithm. I recommend further comparisons with other algorithms, such as Gradient Tracking.\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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject