Jean-Christophe Gris

Eva Cochery-Nouvellon

Sylvie Bouvier

Samir Jaber

Jacques Albanese

Jean-Michel Constantin

Jean-Christophe Orban

Jérome Morel

Marc Leone

Pauline Deras

Clinical value of automated fibrin generation markers in patients with septic shock: a SepsiCoag ancillary study

de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


Hadrien Hendrikx

Francis Bach

Laurent Massoulié

Accelerated Decentralized Optimization with Local Updates for Smooth and Strongly Convex Objectives

. To the best of our knowledge, it is the first asynchronous gossip algorithm with a provably improved rate of convergence of the second moment of the error. We illustrate these results with experiments in idealized settings.

Introduction

Many modern machine learning applications require to process more data than one computer can handle, thus forcing to distribute work among computers linked by a network. In the typical machine learning setup, the function to optimize can be represented as a sum of local functions f (x) = n i=1 f i (x), where each f i represents the objective over the data stored at node i. This problem is usually solved incrementally by alternating rounds of gradient computations and rounds of communications [START_REF] Nedic | Distributed subgradient methods for multi-agent optimization[END_REF][START_REF] Boyd | Distributed optimization and statistical learning via the alternating direction method of multipliers[END_REF][START_REF] John C Duchi | Dual averaging for distributed optimization: Convergence analysis and network scaling[END_REF][START_REF] Shi | Extra: An exact first-order algorithm for decentralized consensus optimization[END_REF][START_REF] Mokhtari | Dsa: Decentralized double stochastic averaging gradient algorithm[END_REF][START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF][START_REF] Nedic | Achieving geometric convergence for distributed optimization over time-varying graphs[END_REF].

Most approaches assume a centralized network with a master-slave architecture in which workers compute gradients and send it back to a master node that aggregates them. There are two main different flavors of algorithms in this case, whether the algorithm is based on stochastic gradient descent [START_REF] Zinkevich | Parallelized stochastic gradient descent[END_REF][START_REF] Recht | Hogwild: A lock-free approach to parallelizing stochastic gradient descent[END_REF] or randomized coordinate descent [START_REF] Nesterov | Efficiency of coordinate descent methods on huge-scale optimization problems[END_REF]Liu and Wright, 2015;Liu et al., 2015;[START_REF] Fercoq | Accelerated, parallel, and proximal coordinate descent[END_REF][START_REF] Hannah | A2BCD: An asynchronous accelerated block coordinate descent algorithm with optimal complexity[END_REF]. Although this approach usually works best for small networks, the central node represents a bottleneck both in terms of communications and computations. Besides, such architectures are not very robust since the failure of the master node makes the whole system fail. In this work, we focus on decentralized architectures in which nodes only perform local computations and communications. These algorithms are generally more scalable and more robust than their centralized counterparts (Lian et al., 2017a). This setting can be used to handle a wide variety of tasks [START_REF] Colin | Gossip dual averaging for decentralized optimization of pairwise functions[END_REF], but it has been particularly studied for stochastic gradient descent, with the D-PSGD algorithm [START_REF] Nedic | Distributed subgradient methods for multi-agent optimization[END_REF][START_REF] Sundhar | Asynchronous gossip algorithms for stochastic optimization[END_REF][START_REF] Sundhar | Distributed stochastic subgradient projection algorithms for convex optimization[END_REF] and its extensions (Lian et al., 2017b;[START_REF] Tang | d 2 : Decentralized training over decentralized data[END_REF].

A popular way to make first order optimization faster is to use Nesterov acceleration [START_REF] Nesterov | Introductory lectures on convex optimization: A basic course[END_REF]. Accelerated gradient descent in a dual formulation yields optimal synchronous algorithms in the decentralized setting [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF][START_REF] Ghadimi | Multi-step gradient methods for networked optimization[END_REF]. Variants of accelerated gradient descent include the acceleration of the coordinate descent algorithm [START_REF] Nesterov | Efficiency of coordinate descent methods on huge-scale optimization problems[END_REF][START_REF] Allen-Zhu | Even faster accelerated coordinate descent using non-uniform sampling[END_REF][START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF], that we use in this paper to solve the problem in [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF]. This approach yields different algorithms in which updates only involve two neighboring nodes instead of the full graph. Our algorithm can be interpreted as an accelerated version of Gower and Richtárik (2015); [START_REF] Necoara | Random block coordinate descent methods for linearly constrained optimization over networks[END_REF]. Updates consist in gossiping gradients along edges that are sequentially picked from the same distribution independently from each other.

Using coordinate descent methods on the dual allows to have local gradient updates. Yet, the algorithm also needs to perform a global contraction step involving all nodes. In this paper, we introduce Edge Synchronous Dual Accelerated Coordinate Descent (ESDACD), an algorithm that takes advantage of the acceleration speedup in a decentralized setting while requiring only local synchrony. This weak form of synchrony consists in assuming that a given node can only perform one update at a time, and that for a given node, updates have to be performed in the order they are sampled. It is called the randomized or asynchronous setting in the gossip literature [START_REF] Boyd | Randomized gossip algorithms[END_REF], as opposed to the synchronous setting in which all nodes perform one update at each iteration. Following this convention, we may call ESDACD an asynchronous algorithm. The locality of the algorithm allows parameters to be finetuned for each edge, thus giving it a lot of flexibility to handle settings in which the nodes have very different characteristics.

Synchronous algorithms force all nodes to be updated the same number of times, which can be a real problem when some nodes, often called stragglers are much slower than the rest. Yet, we show that we match (up to a constant factor) the speed rates of optimal synchronous algorithms such as SSDA [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF] even in idealized homogeneous settings in which nodes never wait when performing synchronous algorithms. In terms of efficiency, we match the oracle complexity of SSDA with lower communication cost. This extends a result that is well-known in the case of averaging, i.e., that randomized gossip algorithms match the rate of synchronous ones [START_REF] Boyd | Randomized gossip algorithms[END_REF]. We also exhibit a clear experimental speedup when the distributions of nodes computing power and local smoothnesses have a high variance.

Choosing quadratic f i functions leads to solving the distributed average consensus problem, in which each node has a variable c i and for which the goal is to find the mean of all variables c = 1 n n i=1 c i . It is a historical problem [START_REF] Morris | Reaching a consensus[END_REF][START_REF] Chatterjee | Towards consensus: Some convergence theorems on repeated averaging[END_REF] that still attracts attention (Cao et al., 2006;[START_REF] Boyd | Randomized gossip algorithms[END_REF][START_REF] Loizou | Accelerated gossip via stochastic heavy ball method[END_REF] with many applications for averaging measurements in sensor networks [START_REF] Xiao | A scheme for robust distributed sensor fusion based on average consensus[END_REF] or load balancing [START_REF] Diekmann | Efficient schemes for nearest neighbor load balancing[END_REF]. Fast synchronous algorithms to solve this problem exist [START_REF] Boris N Oreshkin | Optimization and analysis of distributed averaging with short node memory[END_REF] but no asynchronous algorithms match their rates. We show that ESDACD is faster at solving distributed average consensus than standard asynchronous approaches [START_REF] Boyd | Randomized gossip algorithms[END_REF]Cao et al., 2006) as well as more recent ones [START_REF] Loizou | Accelerated gossip via stochastic heavy ball method[END_REF] that do not show improved convergence rates for the second moment of the error. The complexity of gossip algorithms generally depends on the smallest nonzero eigenvalue of the gossip matrix W , a symmetric semi-definite positive matrix of size n × n ruling how nodes aggregate the values of their neighbors such that Ker(W ) = Vec(1) where 1 is the constant vector. We improve the rate from

λ + min (W ) to O 1 √ n λ + min (W ) where λ + min (W ) ≤ 1 n-1
is the smallest non-zero eigenvalue of the gossip matrix, thus gaining several orders of magnitude in terms of scaling for sparse graphs. In particular, in well-studied graphs such as the grid, we match (up to logarithmic factors that we do not consider) the O(n 3/2 ) iterations complexity of advanced gossip algorithms presented by [START_REF] Alexandros G Dimakis | Gossip algorithms for distributed signal processing[END_REF].

Model

The communication network is represented by a graph G = (V, E). When clear from the context, E will also be used to designate the number of edges. Each node i has a local function f i on R d and a local parameter x i ∈ R d . The global cost function is the sum of the functions at all nodes: F (x) = n i=1 f i (x i ) Each f i is assumed to be L i -smooth and σ i -strongly convex, which means that for all x, y ∈ R d :

f i (x) -f i (y) ≤ ∇f i (y) T (x -y) + L i 2 x -y 2 (1) f i (x) -f i (y) ≥ ∇f i (y) T (x -y) + σ i 2 x -y 2 . (2)
Note that the fenchel conjugate f * i of f i (defined in Equation ( 8)) is (L -1 i )-strongly convex and (σ -1 i )smooth, as shown in [START_REF] Kakade | On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization[END_REF]. We denote L max = max i L i and σ min = min i σ i . Then, we denote κ l = Lmax σmin . κ l is an upper bound of the condition number of all f i as well as an upper bound of the global condition number. Adding the constraint that all nodes should eventually agree on the final solution, so the optimization problem can be cast as:

min x∈R n×d : xi=xj ∀i,j∈{1,...,n} F (x).
(3)

We assume that a communication between nodes i, j ∈ V takes a time τ ij . If (i, j) / ∈ E, the communication is impossible so τ ij = ∞. Node i takes time ∆ i to compute its local gradient.

Algorithm

In this section, we specify the Edge Synchronous Decentralized Accelerated Coordinate Descent (ES-DACD) algorithm. We first give a formal version in Algorithm 1 and prove its convergence rate. Then, we present the modifications needed to obtain the implementable version given by Algorithm 2.

Problem derivation

In order to obtain the algorithm, we consider a matrix A ∈ R n×E such that Ker(A T ) = Vec(1) where 1 = n i=1 e i and e i ∈ R n×1 is the unit vector of size n representing node i. Similarly, we will denote e ij ∈ R E×1 the unit vector of size E representing coordinate (i, j). Then, the constraint in Equation (3) can be expressed as A T x = 0 because if x ∈ Ker(A T ) then all its coordinates are equal and the problem writes:

min x∈R n×d : A T x=0 F (x). ( 4
)
This problem is equivalent to the following one:

min x∈R n×d max λ∈R E×d F (x) -λ, A T x , (5)
where the scalar product is the usual scalar product over matrices x, y = Tr x T y because the value of the solution is infinite whenever the constraint is not met. This problem can be rewritten:

max λ∈R E×d min x∈R n×d F (x) -Aλ, x (6)
because F is convex and A T 1 = 0. Then, we obtain the dual formulation of this problem, which writes:

max λ∈R E×d -F * (Aλ), (7)
where F * is the Fenchel conjugate of F which is obtained by the following formula:

F * (y) = max x∈R n×d x, y -F (x). ( 8
)
F * is well-defined and finite for all y ∈ R E×d because F is strongly convex. We solve this problem by applying a coordinate descent method. If we denote

F * A : λ → F * (Aλ) then the gradient of F * A in the direction (i, j) is equal to ∇ ij F * A = e T ij A T ∇F * .
Therefore, the sparsity pattern of Ae ij will determine how many nodes are involved in a single update. Since we would like to have local updates that only involve the nodes at the end of a single edge, we choose A such that, for any µ ij ∈ R:

Ae ij = µ ij (e i -e j ). (9)
This choice of A satisfies e T ij A T 1 = 0 for all (i, j) ∈ E and Ker(A T ) ⊂ Vec(1) as long as (V, E + ) is connex where E + = {(i, j) ∈ E, µ ij > 0}. Such A happens to be canonical since it is a square root of the Laplacian matrix if all µ ij are chosen to be equal to 1. When not explicitly stated, all µ ij are assumed to be constant so that A only reflects the graph topology. Other choices of A involving more than two nodes per row are possible and would change the trade-off between the communication cost and computation cost but they are beyond the scope of this paper.

Formal algorithm

The algorithm can then be obtained by applying ACDM [START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF] on the dual formulation. We need to define several quantities. Namely, we denote p ij ∈ R the probability of selecting edge (i, j) and σ A ∈ R the strong convexity of

F * A . A + ∈ R E×n is the pseudo-inverse of A and x 2 A + A = x T A + Ax for x ∈ R E×1 . Variable S ∈ R is such that for all (i, j) ∈ E, e T ij A + Ae ij µ 2 ij p -2 ij (σ -1 i + σ -1 j ) ≤ S 2 . We define δ = θ 1-θ 1+θ ∈ R with θ 2 = min ij p 2 ij µ 2 ij e T ij A + Ae ij σ A σ -1 i + σ -1 j ≥ σ A S 2 . (10) Finally, η ij = 1 1+θ µ -2 ij (σ -1 i +σ -1 j ) -1 +(p ij S 2 ) -1 ∈ R and g ij (y t ) = e ij e T ij A T ∇F * (Ay t ) ∈ R E×d . ( 11
)
Algorithm 1 Asynchronous Decentralized Accelerated Coordinate Descent

y 0 = 0, v 0 = 0, t = 0 while t < T do Sample (i, j) with probability p ij y t+1 = (1 -δ)y t + δv t -η ij g ij (y t ) v t+1 = (1 -θ)v t + θy t -θ σ A pij g ij (y t ) end while
Theorem 1. Let y t and v t be the sequences generated by Algorithm 1. Then:

2 (E[F * A (x t )] -F * A (x * )) + σ A E[r 2 t ] ≤ C(1 -θ) t , (12) with x t = (1 + θ)y t -θv t , x * ∈ arg min x F * A (x), r 2 t = v t -x * 2 A + A and C = r 2 0 + 2 (F * A (x 0 ) -F * A (x * )).
Theorem 1 shows that Algorithm 1 converges with rate θ. Lemma 4, in Appendix C shows that

σ A ≥ λ + min (A T A) L max , (13)
where λ + min (A T A) ∈ R is the smallest eigenvalue of A T A. The condition number of the problem then appears in the L max σ -1 i + σ -1 j term whereas the other terms are strictly related to the topology of the graph. Parameter θ is invariant to the scale of µ because rescaling µ would also multiply λ + min (A T A) by the same constant. The p 2 ij /(σ -1 i + σ -1 j ) term indicates that non-smooth edges should be sampled more often, and the square root dependency is consistent with known results for accelerated coordinate descent methods [START_REF] Allen-Zhu | Even faster accelerated coordinate descent using non-uniform sampling[END_REF][START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF]. If both sampling probabilities and smoothnesses are fixed, the µ ij terms can be used to make the dual coordinate (which corresponds to the edge) smoother so that larger step sizes can be used to compensate for the fact that they are only rarely updated. Yet, this may decrease the spectral gap of the graph and slow convergence down.

Proof. The proof consists in evaluating v t+1 -x * 2 A + A and follows the same scheme as by [START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF]. However, F * A is not strongly convex because matrix A T A is generally not full rank. Yet, F * A is strongly convex for the pseudo-norm A + A and the value of F * A (x) only depends on the value of x on Ker(A) ⊥ . Gower et al. ( 2018) develop a similar proof in the quadratic case but without assuming any specific structure on A. The detailed proof can be found in Appendix C.

Practical algorithm

Algorithm 1 is written in a form that is convenient for analysis but it is not practical at all. Its logically equivalent implementation is described in Algorithm 2. All nodes run the same procedure with a different rank r and their own local functions f r and variables θ r , v t (r) and y t (r). For convenience, we de-

fine B = 1 -θ θ δ 1 -δ and s ij = θµ 2 ij pij σ A µ 2 ij η ij T .
Note that each update only involves two nodes, thus allowing for many updates to be run in parallel. Algorithm 2 is obtained by multiplying the updates of Algorithm 1 by A on the left. This has the benefit of switching from edge variables (of size E × d) to node variables (of size n × d). Then, if y t corresponds to the variable of Algorithm 1, y t (i) = e T i Ay t represents the local y t variable of node i and is used to compute the gradient of f * i . We obtain v t (i) in the same way. The updates can be expressed as a matrix multiplication (contraction step, making y t and v t closer), plus a gradient term which is equal to 0 if the node is not at one end of the sampled edge. The multiplication by B t-tr corresponds to catching up the global contraction steps for updates in which node r did not take part. The form of s ij comes from the fact that

Ae ij e T ij A T = µ 2 ij (e i -e j )(e i -e j ) T .
Algorithm 2 Asynchronous Decentralized Accelerated Coordinate Descent 1: r {Id of the node} 2: seed {The common seed} 3: z r = 0, y 0 (r) = 0, v 0 (r) = 0, t = 0 4: Initialize random generator with seed 5: while t < T do 6:

Sample e from P 7:

if ∃j / e ∈ {(r, j), (j, r)} then 8:

v t (r) T y t (r) T r = B t-tr v tr (r) T y tr (r) T 9: z r = ∇f * r (y t (r)) 10:
send_gradient(x r , j) {non blocking} 11: This problem can be handled by generating in advance the sequence of all communications and then simply unrolling this sequence as the algorithm progresses. All nodes perform the neighbors selection protocol starting with the same seed and only consider the communications they are involved in. Therefore, they can count the number of iterations completed. This way of selecting neighbours can cause some nodes to wait for the gradient of a busy node before they can actually perform their update. Since the communication schedule is defined in advance, they cannot choose a free neighbor and exchange with him instead. However, any way of making edges sampled independent from the previous ones would be equivalent to generating the sequence in advance. Indeed, choosing free neighbors over busy ones would introduce correlations with the current state and therefore with the edges sampled in the past.

z dist = receive_gradient(j) {blocking} 12: g t (r) = s e (z r -z dist ) 13: v t+1 (r) T y t+1 (r) T r = B v t (r) T y t (r) T -g t (

Performances

Homogeneous decentralized networks

In this section, we introduce two network-related assumptions under which the performances of ES-DACD are provably comparable to the performances of randomized gossip averaging or SSDA. We denote p max = max ij p ij and p min = min ij p ij . We also note p(G) = max i p i and p(G) = min i p i the maximum and minimum probabilities of nodes of a graph G where p i = n i=1 p ij . We note d max and d min the maximum and minimum degrees in the graph. The dependence on G will be omitted when clear from the context. Assumption 1. We say that a family of graph G with edge weights p is quasi-regular if there exists a constant c such that for n ∈ N, p max ≤ cp min and d max ≤ cd min .

Assumption 1 is satisfied for many standard graphs and probability distribution over edges. In particular, it is satisfied by the uniform distribution for regular degree graphs.

Assumption 2. The family of graphs G is such that there exists a constant c such that for n ∈ N,

max ij e T ij A + Ae ij ≤ c n E
where A is of the form of Equation (9) with µ ij = 1 and uniquely defines G(n).

This second assumption essentially means that removing one edge or another should have a similar impact on the connectivity of the graph. It is verified with c = 1 if the graph is completely symmetric (ring or complete graph). Since A + A is a projector, e T ij A + Ae ij ≤ 1 so Assumption 2 holds true any time the ratio n E is bounded below. In particular, the grid, the hypercube, or any random graph with bounded degree respect Assumption 2.

Average time per iteration

ESDACD updates are much cheaper than the updates of any global synchronous algorithm such as SSDA. However, the partial synchrony discussed in Section 3.4 may drastically slow the algorithm down, making it inefficient to use cheaper iterations. Theorem 2 shows that this does not happen for regular graphs with homogeneous probabilities. We note τ max the maximum delay of all edges.

Theorem 2. If we denote T max (k) the time taken by ESDACD to perform k iterations when edges are sampled according to the distribution p:

τ = E 1 k T max (k) ≤ cpτ max ( 14
)
with a constant c < 14.

The proof of Theorem 2 is in Appendix A. Note that the constant can be improved in some settings, for example if all nodes have the same degrees and all edges have the same weight then a tighter bound c < 4 holds.

Corollary 1. If G satisfies Assumption 1 then there exists c > 0 such that for any n ∈ N, the expected average time per iteration taken by ESDACD in G(n) when edges are sampled uniformly verifies:

E [T max (k)] ≤ c τ max n k + o(k). (15)
Corollary 1 shows that when all nodes have comparable activation frequencies then the expected time required to complete one ESDACD iteration scales as the inverse of the number of nodes in the network. This result essentially means that the synchronization cost of locking edges does not grow with the size of the network and so iterations will not be longer on a bigger network. At any given time, a constant fraction of the nodes is actively performing an update (rather than waiting for a message) and this fraction does not shrink as the network grows. The time per iteration can be as high as τ max for some graph topologies that break Assumption 1, e.g., star networks. These topologies are more suited to centralized algorithms because some nodes take part in almost all updates.

Distributed average consensus

Algorithm 2 solves the problem of distributed gossip averaging if we set

f i (θ) = 1 2 θ -c i 2 . In this setting, f * i (x) = 1 2 x + c i 2 -1 2 c i 2 and so ∇f * i (x) = x + c i .
Local smoothness and strong convexity parameters are all equal to 1.

At each round, an edge is chosen and nodes exchange their current estimate of the mean (which is equal to e T i y t +c i for node i). Yet, they do not update it directly but they keep two sequences y t and v t that are updated according to a linear system. One step simply consists in doing a convex combination of these values at the previous step, plus a mixing of the current value with the value of the chosen neighbor.

The standard randomized gossip iteration consists in choosing an edge (i, j) and replacing the current values of nodes i and j by their average. If we denote E 2 (t) the second moment of the error at time t:

E 2 (t) ≤ (1 -θ gossip ) 2t E 2 (0), (16)
where [START_REF] Boyd | Randomized gossip algorithms[END_REF]. Corollary 2. If G satisfies Assumption 2 then there exists c > 0 such that for any n ∈ N, if θ ESDACD is the rate ESDACD in G(n) and θ gossip the rate of randomized gossip averaging when edges are sampled uniformly then they verify:

θ gossip = λ + min ( W ), with W = 1 E L if L is the Laplacian matrix of the graph
θ ESDACD ≥ c √ n θ gossip . (17)
We can use tools from [START_REF] Mohar | Some applications of laplace eigenvalues of graphs[END_REF] to estimate the eigenvalues of usual graphs. In the case of the complete graph, θ gossip ≈ n -1 and so θ ESDACD ≈ θ gossip .

Actually, we can show that in this case, ESDACD iterations are exactly the same as randomized gossip iterations. In the case of the ring graph, θ gossip ≈ n -3 and so θ ESDACD ≈ n -2 which is significantly better for n large. For the grid graph, a similar analysis yields θ ESDACD = O(n -3/2 ). Achieving this message complexity on a grid is an active research area and is often achieved with complex algorithms like geographic gossip [START_REF] Alexandros G Dimakis | Geographic gossip: efficient aggregation for sensor networks[END_REF], relying on overlay networks, or LADA [START_REF] Li | Location-aided fast distributed consensus[END_REF], using lifted Markov chains [START_REF] Diaconis | Analysis of a nonreversible markov chain sampler[END_REF]. Although synchronous gossip algorithms achieved this rate [START_REF] Boris N Oreshkin | Optimization and analysis of distributed averaging with short node memory[END_REF], finding an asynchronous algorithm that could match the rates of geographic gossip was still, to the best of our knowledge, an open area of research [START_REF] Alexandros G Dimakis | Gossip algorithms for distributed signal processing[END_REF].

Therefore, ESDACD shows improved rate compared with standard gossip when the eigengap of the gossip matrix is small. To our knowledge, this is the first time that better convergence rates of the second moment of the error are proven. Indeed, though they both show improved rates in expectation, the shift-register approach (Cao et al., 2006;[START_REF] Liu | Analysis of accelerated gossip algorithms[END_REF]) has no proven rates for the second moment and the rates for the second moment of heavy ball gossip [START_REF] Loizou | Accelerated gossip via stochastic heavy ball method[END_REF] do not improve over standard randomized gossip averaging. Surprisingly, our results show that gossip averaging is best analyzed as a special case of a more general optimization algorithm that is not even restricted to quadratic objectives. Standard acceleration techniques shed a new light on the problem and allows for a better understanding of it.

We acknowledge that the improved rates of convergence do not come for free. The accelerated gossip algorithm requires some global knowledge on the graph (eigenvalues of the gossip matrix and probability of activating each edge). Even though these quantities can be approximated relatively well for simple graphs with a known structure, evaluating them can be more challenging for more complex graphs (and can be even harder than or of equivalent difficulty to the problem of average consensus). Yet, we believe that ESDACD as a gossip algorithm can still be practical in many cases, in particular when values need to be averaged over the same network multiple times or when computing resources are available at some time but not at the time of averaging. Such use cases can typically be encountered in sensor networks, in which the computation of such hyperparameters can be anticipated before deployment. In any case, the analysis shows that standard optimization tools are useful to analyze randomized gossip algorithms.

Comparison to SSDA

The results described in Theorem 1 are rather precise and allow for a fine tuning of the edges probabilities depending on the topology of the graph and of the local smoothnesses. However, the rate cannot always be expressed in a way that makes it simple to compare with SSDA.

Corollary 3. Let G be a family of graph verifying Assumptions 1 and 2. There exists c > 0 such that:

θ ESDACD τESDACD ≥ c 1 τ max γ κ = c θ SSDA τSSDA , ( 18
)
where θ ESDACD is the rate of ESDACD when edges are sampled uniformly and θ SSDA the rate of SSDA when both algorithms use matrix A as defined in Equation (9).

The proof is in Appendix B. Actually, sampling does not need to be uniform but a ratio p min /p max would appear in the constant otherwise. The result of Corollary 3 means that asynchrony comes almost for free for decentralized gradient descent in these cases. Indeed, both algorithms scale similarly in the network and optimization parameters. Note that in this case, we compare ESDACD and SSDA (and not MSDA) meaning that we implicitly assume that communication times are greater than computing times. This is because ES-DACD is very efficient in terms of communication but not necessarily in terms of gradients.

Corollary 3 states that the rates per unit of time are similar. Figure 1 compares the two algorithms in terms of network and computational resources usage.

SSDA iterations require all nodes to send messages to all their neighbors, resulting in a very high communication cost. ESDACD avoids this cost by only performing local updates. SSDA uses n/2 times more gradients per iterations so both algorithms have a comparable cost in terms of gradients.

At each SSDA iteration, nodes need to wait for the slowest node in the system whereas many nodes can be updated in parallel with ESDACD. ESDACD can thus be tuned not to sample slow edges too much, or on the opposite to sample quick edges but with highly non-smooth nodes at both ends more often.

Edge updates yield a strong correlation between the probabilities of sampling edges and the final rate. In heterogeneous cases (in terms of functions to optimize as well as network characteristics), the greater flexibility of ESDACD allows for a better fine-tuning of the parameters (step-size) and thus for better rates.

Experiments

ESDACD vs. gossip averaging

The goal of this part is to illustrate the rate difference depending on the topology of the graph. We study graphs of n nodes where 10% of the nodes have value 1 and the rest have value 0. Similar results are obtained with values drawn from Gaussian distributions.

Figures 2 and3 show that ESDACD consistently beats standard and heavy ball gossip [START_REF] Loizou | Accelerated gossip via stochastic heavy ball method[END_REF]). The clear rates difference for the ring graph shown in Figure 3 illustrates the fact that ESDACD scales far better for graphs with low connectivity. We chose the best performing parameters from the original paper (ω = 1 and β = 0.5) for heavy ball gossip. ESDACD is slightly slower at the beginning because we chose constant and simple learning rates. Choosing B 0 and A 0 from Appendix C as in [START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF] would lead to a more complex algorithm with better initial performances.

ESDACD vs. SSDA

In order to assess the performances of the algorithm in a fully controlled setting, we perform experiments on two synthetic datasets, similar to the one used by Scaman et al. ( 2017): • Regression: Each node i has a vector of N observations, noted X i ∈ R d×N with d = 50 drawn from a centered Gaussian with variance 1. The targets y i,j are obtained by applying function g : x → xi,j + cos(x j ) + where xj = d -1 1 T X i e j and is a centered Gaussian noise with variance 0.25. At each node, the loss function is

f i (θ i ) = 1 2 X T i θ -y i 2 + c i θ 2 with c i = 1.
• Classification: Each node i has a vector of N observations, noted X i ∈ R d×N with d = 50.

Observations are drawn from a Gaussian of variance 1 centered at -1 for the first class and 1 for the second class. Classes are balanced. At each node, the loss function is

f i (θ i ) = N j=1 ln 1 + exp -yi,j X T i,j θ + c i θ 2 with c i = 1.
Our main focus is on the speed of execution. Recall that edge (i, j) takes time τ ij to transmit a message and so if node i starts its k i th update at time t i (k i ) then t i (k i + 1) = max l=i,j t l (k l ) + τ ij and the same for j. This gives a simple recursion to compute the time needed to execute the algorithm in an idealized setting, that we use as the x-axis for the plots.

To perform the experiments, the gossip matrix chosen for SSDA is the Laplacian matrix and Experiments are conducted on the 10 × 10 grid network. We perform n/4 times more iteration for ES-DACD than for SSDA. Therefore, in our experiments, an execution of SSDA uses roughly 2 times more gradients and 8 times more messages (for the grid graph) than an execution of ESDACD. This also allows us to compare the resources used by the 2 algorithms.

µ 2 ij = p 2 ij (σ -1 i + σ -1 j ) -1 is chosen for ESDACD. The error plotted is the maximum suboptimality max i F (θ i ) -min x F (x).
Homogeneous setting: In this setting, we choose uniform constant delays and N = 150 for each node. We notice on Figure 4 that SSDAis roughly two times faster than ESDACD, meaning that n/8 ES-DACD iterations are completed in parallel by the time SSDA completes one iteration. This means that in average, a quarter of the nodes are actually waiting to complete the schedule, since 2 nodes engage in each iteration.

Heterogeneous setting: In this setting, N is uniformly sampled between 50 (problem dimension) and 300, thus leading to very different values for the local condition numbers. Delays are all exponentially distributed with parameter 1. Figure 5 shows that ES-DACD is computationally more efficient than SSDA on the regression problem because it has a far lower final error although it uses 2 times less gradients. This can be explained by larger step sizes along regular edges and suggests that ESDACD adapts more easily to changes in local regularity, even with uniform sampling probabilities. ESDACD is also much faster since in average, each node performs 2 iterations in half the time needed for one SSDA iteration. For the classification problem, strong convexity is more homogeneous because it only comes from regularization. Therefore, ESDACD does not take full advantage of the local structure of the problem and show performances that are similar to those of SSDA.

Conclusion

In this paper, we introduced the Edge Synchronous Dual Accelerated Coordinate Descent (ESDACD), a randomized gossip algorithm for the optimization of sums of smooth and strongly convex functions. We showed that it matches the performances of SSDA, its synchronous counterpart. Empirically, ESDACD even outperforms SSDA in heterogeneous settings. Applying ESDACD to the distributed average consensus problem yields the first asynchronous gossip algorithm that provably achieves better rates in variance than the standard randomized gossip algorithm, for example matching the rate of geographic gossip [START_REF] Alexandros G Dimakis | Geographic gossip: efficient aggregation for sensor networks[END_REF]) on a grid.

Promising lines of work include a communication accelerated version that would match the speed of MSDA [START_REF] Scaman | Optimal algorithms for smooth and strongly convex distributed optimization in networks[END_REF] when computations are more expensive than communications, a fully asynchronous extension that could handle late gradients as well as a stochastic version of the algorithm that would only use stochastic gradients of the local functions.

A Detailed average time per iteration proof

The goal of this section is to prove Theorem 2. The proof develops an argument similar to the one of Theorem 8.33 [START_REF] Baccelli | Synchronization and linearity: an algebra for discrete event systems[END_REF]). Yet, the theorem cannot be used directly and we need to specialize the argument for our problem in order to get a tighter bound. We note t the number of iterations that the algorithm performs, and we introduce the random variable X t (i, w) such that if edge (i, j) is activated at time t + 1 (with probability p ij ), then for all w ∈ N * : X t+1 (i, w) = X t (i, w -1) + X t (j, w -1).

and X t+1 (k, w -1) = X t (k, w -1) otherwise. We start with the initial conditions X 0 (i, 0) = 1 and X 0 (i, w) = 0 for any w > 0. The following lemma establishes a relationship between the time taken by the algorithm to complete t iterations and variables X t .

Lemma 1. If we note T max (t) the time at which the last node of the system finishes iteration t then for all θ > 0:

E [T max (t)] ≤ θt + w≥θt n i=1 E X t (i, w) .
Proof. We first prove by induction on t that if we denote T i (t) the time at which node i finishes iteration t, then for any i ∈ {1, .., n}:

T i (t) = max w∈N,X t (i,w)>0 w. (19)
To ease notations, we write w max (i, t) = max w∈N,X t (i,w)>0 w. The property is true for t = 0 because T i (0) = 0 for all i.

We now assume that it is true for some fixed t > 0 and we assume that edge (k, l) has been activated at time t. For all i / ∈ {k, l}, T i (t + 1) = T i (t) and for all w ∈ N * , X t+1 (i, w -1) = X t (i, w -1) so the property is true. Besides, w max (k, t + 1) = max w∈N * ,X t (k,w-1)+X t (l,w-1)>0 w = max w∈N,X t (i,w)+X t (i,w)>0

w + 1 = 1 + max (w max (k, t), w max (l, t))

= 1 + max (T k (t), T l (t)) = T k (t + 1).
We finish the proof of Equation ( 19) by observing that k and l are completely equivalent.

The form of the recurrence guarantees that for any fixed t ∈ N and w > 1, if there exists i such that X t (i, w) > 0 then for any w < w, there exists j such that X t (j, w ) > 0. Therefore,

T max (t) = max i max w∈N,X t (i,w)>0 w = max w∈N, i X t (i,w)>0 w = w∈N 1 n i=1 X t (i, w) ≥ 1 , (20)
because having X t (i, w) > 0 is equivalent to having X t (i, w) ≥ 1 since X t (i, w) is integer valued. Therefore, for any θ ∈ [0, 1]

T max (t) ≤ θt + w≥θt 1 n i=1 X t (i, w) ≥ 1 ,
and the proof results from taking the expectation of the previous inequality and using Markov inequality on the second term.

Although there is still a maximum in the expression of T i (t), the recursion for variable X has a much simpler form. In particular, we will crucially exploit its linearity. We write p i = j p ij and introduce p = min i p i and p = max i p i . We now prove the following Lemma:

Lemma 2. For all i, if δ 1 = p, δ 2 = p and δ = 2δ2-δ1 1-2δ2 then for all θ > 0 p≥θt

E X t (i, p) ≤ (1 + δ) t P [Binom(2δ 2 , t) ≥ θt] . (21)
Proof. Taking the expectation over the edges that can be activated gives:

E X t+1 (i, w) = (1 -p i ) E X t (i, w) + j p ij E X t (j, w -1) + p i E X t (i, w -1) . (22)
In particular, for all i, E X t+1 (i, w) ≤ Xt (w) where X0 (w) = 1 if w = 0 and 0 otherwise, and:

Xt+1 (w) = (1 -p) Xt (w) + 2p Xt (w -1). ( 23
)
We now introduce φ t (z) = w∈N z w Xt (w). A direct recursion leads to:

φ t (z) = (1 -p + 2pz) t . (24)
Then, using the fact that δ > 0:

φ t (z) ≤ (1 + δ) t 1 -2δ 2 + 2δ 2 1 + δ z t ≤ (1 + δ) t (1 -2δ 2 + 2δ 2 z) t = (1 + δ) t φ bin (2δ 2 , t)(z), (25)
where φ bin (2δ 2 , t) is the generating function of the Binomial law of parameters 2δ 2 and t. The inequalities above on the integral series φ t and (1 + δ) t φ bin (2δ 2 , t) actually hold coefficient by coefficient. Therefore, E [X t (i, p)] ≤ (1 + δ) t P (Binom(2δ 2 , t) = p)

We conclude the proof of the theorem with this last lemma:

Lemma 3. If θ = 6δ 2 + δ then: lim t∈N w≥θt E X t (i, w) = 0 (26)
Proof. We use tail bounds for the Binomial distribution [START_REF] Arratia | Tutorial on large deviations for the binomial distribution[END_REF] in order to get for θ ≥ 2δ 2 :

ln P [Binom(2δ 2 , t) ≥ θt] ≤ -tD(θ||2δ 2 ), (27)
where D(p||q) = p ln p q + (1 -p) ln 1-p 1-q so applying Lemma 2 yields:

w≥θt E X t (i, w) ≤ e -t[D(θ||2δ2)-ln(1+δ)] . (28)
Therefore, we are left to prove that D(θ||2δ 2 ) -ln(1 + δ) > 0. However,

D(θ||2δ 2 ) = 2δ 2 ln( 2δ 2 θ ) + (1 -2δ 2 ) ln 1 -2δ 2 1 -θ ≥ 2δ 2 ln( 2δ 2 θ ) -2δ 2 + θ (29) by using that x 1+x ≤ ln(1 + x) ≤ x. Since θ = 6δ 2 + δ and δ ≤ 2δ2 1-2δ2 , assuming that δ 2 ≤ 3 8 yields: D(θ||2δ 2 ) ≥ 2δ 2 2 -ln(3 + δ 2δ 2 ) + δ > δ ≥ ln(1 + δ). (30)
If δ 2 ≥ 3 8 , then θ > 1 so the result is obvious because X t (i, w) = 0 for w > t.

B Execution speed comparisons

B.1 Comparison with gossip

In this section, we prove Corollary 2.

Proof. We consider a matrix A such that Ae ij = µ ij (e i -e j ) and µ 2 ij = 1 2 for all (i, j) ∈ E. Then multiplying by W ij = Ae ij e T ij A T corresponds to averaging the values of nodes i and j and so the rate of uniform randomized gossip averaging depends on W

= E[W ij ].
In this case, applying ESDACD with matrix A yields a rate of

θ ESDACD = min ij p ij µ ij σ -1 i + σ -1 j λ + min (A T A) e ij A + Ae ij ≥ λ + min (AA T ) cnE ( 31
)
where c is a constant independent of the size of the graph coming from Assumption 2.

Since W = 1 E AA T then θ gossip = 1 E λ + min (AA T ) and so:

θ ESDACD ≥ c √ n θ gossip (32)
with c = c -1 2 .

B.2 Comparison with SSDA

In this section, we prove Corollary 3. SSDA is based on an arbitrary gossip matrix whereas the rate of ESDACD is based on a specific matrix A T A where Ae ij = µ ij (e i -e j ). Yet, W = AA T is a perfectly valid gossip matrix. Indeed, Ker(W ) = Ker(A) = V ec (1) and AA T is an n × n symmetric positive matrix defined on the graph G(n).

Besides, λ + min (A T A) = λ + min (AA T ), which enables us to compare the rates of SSDA and ESDACD.

Proof. For arbitrary µ, the rate of ESDACD writes:

θ ESDACD ≥ min ij p ij µ ij L max (σ -1 i + σ -1 j )e T ij A + Ae ij λ + min (A T A). (33)
Here, we choose µ 2 ij = 1 2 , which yields the bound:

θ ESDACD ≥ p min λ max (AA T ) max ij e T ij A + Ae ij γ κ . (34)
Therefore, combining this with Theorem 2 and Assumption 2 gives:

θ ESDACD τESDACD ≥ p min √ E cpτ max λ max (AA T ) n γ κ ≥ c τ max p min p max d min d max E nd max γ κ ( 35
)
where we have used that λ max ≥ 1 n T r(AA T ) ≥ d min and p ≤ p max d max . We then use Assumption 1 to get that there exists c such that:

θ ESDACD τESDACD ≥ c τ max γ κ = c θ SSDA τSSDA (36)
In the proof above, it appears that having probabilities that are too unbalanced harms the convergence rate of ESDACD. However, if these probabilities are carefully selected to match the square root of the smoothness along the edge, and if delays are such that this does not cause very slow edges to be sampled too often then unbalanced probabilities can greatly boost the convergence rate.

C Detailed rate proof

The proof of Theorem 1 is detailed in this section. Recall that we note A + the pseudo-inverse of A and we define the scalar product x, y A + A = x T A + Ay. The associated norm is a semi-norm because A + A is positive semi-definite. Since A + A is a projector on the orthogonal of Ker(A), it is a norm on the orthogonal of Ker(A).

Our proof follows the key steps of [START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF]. However, we study the problem in the norm defined by A + A because our problem is strongly convex only on the orthogonal of Ker(A). Matrix A can be tuned so that F * A has the same smoothness in all directions, thus leading to optimal rates. We start by two small lemmas to introduce the strong convexity and smoothness inequalities for the A + A semi-norm. We note U ij = e ij e T ij . Lemma 4 (Strong convexity of F * A ). For all x, y ∈ R E ,

F * A (x) -F * A (y) ≥ ∇F * A (y) T (x -y) + σ A 2 x -y 2 A + A (37)
with σ A = λ + min (A T A) Lmax

Proof. Inequality (37) is obtained by writing the strong convexity inequality for each f * i and then summing them. Then, we remark that L i ≤ L max for all i and that Aw 2 = Aw 2 A + A ≥ λ + min (A T A) w 2 A + A for w = x -y. More specifically: Lemma 5 (Smoothness of F * A ). We note x t+1 = y t -h kl U kl ∇F * A (y t ) where h -1 kl = µ 2 kl (σ -1 k + σ -1 l ). If edge (k, l) is sampled at time t,

F * A (x) -F * A (y) =
F * A (x t+1 ) -F * A (y t ) ≤ - 1 2µ 2 kl σ -1 k + σ -1 l U kl ∇F * A (y t ) 2 . ( 38
)
Equation ( 38) can be seen as an ESO inequality [START_REF] Richtárik | Parallel coordinate descent methods for big data optimization[END_REF] applied to the directional update h kl U kl ∇F * A (y t ).

Proof. Assuming that edge (k, l) is drawn at time t, we use that each f * i is (σ -1 i )-smooth to write: Then, we decompose by using that Ae ij = µ ij (e i -e j ) and U kl = e kl e T kl to get that

f * i e T i Ax
F * A (x t+1 ) -F * A (y t ) ≤ ∇F * A (y t ) T U kl -h kl + 1 2 h 2 kl µ 2 kl (σ -1 k + σ -1 l ) ∇F * A (y t ).
We conclude the proof by using the fact that h kl = 1 µ 2 kl (σ -1 k +σ -1 l ) .

We can now start the proof of Theorem 1. We first prove the convergence of a different algorithm which is essentially the one by [START_REF] Nesterov | Efficiency of the accelerated coordinate descent method on structured optimization problems[END_REF] and show that Algorithm 1 is obtained for a specific choice of initial conditions.

Proof. More specifically, we choose A 0 , B 0 ∈ R and recursively define the following coefficients:

a 2 t+1 S 2 = A t+1 B t+1 (39)
B t+1 = B t + σ A a t+1 (40)
A t+1 = A t + a t+1 (41)

α t = a t+1 A t+1 (42)
β t = σ A a t+1 B t+1 . ( 43
)
Then, we take arbitrary x 0 , y 0 , v 0 ∈ R E×d and recursively define:

y t = (1 -α t )x t + α t (1 -β t )v t 1 -α t β t (44) v t+1 = (1 -β t )v t + β t y t - a t+1 B t+1 p ij U ij ∇F * A (y t ) (45)
x t+1 = y t - 1 µ 2 ij (σ -1 i + σ -1 j ) U ij ∇F * A (y t ). ( 46
)
For convenience, we write w t = (1 -β t )v t + β t y t . Then, we study the quantity r 2 t = v t -x * 2 A + A where x * is the minimizer of F * A . Recall that g ij (y t ) = at+1 Bt+1pij U ij ∇F * A (y t ).

v t+1 -x * 2 A + A = w t -x * 2 A + A + a t+1 B t+1 p ij U ij ∇F * A (y t ) 2 A + A -2 a t+1 B t+1 p ij ∇F * A (y t ) T U ij A + A(w t -x * ). (47)
Then,

E ij [ a t+1 B t+1 p ij ∇F * A (y t ) T U ij ] = ij p ij a t+1 B t+1 p ij ∇F * A (y t ) T U ij = a t+1 B t+1 ∇F * A (y t ) T . (48)
Therefore, Equation ( 47) can be rewritten:

  Proceedings of the 22 nd International Conference on Artificial Intelligence and Statistics (AISTATS) 2019, Naha, Okinawa, Japan. PMLR: Volume 89. Copyright 2019 by the author(s).

AlgorithmFigure 1 :

 1 Figure 1: Per iteration costs of SSDA and ESDACD for quasi-regular graphs.

Figure 2 :

 2 Figure 2: ESDACD, pairwise gossip and heavy ball gossip on the 10 × 10 grid.

Figure 3 :

 3 Figure 3: ESDACD, pairwise gossip and heavy ball gossip on the ring graph of size 100.

Figure 4 :

 4 Figure 4: Homogeneous regression problem

Figure 6 :

 6 Figure 6: Heterogeneous classification problem.

  y) T A T A(x -y) ≥ ∇F * A (y) T (x -y) + λ min (A T A) 2L max x -y 2 A + A

  Even though updates are actually local, nodes need to keep track of the total number of updates performed (variable t) in order to properly execute Algorithm 2.

		r) T
	14:	t r = t + 1
	15:	end if
	16:	t = t + 1
	17: end while
	18: return z r
	3.4 Communication schedule

  t+1 -f * i e T i Ay t ≤ -h kl ∇f * i e T i Ay t T e T i AU kl ∇F * A (y t ) + 1 2σ i h kl e T i AU kl ∇F * A (y t ) 2 .Summing it over all values of i gives:F * A (x t+1 ) -F * A (y t ) ≤ ∇F * A (y t ) T -h kl U kl +

	1 2	h 2 kl U kl A T	n i=1	σ -1 i e i e T i AU kl ∇F * A (y t ).

Acknowledgement

We acknowledge support from the European Research Council (grant SEQUOIA 724063).

Now, the goal is to write a smoothness equation to control the middle term and make F * A (x t+1 ) appear. This control is provided by Equation (38) in Lemma 5.

Therefore, if we choose S such that for all (i, j),

≤ S 2 then the equation becomes:

We use the convexity of the squared norm to get that w t -x * 2

Then, if we multiply both sides by B t+1 we get:

We can now use Equation ( 37) of Lemma 4 (strong convexity of F * A in norm A + A) to write that:

Then, we combine the previous inequality with Equation (51) and we use the fact that B t+1 β t = a t+1 σ A so that:

and so:

By summing over all inequalities, we get that

Now, we need to estimate the growth of coefficients A t and B t . We prove by induction on t that if A 0 = 1 and

We can first combine Equation ( 41) and Equation ( 42) to obtain

For t = 0, we can combine equations ( 55) and ( 56) to obtain that α -1 0 -1 = β -1 0 -1 (since a 1 = 0 and so α 0 = β 0 . Finally,

S . Now suppose that the property is true for a given t ≥ 0. Then, we use Equation ( 55) and the fact that

.

We use Equation ( 56) in the same way to prove that B t+1 = σ A A t+1 .

Then, we use equations ( 55) and ( 56) at time t + 1 to get that α -1 t+1 -1 = β -1 t+1 -1 so α t+1 = β t+1 . Their value can again be retrieved by using Equation ( 39), which finishes the induction.

We have proven that for this choice of A 0 and B 0 the α and β coefficients are constant and are equal to θ =

With this choice of parameters, y t+1 can be expressed as:

Then, the coefficients of Algorithm 1 are recovered by replacing x t+1 and v t+1 by their expressions in Equations ( 46) and ( 45). The actual values of a t+1 , A t+1 and B t+1 are only used for the analysis because only at+1 Bt+1 = σ A βt appears in the recursion.