Asynchronous Speedup in Decentralized Optimization

Mathieu Even1, Hadrien Hendrikx 2 and Laurent Massoulié1,3

1Inria - Département d’informatique de l’ENS

2EPFL

3MSR-Inria Joint Centre

###### Abstract.

In decentralized optimization, nodes of a communication network each possess a
local objective function, and communicate using gossip-based methods in order
to minimize the average of these per-node functions. While synchronous
algorithms are heavily impacted by a few slow nodes or edges in the graph (the
_straggler problem_), their asynchronous counterparts are notoriously harder
to parametrize. Indeed, their convergence properties for networks with
heterogeneous communication and computation delays have defied analysis so
far.

In this paper, we use a _continuized_ framework to analyze asynchronous
algorithms in networks with delays. Our approach yields a precise
characterization of convergence time and of its dependency on heterogeneous
delays in the network. Our continuized framework benefits from the best of
both continuous and discrete worlds: the algorithms it applies to are based on
event-driven updates. They are thus essentially discrete and hence readily
implementable. Yet their analysis is essentially in continuous time, relying
in part on the theory of delayed ODEs.

Our algorithms moreover achieve an _asynchronous speedup_ : their rate of
convergence is controlled by the eigengap of the network graph weighted by
local delays, instead of the network-wide worst-case delay as in previous
analyses. Our methods thus enjoy improved robustness to stragglers.

##  1\. Introduction

We study the following optimization problem:

$\min_{x\in\mathbb{R}^{d}}\left\\{f(x)=\sum_{i=1}^{n}f_{i}(x)\right\\}\,,$ (1)

where each individual function $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ for
$i\in[n]$ is held by an agent $i$. We consider _asynchronous_ and
_decentralized_ optimization methods that do not rely on a central
coordinator. This is particularly relevant in large-scale systems in which
centralized approaches suffer from a communication bottleneck at the central
controller. Decentralized optimization is relevant to supervised learning of
models in data centers, but also to more recent federated learning scenarios
where data and computations are distributed among agents that do not wish to
share their local data. We focus on asynchronous operations because of their
scalability in the number of agents in the system, and their robustness to
node failures and to _stragglers_. In the case of empirical risk minimization,
$f_{i}$ represents the empirical risk for the local dataset of node $i$, and
$f$ the empirical risk over all datasets. Another important example, that
plays the role of a toy problem for both decentralized and/or stochastic
optimization is that of network averaging, corresponding to
$f_{i}(x)={{\left\|x-c_{i}\right\|}}^{2}$ where $c_{i}$ is a vector attached
to node $i$. In this case, the solution of Problem (1) reads
$\bar{c}=\frac{1}{n}\sum_{i=1}^{n}c_{i}$.

###  1.1. Decentralized and asynchronous setting

We assume that agents are located at the nodes of a connected, undirected
graph $G=(V,E)$ with node set $V=[n]$. An agent $i\in V$ can compute first-
order quantities (gradients) related to its local objective function $f_{i}$,
and can communicate with any adjacent agent in the graph. Our model of
asynchrony derives from the popular randomized gossip model of Boyd et al.
(2006). In this model, nodes update their local values at random activation
times using pairwise communication updates. This asynchronous model makes the
idealized assumption of instantaneous communications, and hence does not
faithfully represent practical implementations. To alleviate this drawback,
several works (Assran and Rabbat, 2021; Sirb and Ye, 2018; Wu et al., 2018;
Wang et al., 2015; Li et al., 2016; Lian et al., 2018) introduce communication
and computation delays in either pairwise updates, or in asymmetric gossip
communications.

However, all these works provide convergence guarantees that either require
global synchronization between the nodes, or are implicitly determined by an
upper bound on the worst-case delay in the whole graph. Indeed they assume
that i) for some $k_{\max}>0$, for all edges $(ij)\in E$, each communication
between agents $i$ and $j$ overlaps with at most $k_{\max}$ other
communications in the whole graph, and ii) either agents $i$ or graph edges
$(ij)$ are activated for agent interaction sequentially in an i.i.d. manner.
Thus assuming distributed asynchronous operation where individual nodes
schedule their interactions based only on local information, the $k_{\max}$
constraint can only be enforced by requiring individual nodes to limit their
update frequency to $1/(n\tau_{\max})$.

Consequently, the resulting algorithms have temporal convergence guarantees
proportional to $\tau_{\max}$. They are thus not robust to _stragglers_ , i.e.
slow nodes or edges in the graph that induce large $\tau_{\max}$.

To understand the scope for improvement over such methods, recall that for
synchronous algorithms with updates performed every $\tau_{\max}$ seconds, for
$L$-smooth and $\sigma$-strongly convex functions $f_{i}$, the time required
to reach precision $\varepsilon>0$ for $\frac{1}{n}\sum f_{i}$ is lower-
bounded by (Scaman et al., 2017):

$\Omega\left(\tau_{\max}{\rm
Diam}(G)\sqrt{\kappa}\ln(\varepsilon^{-1})\right)\,,$ (2)

where $\kappa=L/\sigma$ is the condition number of the functions $f_{i}$ and
${\rm Diam}(G)$ is the diameter of graph $G$.

In this article we seek better dependency on individual delays in the network.
Specifically we consider the following

######  Assumption 1 (Heterogeneous delays).

There exist $\tau_{ij}$ for $(ij)\in E$ and $\tau_{i}^{\rm comp}$ for $i\in V$
such that communications between two neighboring agents $i$ and $j$ in the
graph take time at most $\tau_{ij}$, and a computation at node $i$ takes time
at most $\tau_{i}^{\rm comp}$.

Under such heterogeneous delay assumptions, how robust to stragglers can
decentralized algorithms be? One can adapt the proof of Scaman et al. (2017)
to Assumption 1 to establish the generalized form of lower bound (2):

$\Omega\left(D(\tau)\sqrt{\kappa}\ln(\varepsilon^{-1})\right)\,,$ (3)

where $D(\tau)=\sup_{(i,j)\in V^{2}}{\rm dist}(i,j)$ for:

${\rm dist}(i,j)=\underset{\forall 1\leq k\leq p,\,(i_{k},i_{k+1})\in
E}{\inf_{(i=i_{0},\ldots,i_{p}=j),}}\tau_{i}^{\rm comp}+\tau_{j}^{\rm
comp}+\sum_{k=0}^{p-1}\tau_{i_{k}i_{k+1}}\,.$

Here ${\rm dist}(i,j)$ is the time distance between nodes $i$ and $j$, and
$D(\tau)$ is the _diameter_ of graph $G$ for this distance. $D(\tau)$ is the
generalization of $\tau_{\max}{\rm Diam}(G)$ to the heterogeneous-delay
setting. This lower bound suggests that robustness to stragglers is possible:
indeed if a fraction of the nodes or edges is too slow (large delay
$\tau_{ij}$), this may not even impact this lower bound, since the shortest
path between two nodes may always take another route.

We aim at building _decentralized_ algorithms with performance guarantees that
enjoy such robustness to individual delay bounds. However, since we focus on
fully decentralized algorithms, our performance guarantees will not be
expressed in terms of some diameter $D(\tau)$ as in (3) but instead in terms
of some spectral characteristics of the graph at hand111Note that similar
spectral characteristics (albeit based on a single worst-case delay parameter
$\tau_{\max}$) appear in Assran and Rabbat (2021); Sirb and Ye (2018); Wu et
al. (2018); Wang et al. (2015); Li et al. (2016); Scaman et al. (2017)..
Specifically, let us introduce the Graph Laplacian.

######  Definition 1 (Graph Laplacian).

Let $\nu=(\nu_{ij})_{(ij)\in E}$ be a set of non-negative real numbers. The
_Laplacian_ of the graph $G$ weighted by the $\nu_{ij}$’s is the matrix
$\Delta_{G}(\nu)$ with $(i,j)$ entry equal to $-\nu_{ij}$ if $(ij)\in E$,
$\sum_{k\sim i}\nu_{ik}$ if $j=i$, and $0$ otherwise. In the sequel $\nu_{ij}$
always refers to the weights of the Laplacian, and
$\lambda_{2}(\Delta_{G}(\nu))$ denotes this Laplacian’s second smallest
eigenvalue.

We thus seek performance guarantees similar to (3) with in place of $D(\tau)$
the term $\lambda_{2}(\Delta_{G}(\nu))^{-1}$ for some parameters $\nu_{ij}$
that depend on delay characteristics local to edge $(ij)$.

###  1.2. Contributions

_(i)_ We first consider the _network averaging problem_ , for which we
introduce _Delayed Randomized Gossip_ in Section 3. Building on recent works
on continuized gradient descent for Nesterov acceleration (Even et al., 2021),
we analyze Delayed Randomized Gossip in the continuized framework, that allows
a continuous-time analysis of an algorithm even though the latter is based on
discrete, hence practically implementable operations. Our analysis leads to
explicit stability conditions that have the appealing property of being
_local_ , i.e. they require each agent to tune its algorithm parameters to
delay bounds in its graph neighborhood.

They ensure a linear rate of convergence determined by
$\lambda_{2}\big{(}\Delta_{G}(\nu)\big{)}$, for weights of order
$\nu=1/(\sum_{(kl)\sim(ij)}\tau_{kl})$222We write $(ij)\sim(kl)$ and say that
two edges $(ij)$, $(kl)$ are neighbors if they share at least one node.. This
dependency of weights in the Laplacian on local delay bounds is what we call
the _asynchronous speedup_ , since it implies a scaling that is no longer
proportional to $\tau_{\max}$.

_(iii)_ Using an augmented graph approach, we propose algorithms that
generalize Delayed Randomized Gossip to solve the decentralized optimization
problem in Section 5. Under strong convexity and smoothness assumptions on the
local functions $f_{i}$, we obtain local stability conditions yielding an
asynchronous speedup for this more general setup.

_(iv)_ We further generalize our setup with the introduction of _local
capacity constraints_ in Section 6, in order to take into account the fact
that nodes or edges cannot handle an unlimited number of operations in
parallel. To that end, we introduce _truncated Poisson point processes_ in the
continuized framework for the analysis.

_(v)_ The theoretical guarantees for our algorithms in Sections 3, 5 and 6 are
all based on general guarantees for so-called delayed coordinate gradient
descent in the continuized framework, that we present and establish in Section
4. These results may be of independent interest beyond our current focus on
decentralized optimization.

_(v)_ Finally, we identify from our stability conditions and convergence
guarantees a phenomenon reminiscent of _Braess_ ’s paradox (Section 7):
deleting some carefully chosen edges can lead to faster convergence. This in
turn suggests rules for sparsifying communication networks in distributed
optimization.

##  2\. Related works

###  2.1. Decentralized Optimization and Gossip Algorithms

Gossip algorithms (Boyd et al., 2006; Dimakis et al., 2010) were initially
introduced to compute the global average of local vectors with local pairwise
communications only (no central coordinator), and were generalized to
decentralized optimization. Two types of gossip algorithms appear in the
literature: synchronous ones, where all nodes communicate with each other
simultaneously (Dimakis et al., 2010; Scaman et al., 2017; Koloskova et al.,
2019; Shi et al., 2015), and randomized ones (Boyd et al., 2006; Nedic and
Ozdaglar, 2009). A third category considers directed (non-symmetric)
communication graphs (Xi et al., 2018; Assran and Rabbat, 2021) which are much
easier to implement asynchronously. In the synchronous framework, the
communication speed is limited by the slowest node (_straggler_ problem),
whereas the classical randomized gossip framework of Boyd et al. (2006)
assumes communications to happen instantaneously, and thus does not address
the question of how to deal with delays. Assran and Rabbat (2021); Sirb and Ye
(2018); Wu et al. (2018); Wang et al. (2015); Li et al. (2016) introduce
delays in the analysis of decentralized algorithms; as mentioned in the
introduction, their analyses and algorithms are not robust to stragglers,
relying on a single upper bound on the delays of all edges. Wang et al. (2019)
study how sparsifying the communication graph can lead to faster decentralized
algorithm. Their approach is different from ours in Section 7: they do not
consider asynchronous algorithms with physical constraints (delays and
capacity), but synchronous algorithms where sequentially matchings are built
in the graph. Yet, we observe similar phenomenon as theirs in Section 7. We
refer the reader to Nedich et al. (2018) for a more complete survey of gossip
algorithms.

###  2.2. Handling Asynchrony

The dynamics of asynchronous optimization algorithms are significantly more
complex than their synchronous counterparts. Their study goes back to the
monograph of Bertsekas (1989), where asynchrony is modelled through a global
ordering of events, providing the formalism classically used. Most of the
recent literature is then derived from a distributed asynchronous variant of
SGD called _HOGWILD!_ (Recht et al., 2011). Mania et al. (2017); Leblond et
al. (2018) introduce alternative orderings of the iterates (before-read and
after-read) that correspond to different views of the same sequence of
updates, and which simplify the analysis through the use of perturbed or
virtual iterates (Mania et al., 2017; Zhou et al., 2018; Hannah et al., 2019;
Mishchenko et al., 2022; Stich and Karimireddy, 2019), even though proofs and
convergence guarantees under realistic assumptions on the intricacies between
iterates, delays and choices of coordinates, are a challenging problem (Sun et
al., 2017; Cheung et al., 2020). We refer the interested reader to Assran et
al. (2020) for a more exhaustive survey of advances in asynchrony, both in
shared-memory and decentralized models. In this paper, we deal with asynchrony
and delays from a different viewpoint: the analysis is inspired by time-
delayed ODE systems (Niculescu, 2001), and the assumptions related to delays
and asynchrony (such as Assumption 1) do not need to be translated into
discrete-time ones, as in the above references. Finally, we believe our
continuous time framework to be particularly adequate for the study and design
of asynchronous algorithms, in the decentralized setting as in this paper, but
also in centralized settings where it may remove the need to introduce a
discrete ordering of events and thus avoid difficulties that lead to
unrealistic assumptions, such as the _after/before-read_ approaches (Leblond
et al., 2018).

##  3\. Delayed Randomized Gossip for Network Averaging

Focusing in this section on the Network Averaging Problem, we introduce
Delayed Randomized Gossip and state its convergence guarantees. We first begin
with reminders on randomized gossip (Boyd et al., 2006).

###  3.1. Randomized gossip

Let $G=(V,E)$ be a connected graph on the set of nodes $V=[n]$, representing a
communication network of agents. Each agent $i\in V$ is assigned a real vector
$x_{0}(i)\in\mathbb{R}^{d}$. The goal of the averaging (or gossip) problem is
to design an iterative procedure allowing each agent in the network to
estimate the average $\bar{x}=\frac{1}{n}\sum_{i=1}^{n}x_{0}(i)$ using only
local communications, _i.e._ , communications between adjacent agents in the
network.

In randomized gossip (Boyd et al., 2006), time $t$ is indexed continuously by
$\mathbb{R}^{+}$. A Poisson point process (Klenke, 2014) (abbreviated as
_P.p.p._ in the sequel) $\mathcal{P}={{\left\\{T_{k}\right\\}}}_{k\geq 1}$ of
intensity $I>0$ on $\mathbb{R}^{+}$ is generated: $T_{0}=0$ and
$(T_{k+1}-T_{k})_{k\geq 0}$ are _i.i.d._ exponential random variables of mean
$1/I$. For positive intensities $(p_{ij})_{(ij)\in E}$ such that
$\sum_{(ij)\in E}p_{ij}=I$, for every $k\geq 0$, at $T_{k}$ an edge
$(i_{k}j_{k})$ is _activated_ with probability $p_{i_{k}j_{k}}/I$, upon which
adjacent nodes $i_{k}$ and $j_{k}$ communicate and perform a pairwise update.
The _P.p.p._ assumption implies that edges are activated independently of one
another and from the past: the activation times of edge $(ij)$ form a _P.p.p._
of intensity $p_{ij}$.

To solve the gossip problem, Boyd et al. (2006) proposed the following
strategy: each agent $i\in V$ keeps a local estimate $x_{t}(i)$ of the average
and, upon activation of edge $(i_{k}j_{k})$ at time $T_{k}\in\mathbb{R}^{+}$,
the activated nodes $i_{k},j_{k}$ average their current estimates:

$x_{T_{k}}(i_{k}),\,x_{T_{k}}(j_{k})\,\longleftarrow\,\frac{x_{T_{k}-}(i_{k})+x_{T_{k}-}(j_{k})}{2}\,.$
(4)

Writing $f(x)=\sum_{(ij)\in E}\frac{p_{ij}}{I}f_{ij}(x)$, for
$f_{ij}(x)=\frac{1}{2}{{\left\|x(i)-x(j)\right\|}}^{2}$ and $x=(x(i))_{i\in
V}$, Even et al. (2021) observe that local averages (4) correspond to
stochastic gradient steps on $f$:

$x_{T_{k}}\,\longleftarrow\,x_{T_{k}-}-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\nabla
f_{i_{k}j_{k}}(x_{T_{k}-})\,,$ (5)

for step sizes $K_{i_{k}j_{k}}=\frac{p_{i_{k}j_{k}}}{2}$.

These updates can also be derived from coordinate gradient descent steps. Let
$A\in\mathbb{R}^{V\times E}$ be such that for all $(ij)\in E$,
$Ae_{ij}=\mu_{ij}(e_{i}-e_{j})$ for arbitrary $\mu_{ij}\in\mathbb{R}$, where
$(e_{ij})_{(ij)\in E}$ and $(e_{i})_{i\in V}$ are the canonical bases of
$\mathbb{R}^{E}$ and $\mathbb{R}^{V}$. Then, let
$g(\lambda)=\frac{1}{2}{{\left\|A\lambda\right\|}}^{2}$ for
$\lambda\in\mathbb{R}^{E\times d}$, so that the coordinate gradient
$\nabla_{ij}g(\lambda)$ writes
$\nabla_{ij}g(\lambda)=\mu_{ij}((A\lambda)_{i}-(A\lambda)_{j})$. Thus,
provided that for some $\lambda_{T_{k}-}\in\mathbb{R}^{E\times d}$,
$x_{T_{k}-}-\bar{x}=A\lambda_{T_{k}-}$, the local averaging defined in
Equation (4) is equivalent to $x_{T_{k}}-\bar{x}=A\lambda_{T_{k}}$, where:

$\lambda_{T_{k}}=\lambda_{T_{k}-}-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}\mu_{i_{k}j_{k}}^{2}}\nabla_{i_{k}j_{k}}g(\lambda_{T_{k}-})\,,$
(6)

for $K_{i_{k}j_{k}}=\frac{p_{i_{k}j_{k}}}{2}$. Hence, the gossip algorithm of
Boyd et al. (2006) can be viewed as a simple block-coordinate gradient descent
on variables $\lambda\in\mathbb{R}^{E\times d}$ indexed by the edges of the
graph instead of the nodes.

Yet, this continuous-time model with _P.p.p._ activations implicitly assumes
instantaneous communications, or some form of waiting. Indeed, the gradient is
computed on the current value of the parameter, which is $x_{T_{k}-}$. In the
presence of (heterogeneous) communication delays (Assumption 1), a more
realistic update uses the parameter $x_{S_{k}}$ at a previous time
$S_{k}<T_{k}$, to account for the time it takes to compute and communicate the
gradient. In this case, the updates write as

$x_{T_{k}}\,\longleftarrow\,x_{T_{k}-}-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\nabla
f_{i_{k}j_{k}}(x_{S_{k}})\,.$ (7)

Equivalently, from the point of view of node $i_{k}$:

$x_{T_{k}}(i_{k})\leftarrow
x_{T_{k}-}(i_{k})-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\big{(}x_{S_{k}}(i_{k})-x_{S_{k}}(j_{k})\big{)}\,.$

###  3.2. The continuized framework

Our approach uses the continuized framework (Even et al., 2021), which amounts
to consider continuous-time evolution of key quantities, with discrete jumps
at the instants of Poisson point processes. This gives the best of both
continuous (for the analysis and assumptions) and discrete (for the
implementation) worlds. From now on and for the rest of the paper, we assume
that Assumption 1 holds.

Edges $(ij)\in E$ locally generate independent _P.p.p._ $\mathcal{P}_{ij}$ of
intensity $p_{ij}>0$ (random activation times, with _i.i.d._ intervals,
exponentially distributed with mean $1/p_{ij}$). As mentioned previously,
$\mathcal{P}=\bigcup_{(ij)\in E}\mathcal{P}_{ij}$ is a _P.p.p._ of intensity
$I=\sum_{(ij)\in E}p_{ij}$, and noting
$\mathcal{P}={{\left\\{T_{1}<T_{2}<\ldots\right\\}}}$, at each clock ticking
$T_{k},\,k\geq 1$, an edge $(i_{k}j_{k})$ is chosen with probability
$p_{i_{k}j_{k}}/I$. This time $T_{k}$ corresponds to a communication update
between nodes $i_{k}$ and $j_{k}$ started at time $T_{k}-\tau_{i_{k}j_{k}}$
333Standard properties of P.p.p. guarantee that the sequence of points of
$\mathcal{P}_{ij}$ translated by $\tau_{ij}$ is a P.p.p. with the same
distribution.. Assumption 1 ensures that the communication started at time
$T_{k}-\tau_{ij}$ takes some time $\tau^{(k)}\leq\tau_{i_{k}j_{k}}$ and is
thus completed before time $T_{k}$ so that the update at time $T_{k}$ is
indeed implementable. Consequently, the sequence $(x_{t})_{t}$ generated by
Algorithm 1 writes as:

$\left\\{\begin{aligned} &x_{T_{k}}(i)=x_{T_{k}-}(i)\quad\text{if}\quad
i\notin{{\left\\{i_{k},j_{k}\right\\}}}\,,\\\ &x_{T_{k}}(i_{k})\leftarrow
x_{T_{k}-}(i_{k})-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\big{(}x_{T_{k}-\tau_{i_{k}j_{k}}}(i_{k})-x_{T_{k}-\tau_{i_{k}j_{k}}}(j_{k})\big{)},\\\
&x_{T_{k}}(j_{k})\leftarrow
x_{T_{k}-}(j_{k})-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\big{(}x_{T_{k}-\tau_{i_{k}j_{k}}}(j_{k})-x_{T_{k}-\tau_{i_{k}j_{k}}}(i_{k})\big{)}.\end{aligned}\right.$

Algorithm 1 is the pseudo-code for _Delayed Randomized Gossip_ , from the
viewpoint of two adjacent nodes $i$ and $j$. The times $T_{\ell}(ij)$ for
$\ell\geq 1$ denote the activation times of edge $(ij)$. They follow a P.p.p.
of intensity $p_{ij}$, and are sequentially determined by adjacent nodes $i$
and $j$.

Formally, this decentralized and asynchronous algorithm corresponds to a jump
process solution of a _delayed stochastic differential equation_. Defining
$N({\rm d}t,(ij))$ as the _Poisson_ measure on $\mathbb{R}^{+}\times E$ of
intensity $I{\rm d}t\otimes\mathcal{U}_{p}$ where $\mathcal{U}_{p}$ is the
probability distribution on $E$ proportional to $(p_{ij})_{(ij)\in E}$
($\mathcal{U}_{p}((ij))=p_{ij}/I$), we have:

${\rm d}x_{t}=-\int_{\mathbb{R}^{+}\times E}\frac{K_{ij}}{p_{ij}}\nabla
f_{ij}(x_{t-\tau_{ij}}){\rm d}N(t,(ij))\,.$ (8)

Next section presents convergence guarantees for iterates generated by delayed
randomized gossip.

Algorithm 1 Delayed randomized gossip, edge $(ij)$

1: Step size $K_{ij}>0$ and intensity $p_{ij}>0$

2: Initialization $T_{1}(ij)\sim{\rm Exp}(p_{ij})$

3: for $\ell=1,2,\ldots$ do

4: $T_{\ell+1}(ij)=T_{\ell}(ij)+{\rm Exp}(p_{ij})$.

5: end for

6: for $\ell=1,2,\ldots$ do

7: At time $T_{\ell}(ij)-\tau_{ij}$ for, $i$ sends
$\hat{x}_{i}=x_{T_{\ell}(ij)-\tau_{ij}}(i)$ to $j$ and $j$ sends
$\hat{x}_{j}=x_{T_{\ell}(ij)-\tau_{ij}}(j)$ to $i$.

8: At time $T_{\ell}(ij)$,  $\displaystyle x_{T_{\ell}(ij)}(i)\leftarrow
x_{T_{\ell}(ij)-}(i)-\frac{K_{ij}}{p_{ij}}\big{(}\hat{x}_{i}-\hat{x}_{j}\big{)}\,,$
(9) $\displaystyle x_{T_{\ell}(ij)}(j)\leftarrow
x_{T_{\ell}(ij)-}(j)-\frac{K_{ij}}{p_{ij}}\big{(}\hat{x}_{j}-\hat{x}_{i}\big{)}\,,$

9: end for

###  3.3. Convergence guarantees

We begin by recalling the key quantities introduced. _(i)_ The constraints
inherent to the problem are the communication delays, upper-bounded by
constants $\tau_{ij}$. _(ii)_ Parameters of the algorithm are: step sizes
$K_{ij}>0$ and intensities $p_{ij}$ of the local P.p.p. that trigger
communications between adjacent nodes $i$ and $j$. For arbitrary intensities
$p_{ij}$ and delay bounds $\tau_{ij}$, we shall provide local conditions on
the step sizes $K_{ij}$ that guarantee stability and convergence guarantees.
This is to be contrasted with the situation –discussed in Section 6– where in
addition there are capacity constraints, for which additional conditions on
the intensities $p_{ij}$ are needed to prove convergence.

######  Theorem 1 (Delayed Randomized Gossip).

Assume that for all $(ij)\in E$, we have444Note that $(ij)\sim(ij)$; constant
$e$ is $\exp(1)$.:

$\displaystyle
K_{ij}\leq\frac{p_{ij}}{1+\sum_{(kl)\sim(ij)}p_{kl}\big{(}\tau_{ij}+e\tau_{kl}\big{)}}\,\cdot$
(10)

Let $\nu_{ij}\equiv K_{ij}$, $(ij)\in E$, and $\tau_{\max}=\max_{(ij)\in
E}\tau_{ij}$. Let $\gamma>0$ be such that:

$\gamma\leq\min\left(\frac{\lambda_{2}\big{(}\Delta_{G}(\nu)\big{)}}{2}\,,\,\frac{1}{\tau_{\max}}\right)\,.$

For any $T\geq 0$, for $(x_{t})_{t\geq 0}$ generated with delayed randomized
gossip (Algorithm 1) or equivalently by the delayed SDE in Equation (8), we
have:

$\frac{\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[{{\left\|x_{t}-\bar{x}\right\|}}^{2}\right]{\rm
d}t}{\int_{0}^{T}e^{\gamma t}{{\left\|x_{0}-\bar{x}\right\|}}^{2}{\rm d}t}\leq
e^{-\frac{\gamma
T}{2}}\frac{1+\frac{\tau_{\max}}{T}}{1-\gamma\tau_{\max}}\,.\vspace{5pt}$ (11)

Using Jensen inequality then yields the following corollary.

######  Corollary 1.

Under the same assumptions as Theorem 1, for $(x_{t})_{t\geq 0}$ generated
with delayed randomized gossip, define $(\tilde{x}_{t})_{t\geq 0}$ as the
exponentially weighted averaging along the trajectory of $(x_{t})$:

$\tilde{x}_{t}=\gamma\frac{\int_{0}^{t}e^{\gamma s}x_{s}{\rm d}s}{e^{\gamma
t}-1}\,.$

Then, for all $T\geq 0$,

$\mathbb{E}\left[{{\left\|\tilde{x}_{T}-\bar{x}\right\|}}^{2}\right]\leq
e^{-\frac{\gamma
T}{2}}{{\left\|x_{0}-\bar{x}\right\|}}^{2}\frac{1+\frac{\tau_{\max}}{T}}{1-\gamma\tau_{\max}}\,.\vspace{5pt}$

An essential aspect of Theorem 1 lies in the explicit sufficient conditions
for convergence it establishes for our proposed schemes, and on how they only
rely on (upper bounds on) individual delays. We now discuss the _asynchronous
speedup_ obtained by fine-tuning algorithm parameters according to delays.

For many graphs of interest such as grids, hypergrids, trees…and bounded edge
parameters $\nu_{ij}$, in the large network limit $n\to\infty$ one has
$\lambda_{2}(\Delta_{G}(\nu))\to 0$555Networks for which this fails are known
as _expanders_. and so $\lambda_{2}(\Delta_{G})\wedge
1/\tau_{\max}=\lambda_{2}(\Delta_{G})$. The _asynchronous speedup_ consists in
having a rate of convergence as the eigengap of the Laplacian of the graph
weighted by local communication constraints: the term
$\lambda_{2}(\Delta_{G}(K))$, where each $K_{ij}$ is impacted only by local
quantities.

As mentioned in the introduction, this quantity should be understood as the
analogue in decentralized optimization of the squared diameter of the graph
(using time distances) in (3) in centrally coordinated algorithms and as
expected, gossip algorithms are affected by spectral properties of the graph.
In Theorem 1, these properties reflect delay heterogeneity across the graph:
here, $\lambda_{2}(\Delta_{G}(K))^{-1}$ the mixing time of a random walk on
the graph where jumping from node $i$ to $j$ takes a time
$\tilde{\tau}_{ij}=K_{ij}^{-1}$. In contrast, previous analyses (of
synchronous or asynchronous algorithms) involve the mixing time of a random
walk with times between jumps set to a quantity that is linearly dependent on
$\tau_{\max}$. We coin this discrepancy the _asynchronous speedup_.

Equation (10) suggests a scaling of $p_{ij}\approx 1/\tau_{ij}$, giving local
weights $K_{ij}$ of order $1/({\rm degree}_{ij}\tau_{ij})$ where ${\rm
degree}_{ij}$ is the degree of edge $(ij)$ in the edge-edge graph. On the
other hand, synchronous algorithms are slowed down by the slowest node: the
equivalent term would be of order $\lambda_{2}(\Delta_{G}(1/({\rm
degree}_{ij}\tau_{\max}))$. Indeed, for a _gossip matrix_
$W\in\mathbb{R}^{V\times V}$ ($W$ is a symmetric and stochastic matrix), the
equivalent factor in synchronous gossip (Dimakis et al., 2010) is
$\lambda_{2}(\Delta_{G}(W_{ij}\tau_{\max}))$, and $W_{ij}$ is usually set as
$1/{\rm degree}_{ij}$ in order to ensure convergence.

Finally, assume that all $\tau_{ij}$ are equal to $\tau_{\max}$, and set
$p_{ij}=1/\tau_{\max}$. We then recover $\lambda_{2}(\Delta_{G}(1/({\rm
degree}_{ij}\tau_{\max}))$ in the rate of convergence $\gamma$, thus yielding
the same rates as synchronous algorithms (Dimakis et al., 2010) and
asynchronous algorithms that only use a global upper bound on the delays
(Assran and Rabbat, 2021; Sirb and Ye, 2018; Wu et al., 2018; Wang et al.,
2015; Li et al., 2016; Lian et al., 2018): albeit being asynchronous, these
algorithms do not take advantage of an asynchronous speedup in their
convergence speed.

###  3.4. A delayed _ODE_ for mean values in gossip

Before proving Theorem 1, we provide some intuition for its conditions and the
resulting convergence rate. We do this by studying the means of the iterates,
that verify a delayed linear ordinary differential equation, easier to study
than the process itself, for which we provide stability conditions.

Denoting $y_{t}=\mathbb{E}\left[x_{t}\right]\in\mathbb{R}^{n\times d}$, for
$t\geq 0$, where $(x_{t})_{t\geq 0}$ is generated using delayed randomized
gossip updates (7), we have:

$\frac{{\rm d}y_{t}}{{\rm d}t}=-\sum_{(ij)\in E}K_{ij}\nabla
f_{ij}(y_{t-\tau_{ij}})\,.$ (12)

Indeed, for any $t\geq 0$ and ${\rm d}t>0$,

$\displaystyle\mathbb{E}\left[x_{t+{\rm d}t}|x_{t}\right]-x_{t}$
$\displaystyle=-x_{t}+(1-I{\rm d}t)x_{t}+o({\rm d}t)$ $\displaystyle\quad+{\rm
d}t\sum_{(ij)\in E}p_{ij}\big{(}x_{t}-\frac{K_{ij}}{p_{ij}}\nabla
f_{ij}(x_{t-\tau_{ij}})\big{)}$ $\displaystyle=-{\rm d}t\sum_{(ij)\in
E}K_{ij}\nabla f_{ij}(x_{t-\tau_{ij}})+o({\rm d}t)\,.$

Taking the mean, dividing by ${\rm d}t$ and making ${\rm d}t\to 0$ leads to
the delayed ODE verified by $y_{t}=\mathbb{E}\left[x_{t}\right].$ Such delay-
differential ODEs are classical (Niculescu, 2001) yet their stability
properties are notoriously hard to characterize. This is typically attacked by
means of _Lyapunov-Krasovskii_ functionals or _Lyapunov-Razumikhin_ functions
(Gu and Liu, 2009). Alternatively, sufficient conditions for convergence and
stability guarantees on $(y_{t})$ can be obtained, under specific conditions,
by enforcing stability of the original system after _linearizing_ it with
respect to delays (Massoulié, 2002). Linearizing in the sense of Massoulié
(2002) means making the approximation
$y_{t-\tau_{ij}}=y_{t}-\tau_{ij}\frac{{\rm d}y_{t}}{{\rm d}t}$. Under this
approximation, we have:

$\frac{{\rm d}y_{t}}{{\rm d}t}=-\sum_{(ij)\in E}K_{ij}\big{(}\nabla
f_{ij}(y_{t})-\tau_{ij}\nabla f_{ij}(\frac{{\rm d}y_{t}}{{\rm d}t})\big{)}\,.$

For any weights $\nu_{ij}$ and vector $z$, $\sum_{ij}\nu_{ij}\nabla
f_{ij}(z)=\Delta_{G}(\nu)z$. Thus the delay-linearized ODE reads

$(I-\Delta_{G}(\\{K_{ij}\tau_{ij}\\}))\frac{{\rm d}y_{t}}{{\rm
d}t}=-\Delta_{G}(\\{K_{ij}\\})y_{t}\,.$ (13)

This delay-linearized ODE (13) provides intuition on the behavior of
$\mathbb{E}\left[x_{t}\right]$. Indeed, (13) is stable provided that
$\rho(\Delta_{G}(\\{\tau_{ij}K_{ij}\\}))<1$, in which case it has a linear
rate of convergence of order
$\lambda_{2}(\Delta_{G}({{\left\\{K_{ij}\right\\}}})$.

Even though this stability condition and the rate of convergence are only
heuristics, since (13) is obtained through an approximation of the delayed ODE
verified by $\mathbb{E}\left[x_{t}\right]$ (12), this stability condition for
the delay-linearized system implies stability of the original delayed system
under assumptions on the matrices and delays involved (Massoulié, 2002), that
hold in our case, leading to the following

######  Proposition 1.

Assume that the spectral radius of the weighted Laplacian
$\Delta_{G}(\\{\tau_{ij}K_{ij}\\})$ verifies
$\rho(\Delta_{G}(\\{\tau_{ij}K_{ij}\\}))<1$. Then the delayed _ODE_ (12) is
stable.

Consequently, the stability conditions (necessary conditions on step sizes
$K_{ij}$ in Equation (10)) obtained in Theorem 1 are very natural. Indeed, a
simple way to enforce $\rho(\Delta_{G}(\\{\tau_{ij}K_{ij}\\})<1$ based on
local conditions consists in imposing $\sum_{j}\tau_{ij}K_{ij}<1$ for all $i$.
This is a weaker condition than the one stated in Theorem 1, but it only gives
stability of the means. Furthermore, the rate of convergence of delayed
randomized gossip in Theorem 1, that takes the form of the eigengap of a
weighted graph Laplacian, is also that of any solution of the delay-linearized
ODE (13).

###### Proof of Proposition 1.

For $A\in\mathbb{R}^{V\times E}$ as defined in Section 3.1 for non-null
weights $\mu_{ij}$, define the following delayed ODE:

$\frac{{\rm d}\lambda_{t}}{{\rm d}t}=-\sum_{(ij)\in
E}\frac{K_{ij}}{\mu_{ij}^{2}}e_{ij}^{\top}A^{\top}A\lambda_{t-\tau_{ij}}\,.$
(14)

For $(y_{t})$ solution of (12), if there exists $\lambda_{0}$ such that
$A\lambda_{0}=y_{0}$, then $y_{t}=A\lambda_{t}$ for all $t$, where
$\lambda_{t}$ is solution of (14) initialized at the value $\lambda_{0}$.
Then, since $AA^{\top}$ is the Laplacian of graph $G$ with weights
$\mu_{ij}^{2}>0$, $A$ is of rank $n-1$. For all $\lambda$, $A\lambda$ is in
the orthogonal of $\mathbb{R}\mathbf{1}$ ($\mathbf{1}\in\mathbb{R}^{V}$ is the
vector with all entries equal to $1$), so that ${\rm Im}(A)$ is exactly the
orthogonal of $\mathbb{R}\mathbf{1}$. Finally, since for $(y_{t})$ a solution
of (12), $y_{t}-(\mathbf{1}^{\top}y_{0})\mathbf{1}$ is also solution of (12)
and takes values in the orthogonal of $\mathbb{R}\mathbf{1}$, it is sufficient
to prove stability of (14).

To that end, we use Theorem 1 of Massoulié (2002). For $z\in\mathbb{R}^{E}$,
let $D(z)\in\mathbb{R}^{E\times E}$ be the diagonal matrix with diagonal equal
to $z$. Let $M=D(\frac{K}{\mu^{2}})A^{\top}A$. Then, the delayed ODE (14)
writes as:

$\frac{{\rm d}\lambda_{t}(ij)}{{\rm d}t}=-\sum_{(kl)\in
E}M_{(ij),(kl)}\lambda_{t-\tau_{ij}}(kl)\quad,\,(ij)\in E\,,$

and ODE that takes the same form as Equation (7) in Massoulié (2002), for
$D_{(ij)}^{\leftarrow}=\tau_{ij}$, $D_{(ij)}^{\rightarrow}=0$ and
$D_{(ij)}=\tau_{ij}$, $R=E$ and with our matrix $M$. In order to ensure that
$M$ is symmetric and positive semi-definite, we take $\mu_{ij}^{2}=K_{ij}$, to
have $M=A^{\top}A$. The assumptions of Theorem 1 of Massoulié (2002) are
verified, so that the delayed ODE (14) is table if $\rho(D(\tau)M)<1$. We then
write
$\rho(D(\tau)M)=\rho(D(\sqrt{\tau})A^{\top}AD(\sqrt{\tau})=\rho(AD(\sqrt{\tau})(AD(\sqrt{\tau}))^{\top})$,
and notice that $AD(\sqrt{\tau})(AD(\sqrt{\tau}))^{\top}$ is the Laplacian of
graph $G$ with weights $\mu_{ij}^{2}\tau_{ij}=K_{ij}\tau_{ij}$, concluding the
proof. ∎

###  3.5. Proof of Theorem 1

In the proof, we use the assumed bounds $\tau_{ij}$ on actual delays in our
algorithm to ensure that communications between $i$ and $j$ started at a time
$t-\tau_{ij}$ induce communication updates at time $t$. Our algorithms thus
behave exactly as if individual communication delays coincide with these upper
bounds $\tau_{ij}$, which allows us to analyze algorithms with constant,
albeit heterogeneous delays.

In contrast an analysis in discrete time would use a global iteration counter,
and discrete-time delays would not be constant,making the analysis either much
more involved or unable to capture the asynchronous speedup described above.

###### Proof.

Theorem 1 is obtained by applying a general result on delayed coordinate
descent in the continuized framework that we detail in Section 4.

Specifically, we consider the function:

$g(\lambda)=\frac{1}{2}{{\left\|A\lambda\right\|}}^{2}\,\quad\lambda\in\mathbb{R}^{E\times
d}$

for some $A\in\mathbb{R}^{V\times E}$ such that
$Ae_{ij}=\mu_{ij}(e_{i}-e_{j})$ for all $(ij)\in E$, where we let
$\mu_{ij}=-\mu_{ji}$ by convention. As in Section 3.4, there exists
$\lambda\in\mathbb{R}^{E\times d}$ such that $x_{0}-\bar{x}=A\lambda$. Let
$(\lambda_{t})_{t\geq 0}$ be defined with $\lambda_{0}=\lambda$, and the
delayed coordinate gradient steps at the clock tickings of the _P.p.p._ ’s:

$\lambda_{T_{k}}\leftarrow\lambda_{T_{k}-}-\frac{K_{i_{k}j_{k}}}{p_{i_{k}j_{k}}}\nabla_{i_{k}j_{k}}g(\lambda_{T_{k}-\tau_{i_{k}j_{k}}})\,.$

For all $t\geq 0$, we then have $x_{t}=\bar{x}+A\lambda_{t}$, where we recall
that the process $(x_{t})$ follows the delayed randomized gossip updates (9)
of Algorithm 1. Then, for all $t\geq 0$, we have
$g(\lambda_{t})=\frac{1}{2}{{\left\|A\lambda_{t}\right\|}}^{2}=\frac{1}{2}{{\left\|x_{t}-\bar{x}\right\|}}^{2}$.

The result of Theorem 1 follows from a control of
$\mathbb{E}\left[g(\lambda_{t})\right]$ that is a direct consequence of
Theorem 2 in next section with the specific choices $m=|E|$ and coordinate
blocks corresponding to edges. The assumptions of Theorem 2 are verified with
$L_{ij}=2\mu_{ij}^{2}$, $M_{(ij),(kl)}=\sqrt{L_{ij}L_{kl}}$, and strong
convexity parameter $\lambda_{2}(\Delta_{G}(\nu_{ij}=\mu_{ij}^{2}))$ for the
specific choice $\mu_{ij}^{2}=K_{ij}$, as is shown in Lemmas 2, 3, 4 in the
Appendix, giving us exactly Theorem 1. ∎

##  4\. Delayed coordinate gradient descent in the continuized framework

Let $G$ be a $\sigma$-strongly convex function on $\mathbb{R}^{D}$. For
$k=1,...,m$, let $E_{k}$ be a subspace of $\mathbb{R}^{d}$, and assume that:

$\mathbb{R}^{d}=\bigoplus_{k=1}^{n}E_{k}\,.$ (15)

For $x\in\mathbb{R}^{D}$, let $x_{k}$ denote its orthogonal projection on
$E_{k}$ and let $\nabla_{k}G:=(\nabla G)_{k}$, and assume that the subspaces
$E_{1},...,E_{m}$ are orthogonal. For $k,\ell\in[m]$, we say that $k$ and
$\ell$ are adjacent and we write $k\sim\ell$ if and only if
$\nabla_{k}\nabla_{\ell}G$ is not identically constant equal to $0$. This
induces a symmetric graph structure on the coordinates $k\in[m]$. In the
context of gossip network averaging, $m=|E|$ and each subspace $E_{k}$
corresponds to an edge $e_{k}=(i_{k}j_{k})$ of the graph; in that context, we
have $k\sim\ell$ if and only if edges $e_{k}$ and $e_{\ell}$ share a node.

In the network averaging problem previously described, the function $G$ used
is $g(\lambda)=\frac{1}{2}{{\left\|A\lambda\right\|}}$ for
$\lambda\in\mathbb{R}^{E\times d}$ the edge variables. Subspaces are $E_{ij}$
of dimension $d$ for $(ij)\in E$ (and $m=|E|$) corresponding to variables of
$\lambda$ associated to edge $(ij)$.

###  4.1. Algorithm and assumptions

####  4.1.1. Continuized delayed coordinate gradient descent algorithm

For $k\in[m]$, let $\mathcal{P}_{k}$ be a _P.p.p._ of intensity $p_{k}$
denoting the times at which an update can be performed on subspace $E_{k}$.
For $t\in\mathcal{P}_{k}$ let $\varepsilon_{k}(t)\in\\{0,1\\}$ be the
indicator of whether the update is performed or not. Let also $\eta_{k}$ be
some positive step size for $k\in[m]$. Consider then the following continuous-
time process $X(t)$, where $X_{k}(t)$ (the projection of $X(t)$ on $E_{k}$)
evolves according to:

${\rm
d}X_{k}(t)=-\varepsilon_{k}(t)\eta_{k}\nabla_{k}G((X(t-\tau_{k}))\mathcal{P}_{k}({\rm
d}t)\,,$ (16)

where $\mathcal{P}_{k}({\rm d}t)$ corresponds to a Dirac at the points of the
_P.p.p._ $\mathcal{P}_{k}$. In words, $(X(t))_{t\geq 0}$ is a jump process
that takes coordinate gradient descent steps along subspaces
$(E_{k})_{k\in[m]}$ at the times of independent Poisson point processes
$(\mathcal{P}_{k})_{k\in[m]}$. We introduced variables
$(\varepsilon_{k}(t))_{k\in[m],t\in\mathcal{P}_{k}}$ with values in
${{\left\\{0,1\right\\}}}$ to represent capacity constraints:
$\varepsilon_{k}(t)=0$ if the update at time $t\in\mathcal{P}_{k}$ cannot be
performed due to some constraint saturation; these variables
$\varepsilon_{k}(t)$ will be essential in our treatment of communication and
computation capacity constraints in Section 6.

####  4.1.2. Regularity assumptions

$G$ is $\sigma$-strongly convex, and $L_{k}$-smooth on $E_{k}$ for $k\in[m]$.
Furthermore, there exist non-negative real numbers $M_{k,\ell}$ and
$M_{\ell,k}$ for $k\sim\ell$ such that for all $k=1,...,m$ and
$x,y\in\mathbb{R}^{D}$, we have:

${{\left\|\nabla_{k}G(x)-\nabla_{k}G(y)\right\|}}\leq\sum_{\ell\sim
k}M_{k,\ell}{{\left\|x_{\ell}-y_{\ell}\right\|}}\,.$ (17)

When $G$ is $L_{k}$ smooth on $E_{k}$ as we assume, the above condition is
verified by the choice $M_{i,j}=L_{j}$, $i\sim j$. If $\nabla_{k}G$ is
$M_{k}$-Lipschitz, Condition (17) is verified by the choice
$M_{k,\ell}=M_{k}$. Assumption (17) however allows for more freedom, and is
particularly well suited for our analysis. In particular for decentralized
optimization, it will be convenient to take $M_{k\ell}=\sqrt{L_{k}L_{\ell}}$.

####  4.1.3. Assumptions on variables
$\varepsilon_{k}(t),\,t\in\mathcal{P}_{k}$

For $t\in\mathcal{P}_{k}$, random variable $\varepsilon_{k}(t)$ is
$\sigma\big{(}\mathcal{P}_{\ell}\cap[t-\tau_{k},t),\ell\in[m])$-measurable,
and there exists a constant $\varepsilon_{k}>0$ such that:

$\mathbb{E}\left[\varepsilon_{k}(t)\right]\geq\varepsilon_{k}\,,$

Furthermore, we assume that $\varepsilon_{k}(t)$ is negatively correlated with
each quantity $N_{\ell}(t-\tau_{k},t)=|\mathcal{P}_{\ell}\cap[t-\tau_{k},t]|$,
_i.e._ that for all $k,\ell\in[m]$,

$\mathbb{E}\left[\varepsilon_{k}(t)N_{\ell}(t-\tau_{k},t)\right]\leq\mathbb{E}\left[\varepsilon_{k}(t)\right]\mathbb{E}\left[N_{\ell}(t-\tau_{k},t)\right]\,.$
(18)

In our subsequent treatment of communication and capacity contraints, we shall
see that the above assumptions are verified for $\epsilon_{k}(t)$ the
indicator that $t$ is a point a _truncated P.p.p._ $\tilde{\mathcal{P}}_{k}$
defined as follows:

######  Definition 2 (Truncated _P.p.p._).

Let $(\mathcal{P}_{k})_{1\leq k\leq m}$ be _P.p.p._ of respective intensities
$(p_{k})_{1\leq k\leq m}$, $(\tau_{k})_{1\leq k\leq m}$ non-negative delays.
Let $N_{k}$ be the Poisson point measures associated to $\mathcal{P}_{k}$,
$k\in[m]$. For $(\mathcal{C}_{r})_{1\leq r\leq M}$ subsets of $[m]$, we define
the truncated Poisson point measures $(\tilde{N})_{1\leq k\leq m}$ of
intensities $(p_{k})_{1\leq k\leq m}$ and parameters
$(\tau_{k})_{k},(q_{k,r})_{k\in[m],r\in[M]}$ as:

${\rm d}\tilde{N}_{k}(t)=1_{{\left\\{\bigcap_{1\leq k\leq
M}{{\left\\{\sum_{\ell\in\mathcal{C}_{r}}N_{\ell}([t-\tau_{k},t))\leq
q_{k,r}\right\\}}}\right\\}}}{\rm d}N_{k}(t)\,,$ (19)

and we let $\tilde{\mathcal{P}}_{k}$ be the point process associated to this
point measure.

###  4.2. Convergence guarantees and analysis

The main result of this Section is the following

######  Theorem 2 (Delayed Coordinate Gradient Descent).

Under the stated assumptions on regularity of $G$ and on variables
$\epsilon_{k}(t)$, assume further that the step sizes $\eta_{k}$ are given by
$\eta_{k}=\frac{K_{k}}{p_{k}L_{k}}$ where for all $k\in[m]$,

$K_{k}\leq\frac{p_{k}}{1+\sum_{\ell\sim
k}p_{\ell}\left(\frac{\tau_{k}M_{k,\ell}+e\tau_{\ell}M_{\ell,k}}{\sqrt{L_{k}L_{\ell}}}\right)}\,,$
(20)

and let $\gamma\in\mathbb{R}_{+}$ be such that:

$\gamma<\min\left(\sigma\min_{k}\frac{\varepsilon_{k}K_{k}}{L_{k}},\frac{1}{\tau_{\max}}\right)\,,$
(21)

where $\tau_{\max}:=\max_{k\in[m]}\tau_{k}$. Then for any $T>0$ the solution
$X(t)$ to Equation (16) verifies

$\frac{\int_{0}^{T}e^{\gamma t}\mathbb{E}\left[G(X(t))-G(x^{\star})\right]{\rm
d}t}{\int_{0}^{T}e^{\gamma t}\big{(}G(X(0))-G(x^{\star})\big{)}{\rm d}t}\leq
e^{-\frac{\gamma
T}{2}}\frac{1+\frac{\tau_{\max}}{T}}{1-\gamma\tau_{\max}}\,\cdot\vspace{5pt}$
(22)

###### Proof.

We proceed in three steps. The first step consists in upper bounding, for
$t\geq 0$, the quantity $\frac{{\rm d}\mathbb{E}\left[G(X(t))\right]}{{\rm
d}t}$. We then introduce in Step 2 a Lyapunov function inspired by the
Lyapunov-Krasovskii functional (Gu and Liu, 2009)), and by using the result
proved in the first step, we show that it verifies a delayed ordinary
differential inequality. The last step then consists in deriving the desired
result from this delayed differential inequality.

#### Step 1

To bound $\frac{{\rm d}\mathbb{E}\left[G(X(t))\right]}{{\rm d}t}$, we study
infinitesimal increments between $t$ and $t+{\rm d}t$ for ${\rm d}t\to 0$.
This approach is justified by results on _stochastic ordinary differential
equation with Poisson jumps_ , see Davis (1984). For $t\geq 0$, let
$\mathcal{F}_{t}$ be the filtration induced by
$\mathcal{P}_{k}\cap[0,t),\,k\in[m]$ _i.e._ , the filtration up to time $t$.
By convention, for non-positive $t$, we write $X(t)=X(0)$. The following
inequalities are written up to $o({\rm d}t)$ terms, that we omit to lighten
notations. Finally, we write

$g_{k,t}=\nabla_{k}G(X(t))\,,\quad k\in[m],t\geq 0\,.$

We have, using local smoothness properties of $G$ and the fact that for a
_P.p.p._ $\mathcal{P}$ of intensity $p$, $\mathbb{P}(\mathcal{P}\cap[t,t+{\rm
d}t]=\emptyset)=1-p{\rm d}t+o({\rm d}t)$ and
$\mathbb{P}(\\#\mathcal{P}\cap[t,t+{\rm d}t]=1)=p{\rm d}t+o({\rm d}t)$:

$\begin{split}&\frac{\mathbb{E}\left[G(X(t+{\rm
d}t))-G(X(t))|\mathcal{F}_{t}\right]}{{\rm d}t}\\\
&=\sum_{k=1}^{m}p_{k}\left(G\left(X(t)-\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}g_{k,t-\tau_{k}}\right)-G(X(t))\right)\\\
&\leq\sum_{k=1}^{m}p_{k}\left(-\frac{K_{k}}{p_{k}L_{k}}\langle\varepsilon_{k}(t)g_{k,t-\tau_{k}},g_{k,t}\rangle\right.\\\
&+\left.\frac{L_{k}}{2}{{\left\|\varepsilon_{k}(t)\frac{K_{k}}{p_{k}L_{k}}\nabla_{k}g_{k,t-\tau_{k}}\right\|}}^{2}\right)\,.\end{split}$

First, we rewrite $-\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}\langle
g_{k,t-\tau_{k}},g_{k,t}\rangle$ as

$-\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}{{\left\|g_{k,t-\tau_{k}}\right\|}}^{2}-\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}\langle
g_{k,t-\tau_{k}},g_{k,t}-g_{k,t-\tau_{k}}\rangle,$

and bound the second term there by

$\begin{split}&-\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}\langle
g_{k,t-\tau_{k}},g_{k,t}-g_{k,t-\tau_{k}}\rangle\\\
&\leq\frac{\varepsilon_{k}(t)K_{k}}{p_{k}L_{k}}{{\left\|g_{k,t-\tau_{k}}\right\|}}\;{{\left\|g_{k,t}-g_{k,t-\tau_{k}}\right\|}}\\\
&\leq\frac{K_{k}}{p_{k}L_{k}}{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}\sum_{\ell\sim
k}M_{k,\ell}{{\left\|X_{\ell}(t)-X_{\ell}(t-\tau_{k})\right\|}}\,,\end{split}$

where we used the Cauchy-Schwarz inequality and then local Lipschitz property
(17) of $\nabla_{k}G$. Writing

$\displaystyle{{\left\|X_{\ell}(t)-X_{\ell}(t-\tau_{k})\right\|}}$
$\displaystyle={{\left\|\int_{(t-\tau_{k})^{+}}^{t}\frac{\varepsilon_{\ell}(s)K_{\ell}}{p_{\ell}L_{\ell}}g_{\ell,s-\tau_{\ell}}N_{\ell}({\rm
d}s)\right\|}}\,,$

where $N_{\ell}$ is the Poisson point measure associated to
$\mathcal{P}_{\ell}$, we have (where we use a triangle inequality for
integrals):

$\displaystyle\frac{K_{k}M_{k,\ell}}{p_{k}L_{k}}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}{{\left\|X_{\ell}(t)-X_{\ell}(t-\tau_{k})\right\|}}\right]$
$\displaystyle\leq\mathbb{E}\left[\int_{(t-\tau_{k})^{+}}^{t}M_{k,\ell}\frac{\varepsilon_{k}(t)K_{k}\varepsilon_{\ell}(s)K_{\ell}}{L_{k}p_{k}p_{\ell}L_{\ell}}{{\left\|g_{k,t-\tau_{k}}\right\|}}{{\left\|g_{\ell,s-\tau_{\ell}}\right\|}}N_{\ell}({\rm
d}s)\right]$
$\displaystyle\leq\mathbb{E}\left[\int_{(t-\tau_{k})^{+}}^{t}\frac{1}{2}\left(\frac{K_{k}^{2}M_{k,\ell}}{p_{k}^{2}L_{k}\sqrt{L_{k}L_{\ell}}}{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right.\right.$
$\displaystyle\quad\quad\left.\left.+\frac{K_{\ell}^{2}M_{k,\ell}}{p_{\ell}^{2}L_{\ell}\sqrt{L_{k}L_{\ell}}}{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}\right)N_{\ell}({\rm
d}s)\right]\,.$

For the first term, since both $\varepsilon_{k}(t)$ and $N_{\ell}({\rm d}s)$
for $s$ in the integral are independent from $X(t-\tau_{k})$ (and thus from
$g_{k,t-\tau_{k}}$), and where we write $N_{\ell}(u,v)$ the number of clock
tickings of $\mathcal{P}_{\ell}$ in the interval $[u,v)$, we obtain:

$\displaystyle\mathbb{E}\left[\int_{(t-\tau_{k})^{+}}^{t}\frac{1}{2}\frac{K_{k}^{2}M_{k,\ell}}{p_{k}^{2}L_{k}\sqrt{L_{k}L_{\ell}}}{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]$
$\displaystyle=\frac{\mathbb{E}\left[N_{\ell}(t-\tau_{k},t)\varepsilon_{k}(t)\right]}{2}\frac{K_{k}^{2}M_{k,\ell}}{p_{k}^{2}L_{k}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|g_{k,t-\tau_{k}}\right\|}}^{2}\right]\,.$

Furthermore, using our negative correlation assumption,
$\mathbb{E}\left[N_{\ell}(t-\tau_{k},t)\varepsilon_{k}(t)\right]\leq\mathbb{E}\left[N_{\ell}(t-\tau_{k},t)\right]\mathbb{E}\left[\varepsilon_{k}(t)\right]=p_{\ell}\tau_{k}\mathbb{E}\left[\varepsilon_{k}(t)\right]$,
and since $\varepsilon_{k}(t)$ and $g_{k,t-\tau_{k}}$ are independent,
$\mathbb{E}\left[\varepsilon_{k}(t)\right]\mathbb{E}\left[{{\left\|g_{k,t-\tau_{k}}\right\|}}^{2}\right]=\mathbb{E}\left[\varepsilon_{k}(t){{\left\|g_{k,t-\tau_{k}}\right\|}}^{2}\right]$.

For the second term, since the process
$(\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}})_{s}$ is predictable (in the
sense that it is independent from $N_{u}({\rm d}s)$ for all $u$), we have

$\displaystyle\mathbb{E}\left[\int_{(t-\tau_{k})^{+}}^{t}\frac{K_{\ell}^{2}M_{k,\ell}}{2p_{\ell}^{2}L_{\ell}\sqrt{L_{k}L_{\ell}}}{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}N_{\ell}({\rm
d}s)\right]$
$\displaystyle=\int_{(t-\tau_{k})^{+}}^{t}\frac{K_{\ell}^{2}M_{k,\ell}}{2p_{\ell}^{2}L_{\ell}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}\right]\mathbb{E}\left[N_{\ell}({\rm
d}s)\right]$
$\displaystyle=\int_{(t-\tau_{k})^{+}}^{t}\frac{K_{\ell}^{2}M_{k,\ell}}{2p_{\ell}^{2}L_{\ell}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}\right]p_{\ell}{\rm
d}s\,.$

Hence,

$\displaystyle\frac{K_{k}M_{k,\ell}}{p_{k}L_{k}}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}{{\left\|X_{\ell}(t)-X_{\ell}(t-\tau_{k})\right\|}}\right]$
$\displaystyle\leq\frac{p_{\ell}\tau_{k}K_{k}^{2}M_{k,\ell}}{2p_{k}^{2}L_{k}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]$
$\displaystyle\quad+\int_{(t-\tau_{k})^{+}}^{t}\frac{K_{\ell}^{2}M_{k,\ell}}{2p_{\ell}^{2}L_{\ell}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}\right]p_{\ell}{\rm
d}s\,.$

Combining all our elements and taking ${\rm d}t\to 0$, we hence have:

$\begin{split}&\frac{{\rm d}\mathbb{E}\left[G(X(t))\right]}{{\rm
d}t}\leq-\sum_{k=1}^{m}\frac{K_{k}}{L_{k}}\big{(}1-\frac{K_{k}}{2p_{k}}\big{)}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]\\\
&\quad+\sum_{k=1}^{m}\sum_{\ell\sim
k}\frac{p_{\ell}\tau_{k}K_{k}^{2}M_{k,\ell}}{2p_{k}L_{k}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]\\\
&\quad+\sum_{k=1}^{m}\sum_{\ell\sim
k}\int_{(t-\tau_{k})^{+}}^{t}\frac{p_{k}K_{\ell}^{2}M_{k,\ell}}{2p_{\ell}L_{\ell}\sqrt{L_{k}L_{\ell}}}\mathbb{E}\left[{{\left\|\varepsilon_{\ell}(s)g_{\ell,s-\tau_{\ell}}\right\|}}^{2}\right]{\rm
d}s\,.\end{split}$ (23)

#### Step 2

Now, introduce the following Lyapunov function:

$\mathcal{L}^{\gamma}_{T}=\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[G(X(t))-G(x^{\star})\right]{\rm d}t\,,$

that we wish to upper-bound by some constant, where $\gamma$ is as in (21). We
have:

$\frac{{\rm d}\mathcal{L}^{\gamma}_{T}}{{\rm
d}T}=G(X(0))-G(x^{\star})+\gamma\mathcal{L}^{\gamma}_{T}+\int_{0}^{T}e^{\gamma
t}\frac{{\rm d}\mathbb{E}\left[G(X(t))\right]}{{\rm d}t}{\rm d}t\,.$

Integrating the bound (23) on $\frac{{\rm
d}\mathbb{E}\left[G(X(t))\right]}{{\rm d}t}$, we obtain, using
$\int_{0}^{T}\int_{(t-\tau)^{+}}^{t}h(u){\rm d}u{\rm
d}t\leq\tau\int_{0}^{T}h(t){\rm d}t$ for non-negative $h$:

$\begin{split}\frac{{\rm d}\mathcal{L}^{\gamma}_{T}}{{\rm d}T}&\leq
G(X(0))-G(x^{\star})+\gamma\mathcal{L}^{\gamma}_{T}\\\
&-\sum_{k=1}^{m}\frac{K_{k}}{L_{k}}\big{(}1-\frac{K_{k}}{2p_{k}}\big{)}\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]{\rm
d}t\\\ &+\sum_{k=1}^{m}A_{k}\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t)g_{k,t-\tau_{k}}\right\|}}^{2}\right]{\rm
d}t\,,\end{split}$

where

$A_{k}=\frac{K_{k}^{2}}{2p_{k}L_{k}}\sum_{\ell\sim
k}\frac{p_{\ell}\tau_{k}M_{k,\ell}}{\sqrt{L_{k}L_{\ell}}}+e^{\gamma\tau_{\ell}}\frac{p_{\ell}\tau_{\ell}M_{\ell,k}}{\sqrt{L_{k}L_{\ell}}}\,.$

Remark now that we have

$\frac{K_{k}^{2}}{2p_{k}L_{k}}+A_{k}\leq\frac{K_{k}}{2L_{k}},\quad k\in[m].$
(24)

Indeed, (24) is equivalent to

$K_{k}\leq\frac{p_{k}}{1+\sum_{\ell\sim
k}\Big{(}\frac{p_{\ell}\tau_{k}M_{k,\ell}}{\sqrt{L_{k}L_{\ell}}}+e^{\gamma\tau_{\ell}}\frac{p_{\ell}\tau_{\ell}M_{\ell,k}}{\sqrt{L_{k}L_{\ell}}}\Big{)}}\,,$

which follows from the assumed bounds (20) on $K_{k}$ and the fact that
$\gamma\leq 1/\tau_{\max}$, assumed in (21). we then have, using (24) and the
fact that, by strong convexity,
$G(X(t))-G(x^{\star})\leq\frac{1}{2\sigma}{{\left\|\nabla
G(X(t))\right\|}}^{2}=\frac{1}{2\sigma}\sum_{k=1}^{m}{{\left\|\nabla
g_{k,t}\right\|}}^{2}$:

$\begin{split}\frac{{\rm d}\mathcal{L}^{\gamma}_{T}}{{\rm d}T}&\leq
G(X(0))-G(x^{\star})+\gamma\mathcal{L}^{\gamma}_{T}\\\
&-\sum_{k=1}^{m}\frac{K_{k}}{2L_{k}}\int_{0}^{T-\tau_{k}}e^{\gamma(t+\tau_{k})}\mathbb{E}\left[{{\left\|\varepsilon_{k}(t+\tau_{k})g_{k,t}\right\|}}^{2}\right]{\rm
d}t\\\ &\leq G(X(0))-G(x^{\star})+\gamma\mathcal{L}^{\gamma}_{T}\\\
&-\min_{k\in[m]}\big{(}\frac{K_{k}\varepsilon_{k}e^{\gamma\tau_{k}}}{2L_{k}}\big{)}\int_{0}^{T-\tau_{\max}}e^{\gamma
t}\mathbb{E}\left[\sum_{k=1}^{m}{{\left\|g_{k,t}\right\|}}^{2}\right]{\rm
d}t\\\ &\leq
G(X(0))-G(x^{\star})+\gamma\big{(}\mathcal{L}^{\gamma}_{T}-\mathcal{L}^{\gamma}_{T-\tau_{\max}}\big{)}\,,\end{split}$

where we used the assumption (21) that
$\gamma\leq\sigma\min_{k\in[m]}\big{(}\frac{K_{k}\varepsilon_{k}}{L_{k}}\big{)}$.

#### Step 3

The proof is then concluded by using the following lemma, to control solutions
of this delayed ordinary differential inequality.

######  Lemma 1.

Let $h:\mathbb{R}\to\mathbb{R}^{+}$ a differentiable function such that:

$\displaystyle\forall t\leq 0\,,\,h(t)=0\,,$ $\displaystyle\forall t\geq
0\,,\,h^{\prime}(t)\leq a+b(h(t)-h(t-\tau))\,,$

for some positive constants $a,b,\tau$ verifying $\tau b<1$. Then:

$\forall t\in\mathbb{R}\,,\quad h(t)\leq\frac{a(t+\tau)}{1-\tau b}\,.$

###### Proof.

Let $\delta(t)=h(t)-h(t-\tau)$. For any $t\geq 0$, we have:

$\displaystyle\delta(t)$ $\displaystyle=\int_{t-\tau}^{t}h^{\prime}(s){\rm
d}s$ $\displaystyle\leq\int_{t-\tau}^{t}(a+b\delta(s)){\rm d}s$
$\displaystyle\leq\tau(a+b\sup_{s\leq t}\delta(s)).$

Let $c=\frac{\tau a}{1-\tau b}$ (solution of $x=\tau(a+bx)$) and
$t_{0}=\inf\\{t>0|\delta(t)\geq c\\}\in\mathbb{R}\cup\\{\infty\\}$. Assume
that $t_{0}$ is finite. Then, by continuity, $\delta(t_{0})=c$ and:

$\displaystyle c\leq\tau(a+b\sup_{s\leq t_{0}}\delta(s))<\tau(a+bc)<c,$

as for all $s<t_{0}$, $\delta(s)<c$. This is absurd, and thus $t_{0}$ is not
finite: $\forall t>0,\delta(t)<c$, giving us $h(t)\leq c(t+\tau)/\tau$ for all
$t\geq 0$. ∎

To conclude the proof of Theorem (2), we apply Lemma 1 to
$h(T)=\mathcal{L}_{T}^{\gamma}$ with $a=G(X(0))-G(x^{\star})$, $b=\gamma$ and
$\tau=\tau_{\max}$ to obtain that for all $T>0$,

$\mathcal{L}_{T}^{\gamma}\leq\big{(}G(X(0))-G(x^{\star})\big{)}\frac{T+\tau_{\max}}{1-\tau_{\max}\gamma}\,\cdot$

The result of Theorem 2 follows by dividing this inequality by
$\int_{0}^{T}e^{\gamma t}{\rm d}t=\frac{e^{\gamma T}-1}{\gamma}$:

$\displaystyle\frac{\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[G(X(t))-G(x^{\star})\right]{\rm d}t}{\int_{0}^{T}e^{\gamma
t}\big{(}G(X(0))-G(x^{\star})\big{)}{\rm d}t}$
$\displaystyle\leq\frac{\gamma}{e^{\gamma
T}-1}\frac{T+\tau_{\max}}{1-\tau_{\max}\gamma}$ $\displaystyle=\frac{\gamma
T}{e^{\gamma T}-1}\frac{1+\tau_{\max}/T}{1-\tau_{\max}\gamma}$
$\displaystyle\leq e^{-\gamma
T/2}\frac{1+\tau_{\max}/T}{1-\tau_{\max}\gamma}\,,$

where we used that for $x\geq 0$, $\frac{e^{x}-1}{x}\geq e^{x/2}$. ∎

##  5\. Extension to decentralized optimization

Using Theorem 2, we are now armed to generalize the delayed randomized gossip
algorithm and analysis to more general settings. In this section we extend our
results to decentralized optimization, going beyond the quadratic objective
functions considered network averaging.

###  5.1. Delayed Decentralized Optimization

Consider the decentralized optimization problem (1). We make the following
assumptions on the individual objective functions $f_{i}$ therein :

Each $f_{i}$, $i\in V$, is $\sigma$-strongly convex and $L$-smooth, (25)

see Bubeck (2015) for definitions. Let $f(z):=\sum_{i\in[n]}f_{i}(z)$ for
$z\in\mathbb{R}^{d}$ and $F(x)=\sum_{i\in[n]}f_{i}(x_{i})$ for
$x=(x_{1},\cdots,x_{n})\in\mathbb{R}^{n\times d}$ where
$x_{i}\in\mathbb{R}^{d}$ corresponds to node $i\in[n]$.

######  Definition 3 (Fenchel Conjugate).

For any function $g:\mathbb{R}^{p}\to\mathbb{R}$, its _Fenchel conjugate_ is
denoted by $g^{*}$ and defined on $\mathbb{R}^{p}$ by
$g^{*}(y)=\sup_{x\in\mathbb{R}^{p}}\langle
x,y\rangle-g(x)\in\mathbb{R}\cup\\{+\infty\\}$.

Our algorithm for delayed decentralized optimization is built on delayed
randomized gossip for network averaging, augmented with local computations.
Each node $i\in V$ keeps two local variables: the communication variable
$x_{i}(t)$, used to run delayed randomized gossip, and a computation variable
$y_{i}(t)$, used to make local computation updates in the following way.

Local computations. Each node $i$ generates a _Poisson point process_
$\mathcal{P}_{i}^{{\rm comp}}={{\left\\{T_{1}^{{\rm comp}}(i)<T_{2}^{{\rm
comp}}(i),\ldots\right\\}}}$ of intensity $p_{i}^{{\rm comp}}$. At the clock
tickings $T_{k}^{{\rm comp}}(i)$, a local computation update is made
corresponding to a computation started at a time $T_{k}^{{\rm
comp}}(i)-\tau_{i}^{{\rm comp}}$, where $\tau_{i}^{{\rm comp}}$ is the upper
bound on the time to perform an elementary computation at node $i$, introduced
in Assumption 1. Thus by assumption the computation started at time
$T_{k}^{{\rm comp}}(i)-\tau_{i}^{{\rm comp}}$ is completed by time
$T_{k}^{{\rm comp}}(i)$ so that the update can be performed at that time. The
precise form of this update is given by Equation (29).

Communications. In parallel of these local computations, a _Delayed Randomized
Gossip_ is run on the graph. Dedicated _P.p.p._ $(\mathcal{P}_{ij})_{(ij)\in
E}$ with respective intensities $(p_{ij})_{(ij)\in E}$ are associated to
communication updates of all network edges, and used to perform updates as
prescribed by Equation (9) in _Delayed Randomized Gossip_.

The resulting Delayed Decentralized Optimization algorithm, or _DDO_ for
short, is described in Algorithm 3 and is a combination of Algorithm 1 for
communication updates along edges $(ij)\in E$ with Algorithm 2 for local
computation updates at nodes $i\in V$.

###  5.2. Convergence guarantees

The process $(x(t),y(t))\in\mathbb{R}^{2n\times d}$ defined by algorithm _DDO_
, Algorithm 3, satisfies the following convergence guarantees that generalize
Theorem 1 to decentralized optimization beyond the case of quadratic
functions.

######  Theorem 3 (Delayed Decentralized Optimization).

Under the regularity assumptions (25), assume further that for all $1\leq i\in
V$ and $(ij)\in E$, we have:

$\displaystyle
K_{ij}\leq\frac{p_{ij}}{1+\sum_{(kl)\sim(ij)}p_{kl}\big{(}\tau_{ij}+e\tau_{kl}\big{)}}\,$
(26) $\displaystyle K_{i}^{{\rm comp}}\leq\frac{p_{i}^{{\rm
comp}}}{1+\sum_{j\sim i}p_{ij}\big{(}\tau_{i}^{{\rm
comp}}+e\tau_{ij}\big{)}}\,.$

Let $\tau_{\max}:=\max\left(\max_{(ij)\in E}\tau_{ij},\max_{i\in
V}\tau_{i}^{{\rm comp}}\right).$ Then for $\gamma>0$ such that

$\gamma\leq\min\left(\frac{\sigma}{4L}\lambda_{2}\big{(}\Delta_{G}(K)\big{)}\,,\,\frac{1}{\tau_{\max}}\right)\,,$
(27)

the process $(x(t),y(t))$ generated by _DDO_ satisfy

$\frac{\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[{{\left\|\frac{\sigma}{2}x(t)-\bar{x}^{\star}\right\|}}^{2}\right]{\rm
d}t}{\int_{0}^{T}e^{\gamma
t}{{\left\|\frac{\sigma}{2}x(0)-\bar{x}^{\star}\right\|}}^{2}{\rm d}t}\leq
e^{-\frac{\gamma
T}{2}}\frac{L}{\sigma}\frac{1+\frac{\tau_{\max}}{T}}{1-\gamma\tau_{\max}}\,,$
(28)

where
$\bar{x}^{\star}=(x^{\star},\ldots,x^{\star})^{\top}\in\mathbb{R}^{n\times d}$
for $x^{\star}$ minimizer of $f=\sum_{i}f_{i}$.

DDO is based on a dual formulation and uses an augmented graph representation
introduced in Hendrikx et al. (2020) to decouple computations from
communications, as detailed in the proof. The dual gradient computations in
Algorithm 2 can be expensive in general; they could be avoided by using a
primal-dual approach for the computation updates (Kovalev et al., 2021).

The convergence guarantees we obtain resemble classical ones: Interpreting
$\gamma$ as the reciprocal of the time scale for convergence, we recognize in
its upper bound (27) an “optimization factor” $\kappa_{\rm
comp}^{-1}:=\sigma/L$, and a “communication factor” $\kappa_{\rm
comm}^{-1}=\lambda_{2}\big{(}\Delta_{G}(K)\big{)}$. Our method is non-
accelerated, so the computation factor $\kappa_{\rm comp}$, the condition
number of the optimization problem, is expected. The communication factor
captures the delay heterogeneity in the graph as in _Delayed Randomized
Gossip_ , leading to the _asynchronous speedup_ discussed in Section 3 after
Theorem 1.

Previous approaches have considered accelerating decentralized optimization by
obtaining $\sqrt{\kappa_{\rm comp}}$ instead of $\kappa_{\rm comp}$ and/or
$\sqrt{\kappa^{\prime}_{\rm comm}}$ instead of $\kappa^{\prime}_{\rm comm}$
for $\kappa^{\prime}_{\rm comm}$ a communication factor in the rate of
convergence (Scaman et al., 2017; Kovalev et al., 2020; Hendrikx et al.,
2019a). Our result yields a speedup of a different nature: we obtain a
communication factor $\kappa_{\rm comm}$ that can be arbitrarily larger than
previously considered $\kappa^{\prime}_{\rm comm}$ for networks with huge
delay heterogeneity.

Algorithm 2 Local computations, node $i$

1: Step size $K_{i}^{\rm comp}>0$

2: Initialization $x_{0}(i)=y_{0}(i)=0$

3: Initialization $T_{1}^{\rm comp}(i)\sim{\rm Exp}(p_{i}^{\rm comp})$

4: for $\ell=1,2,\ldots$ do

5: $T_{\ell+1}(ij)=T_{\ell}(ij)+{\rm Exp}(p_{ij})$.

6: end for

7: for $\ell=1,2,\ldots$ do

8: At time $T_{\ell}^{\rm comp}(i)-\tau_{i}^{\rm comp}$, node $i$ computes
$g_{i}=\nabla\phi_{i}^{*}(y_{i}(T_{\ell}^{\rm comp}(i)-\tau_{i}^{\rm comp}))$
(takes a time less than $\tau_{i}^{\rm comp}$) and keeps
$\hat{x}_{i}=x_{i}(T_{\ell}^{\rm comp}(i)-\tau_{i}^{\rm comp})$ in memory,
where $\phi_{i}=f_{i}-\frac{\sigma}{4}{{\left\|.\right\|}}^{2}$.

9: At time $T_{\ell}^{\rm comp}(i)$,  $\displaystyle y_{i}(T_{\ell}^{\rm
comp}(i))\xleftarrow{t}y_{i}(T_{\ell}^{\rm comp}(i)-)-\frac{\sigma K_{i}^{{\rm
comp}}}{p_{i}^{{\rm comp}}}\big{(}g_{i}-\hat{x}_{i}\big{)}\,,$ (29)
$\displaystyle x_{i}(T_{\ell}^{\rm comp}(i))\xleftarrow{t}x_{i}(T_{\ell}^{\rm
comp}(i)-)-\frac{K_{i}^{{\rm comp}}}{2p_{i}^{{\rm
comp}}}\big{(}\hat{x}_{i}-g_{i}\big{)}\,.$

10: end for

Algorithm 3 _DDO_

1: Node initializations $x_{0}(i)=y_{0}(i)=0$, $i=1,\ldots,n$

2: for $i\in V$ and $(ij)\in E$, asynchronously, in parallel do

3: Communication updates along edge $(ij)$ according to Algorithm 1

4: Local computation updates at node $i$ according to Algorithm 2

5: end for

6: Output: $\frac{\sigma}{2}x_{i}(t)$ at time $t$ and node $i$.

###  5.3. Proof of Theorem 3

###### Proof.

Following the augmented graph approach of Hendrikx et al. (2020), for each
“physical” node $i\in V$, we associate a “virtual” node $i^{\rm comp}$,
corresponding to the computational unit of node $i$. We then consider the
augmented graph $G^{+}=(V^{+},E^{+})$, where $V^{+}=V\cup V^{{\rm comp}}$ (for
$V^{\rm comp}={{\left\\{i^{\rm comp},i\in V\right\\}}}$) and $E^{+}=E\cup
E^{\rm comp}$ (for $E^{\rm comp}={{\left\\{(ii^{\rm comp}),i\in
V\right\\}}}$).

For $i\in V$, function $f_{i}$ is then split (using $\sigma$-strong convexity)
into a sum of two $\sigma/2$-strongly convex functions:
$f_{i}=\phi_{i}+\phi_{i^{{\rm comp}}}$ where $\phi_{i^{{\rm
comp}}}(x_{i})=f_{i}(x_{i})-\frac{\sigma}{4}{{\left\|x_{i}\right\|}}^{2}$ and
$\phi_{i}(x_{i})=\phi_{{\rm
comm}}(x_{i})=\frac{\sigma}{4}{{\left\|x_{i}\right\|}}^{2}$.

The optimization objective (1)

$\min_{x_{1}=\ldots=x_{n}}\frac{1}{n}\sum_{i=1}^{n}f_{i}(x_{i})\,,\quad
x=(x_{1},\ldots,x_{n})\in\mathbb{R}^{V\times d}\,$

can then be rewritten as

$\min_{x\in\mathbb{R}^{V^{+}}}{{\left\\{F(x)=\sum_{i\in
V}\phi_{i}(x_{i})+\sum_{i^{\rm comp}\in V^{\rm comp}}\phi_{i^{\rm
comp}}(x_{i^{\rm comp}})\right\\}}}\,,$

under the constraint $x_{i}=x_{j}$ for $(ij)\in E^{+}$. This constraint can
then be rewritten as $A^{\top}x=0$ for $A\in\mathbb{R}^{E^{+}\times V^{+}}$
such that for all $(ij)\in E^{+}$, $Ae_{ij}=\mu_{ij}(e_{i}-e_{j})$, as was
done for network averaging, considering the augmented graph instead of the
original graph. Using Lagrangian duality, denoting
$F_{A}^{*}(\lambda):=F^{*}(A\lambda)$ for $\lambda\in\mathbb{R}^{E^{+}\times
d}$ where $F^{*}$ is the Fenchel conjugate of $F$, we have:

$\min_{x\in\mathbb{R}^{V^{+}\times d},x_{i}=x_{j},(ij)\in
E^{+}}F(x)=\max_{\lambda\in\mathbb{R}^{E\times d}}-F_{A}^{*}(\lambda).$

Thus $F_{A}^{*}(\lambda)$ is to be minimized over the dual variable
$\lambda\in\mathbb{R}^{E^{+}\times d}$. The rest of the proof is divided in
two steps: in the first, we derive the updates of the _DDO_ algorithm from
coordinate gradient descent steps on dual variables, and in the second step we
apply Theorem 2 to prove rates of convergence for these coordinate gradient
descent steps on function $F_{A}^{*}$.

The partial derivative of $F^{*}_{A}$ with respect to coordinate $(ij)\in
E^{+}$ of $\lambda\in\mathbb{R}^{E^{+}\times d}$ reads:

$\displaystyle\nabla_{ij}F_{A}^{*}(\lambda)=\mu_{ij}(\nabla\phi_{i}^{*}((A\lambda)_{i})-\nabla\phi_{j}^{*}((A\lambda)_{j}))\,.$

Consider then the following step of coordinate gradient descent for
$F^{*}_{A}$ on coordinate $(i_{k}j_{k})\in E^{+}$ of $\lambda$, performed when
edge $(i_{k}j_{k})$ is activated at iteration $k$ (corresponding to time
$t_{k}$):

$\lambda_{t_{k}}=\lambda_{t_{k}-}-\frac{1}{(2\sigma^{-1})\mu_{i_{k}j_{k}}^{2}}\nabla_{i_{k}j_{k}}F_{A}^{*}(\lambda_{t_{k}-\tau_{i_{k}j_{k}}})\,,$
(30)

corresponding to an instantiation of delayed coordinate gradient descent in
the continuized framework, on function $F_{A}^{*}$, for _P.p.p._ of
intensities $(p_{ij})$ for $(ij)\in E$ and $p_{i}^{\rm comp}$ for $(ii^{\rm
comp})\in E^{\rm comp}$. Denoting
$v_{t}=A\lambda_{t}\in\mathbb{R}^{V^{+}\times d}$ for $t\geq 0$, we obtain the
following formula for updating coordinates $i_{k},j_{k}$ of $v$ when
$i_{k}j_{k}$ activated, _irrespectively of the choice of $\mu_{ij}$ in matrix
$A$_:

$\displaystyle
v_{t_{k},i_{k}}=v_{t_{k}-,i_{k}}-\frac{\nabla\phi_{i_{k}}^{*}(v_{t_{k}-\tau_{i_{k}j_{k}},i_{k}})-\nabla\phi_{j_{k}}^{*}(v_{t_{k}-\tau_{i_{k}j_{k}},j_{k}})}{2\sigma^{-1}}\,,$
(31) $\displaystyle
v_{t_{k},j_{k}}=v_{t_{k}-,j_{k}}+\frac{\nabla\phi_{i_{k}}^{*}(v_{t_{k}-\tau_{i_{k}j_{k}},i_{k}})-\nabla\phi_{j_{k}}^{*}(v_{t_{k}-\tau_{i_{k}j_{k}},j_{k}})}{2\sigma^{-1}}\,.$

Such updates can be performed locally at nodes $i$ and $j$ after communication
between the two nodes (if $(ij)$ is a ‘physical edge’), or locally (if $(ij)$
is ‘virtual edge’). We refer in the sequel to this scheme as the Coordinate
Descent Method. While $\lambda\in\mathbb{R}^{E\times d}$ is a dual variable
defined on the edges, $v\in\mathbb{R}^{n\times d}$ is also a dual variable,
but defined on the nodes. The primal surrogate of $v$ is defined as $x=\nabla
F^{*}(v)$ _i.e._ $x_{i}=\nabla f_{i}^{*}(v_{i})$ at node $i$. It can hence be
computed with local updates on $v$. The decentralized updates of Algorithm 3
(computational updates in Algorithm 2, communication updates in Algorithm 1)
are then direct consequences of Equation (31).

The last step of the proof consists in applying Theorem 2 in order to obtain
Theorem 3. The function $F_{A}^{*}$ we introduced satisfies the assumptions of
Theorem 2 with coordinate blocks corresponding to edges $E^{+}$: The
regularity assumptions are satisfied with smoothness parameter
$L_{ij}=8\mu_{ij}^{2}\sigma^{-1}$ and local Lipschitz coefficients
$M_{(ij),(kl)}=\sqrt{L_{ij}L_{kl}}$ for any $(ij),(kl)\in E^{+}$, as shown in
Lemmas 2 and 3 in the Appendix. $F_{A}^{*}$ is moreover $\sigma$-strongly
convex666In fact, it is strongly convex on the orthogonal of $\hbox{Ker}A$,
which suffices for us to conclude since the dynamics are restricted to this
subspace. with $\sigma$ derived using Lemmas 4 and 5, and the weights
associated to matrix $A$ are chosen so that
$\mu_{ij}^{2}=\frac{\varepsilon_{ij}K_{ij}\sigma}{2\mu_{ij}^{2}}$.

Finally, the output of the algorithm at node $i$ is the primal surrogate of
variable $x_{i}(t)$ (associated to $\phi_{i}$), which is equal to
$\nabla\phi_{i}(x_{i}(t))=\frac{\sigma}{2}x_{i}(t)$.

∎

##  6\. Handling communication and computation capacity limits

###  6.1. Communication and computation capacity constraints

A given node or edge in the network may be able to handle only a limited
number of communications or computations simultaneously. In Delayed Randomized
Gossip and _DDO_ algorithms, such constraints could be violated when some
P.p.p. generates many points in a short interval. We extend our algorithms and
resulting convergence guarantees to take into account these additional
constraints.

In the continuized framework, this constraint can be enforced by truncating
the _P.p.p._ that handles activations (Definition 2). We formalize
communication and capacity constraints in Assumption 2, and show that
asynchronous speedup is still achieved in this setting in Theorem 4.

In the previous sections, step size parameters $K_{ij},K_{i}^{\rm comp}$ of
the algorithms could be tuned to counterweight the effect of delays for
arbitrary intensities $p_{ij}$. With the introduction of capacity constraints
we will see that the local optimizers at every node must also bound the
intensities $p_{ij},p_{i}^{\rm comp}$ based on local quantities. The resulting
rate of convergence is the same as in Theorems 1 and 3, up to a constant
factor of $1/2$.

We formalize communication and computation capacity constraints as follows.

######  Assumption 2 (Capacity constraints).

For some $q_{ij}$, $q_{i}^{{\rm comm}}$, $q_{i}^{{\rm
comp}}\in\mathbb{N}^{*}\cup{{\left\\{\infty\right\\}}}$, $i\in V$ and $(ij)\in
E$,

  1. (1)

_Computation Capacity:_ Node $i$ can compute only $q_{i}^{{\rm comp}}$
gradients in an interval of time of length $\tau_{i}^{{\rm comp}}$;

  2. (2)

_Communication Capacity, edge-wise limitations:_ Only $q_{ij}$ messages can be
exchanged simultaneously between adjacent nodes $i\sim j$ in an interval of
time of length $\tau_{ij}$;

  3. (3)

_Communication Capacity, node-wise limitations:_ Node $i$ can only send
$q_{i}^{{\rm comm}}$ messages in any interval of time of length
$\tau_{i}^{{\rm comm}}=\max_{j\sim i}\tau_{ij}$.

Taking into account these constraints in the analysis boils down to replacing
_P.p.p._ processes $(\mathcal{P}_{ij})_{(ij)\in E}$, $(\mathcal{P}_{i}^{\rm
comp})_{i\in V}$ of intensities $(p_{ij})$, $(p_{i}^{\rm comp})$ in the _DDO_
algorithm, by _truncated Poisson point processes_
$(\tilde{\mathcal{P}}_{ij},\tilde{\mathcal{P}}_{i}^{\rm comp})$ (see
Definition 2).

More precisely, for every edge $(ij)\in E$ (_resp._ node $i\in V$), let
$n_{ij}(t)$ be the number of communications occurring along $(ij)$ between
times $t-\tau_{ij}$ and $t$ (_resp._ $n_{i,j}^{\rm comm}$ the number of
communications node $i$ is involved in between times $t$ and $t-\tau_{ij}$,
$n_{i}^{\rm comp}$ the number of computations node $i$ is involved with
between times $t$ and $t-\tau_{i}^{\rm comp}$). Without capacity constraints,
these quantities are discrete Poisson random variables (of mean
$p_{ij}\tau_{ij}$ for $n_{ij}(t)$, _e.g._).

###  6.2. Convergence guarantees

As in Section 5, we consider communication and computation update rules as in
Algorithm 3 (_DDO_ algorithm). In the presence of capacity constraints, a
communication alongside edge $(ij)\in E$ at a clock ticking
$t\in\mathcal{P}_{ij}$ occurs and _does not break the communication capacity
constraints_ if and only if $n_{ij}(t)<q_{ij}$ (for edge-wise limitations),
$n_{i,j}^{\rm comm}(t)<q_{i}^{\rm comm}$ and $n_{j,i}^{\rm comm}(t)<q_{j}^{\rm
comm}$ (for node-wise limitations) are satisfied. The realistic implementation
of these _truncated Point processes_ is discussed in Section 8.

Under capacity constraints, we have the following guarantees for our
algorithm, defined as in Algorithm 3 (Algorithm 1 for communications and
Algorithm 2 for local computations), where communications and computations
that violate the capacity constraints are dropped.

######  Theorem 4.

Assume for any $i\in V$ and $(ij)\in E$:

$\displaystyle cp_{i}^{{\rm comp}}\tau_{i}^{{\rm comp}}\leq q_{i}^{{\rm
comp}},$ (32) $\displaystyle cp_{ij}\tau_{ij}\leq q_{ij},$ $\displaystyle
c\sum_{j\sim i}p_{ij}\tau_{i}^{{\rm comm}}\leq q_{i}^{{\rm comm}}\,,$

where $c=1/(1-\sqrt{\ln(6)/2})$ is a numerical constant. Then, if the
assumptions of Theorem 3 described in Equation 26 additionally hold, for
$\gamma$ verifying

$\gamma\leq\min\left(\frac{\sigma}{8L}\lambda_{2}\big{(}\Delta_{G}(\nu_{ij}=K_{ij})\big{)}\,,\,\frac{1}{\tau_{\max}}\right)\,,$

we have:

$\frac{\int_{0}^{T}e^{\gamma
t}\mathbb{E}\left[{{\left\|\frac{\sigma}{2}x(t)-\bar{x}^{\star}\right\|}}^{2}\right]{\rm
d}t}{\int_{0}^{T}e^{\gamma
t}{{\left\|\frac{\sigma}{2}x(0)-\bar{x}^{\star}\right\|}}^{2}{\rm d}t}\leq
e^{-\frac{\gamma
T}{2}}\frac{L}{\sigma}\frac{1+\frac{\tau_{\max}}{T}}{1-\gamma\tau_{\max}}\,.$

The same guarantees as without the capacity constraints thus hold, up to a
constant factor $1/2$ in the rate of convergence. The conditions on the
activation intensities (32) suggest that graph sparsity is beneficial: for
$q_{i}^{\rm comm}$ small, $2\sum_{j\sim i}p_{ij}\tau_{i}^{{\rm comm}}\leq
q_{i}^{{\rm comm}}$ translates into $p_{ij}$ scaling with the inverse of the
edge-degree of $(ij)$, so large degrees thus slow down the convergence. The
new conditions (32) are easily enforced with the natural choice of intensities
$p_{ij}$ (_resp._ $p_{i}^{\rm comp}$) of order $1/\tau_{ij}$ (_resp._
$\tau_{i}^{\rm comp}$).

Taking $q_{i}^{\rm comm}=1$, we recover the behavior of _loss networks_
(Kelly, 1991), where a node cannot concurrently communicate with different
neighbors. Gossip on loss networks was previously studied in Even et al.
(2020), to obtain some form of asynchronous speedup. Comparatively, our
present algorithms are structurally simpler and their analysis in the
continuized framework yields faster convergence speeds.

###  6.3. Proof of Theorem 4

###### Proof.

The algorithm under capacity constraints is obtained by applying coordinate
gradient descent in the continuized framework to the same dual problem as in
Section 5, but with random variables “$\varepsilon_{k}(t)$” that are not taken
constant equal to 1. Here, for $(ij)\in E$ and $t\in\mathcal{P}_{ij}$, we have

$\varepsilon_{ij}(t)=1_{{\left\\{n_{ij}(t)<q_{ij}\,,\,n_{i}^{\rm
comm}(t)<q_{i}^{\rm comm}\,,\,n_{j}^{\rm comm}(t)<q_{j}^{\rm
comm}\right\\}}}\,,$

while for $i\in V$ and $t\in\mathcal{P}_{i}^{\rm comp}$,

$\varepsilon_{ii^{\rm comp}}(t)=1_{{\left\\{n_{i}^{\rm comp}<q_{i}^{\rm
comp}\right\\}}}\,.$

We apply Theorem 2 as in the proof of Theorem 3, leading to the same stability
conditions on the step sizes $K_{ij},K_{i}^{\rm comp}$, while the rate of
convergence is multiplied by a lower bound $\varepsilon$ on all
$\mathbb{E}\left[\varepsilon_{ij}(t)\right]$ and
$\mathbb{E}\left[\varepsilon_{ii^{\rm comp}}(t)\right]$. Let us finally
compute such a lower bound $\varepsilon$.

For $(ij)\in E$, $n_{ij}(t)$ is stochastically dominated by $Z_{ij}$ a Poisson
random variable of parameter $p_{ij}\tau_{ij}$, while $n_{i}^{\rm comm}(t)$
and $n_{j}^{\rm comm}(t)$ are respectively dominated by $Z_{i}$ and $Z_{j}$,
Poisson random variables of parameters $\tau_{ij}\sum_{k\sim i}p_{ki}$ and
$\tau_{ij}\sum_{\ell\sim j}p_{\ell j}$, so that:

$\displaystyle\mathbb{E}\left[\varepsilon_{ij}(t)\right]$
$\displaystyle\geq\mathbb{P}\left(Z_{ij}<q_{ij}\,,\,Z_{i}<q_{i}^{\rm
comm}\,,\,Z_{j}<q_{j}^{\rm comm}\right)$ $\displaystyle\geq
1-\mathbb{P}(Z_{ij}\geq q_{ij})-\mathbb{P}(Z_{i}\geq q_{i}^{\rm
comm})-P(Z_{j}\geq q_{j}^{\rm comm})\,.$

We now prove that $\mathbb{P}(Z_{ij}\geq q_{ij}),\mathbb{P}(Z_{i}\geq
q_{i}^{\rm comm}),P(Z_{j}\geq q_{j}^{\rm comm})$ are all inferior to $1/6$.
For $\mathbb{P}(Z_{ij}\geq q_{ij})$, using that for $Z$ a Poisson variable of
parameter $\mu$ and $x\geq 0$,

$\mathbb{P}(Z_{\mu}\geq\mu+x)\leq e^{\frac{-x^{2}}{\mu+x}}\,,$

we have $\mathbb{P}(Z_{ij}\geq q_{ij})\leq
e^{-\frac{(q_{ij}-p_{ij}\tau_{ij})^{2}}{q_{ij}}}\leq e^{-2(1-1/c)^{2}}$ if
$q_{ij}\geq 2$, and this quantity is equal to $1/6$, by definition of $c$.
Then, if $q_{ij}=1$, using $\mathbb{P}(Z_{\mu}\geq 1)=1-e^{-\mu}$, we have
that $\mathbb{P}(Z_{ij}\geq q_{ij})\leq p_{ij}\tau_{ij}\leq 1/c\leq 1/6$. We
proceed in the same way for $\mathbb{P}(Z_{i}\geq q_{i}^{\rm
comm}),P(Z_{j}\geq q_{j}^{\rm comm})$. Hence,
$\mathbb{E}\left[\varepsilon_{ij}(t)\right]\geq 1/2$ under our assumptions on
the Poisson intensities. Similarly, we prove that
$\mathbb{E}\left[\varepsilon_{ii^{\rm comp}}(t)\right]\geq 1/2$, and this
concludes the proof. ∎

##  7\. Braess’s Paradox and Experiments

In this section, we investigate how the local step sizes $K_{ij}$ and Poisson
intensities $p_{ij}$ used in Theorems 1, 3 and 4 should be tuned for a fixed
choice of communication delays. Consider the line graph with constant delays
$\tau_{i,i+1}=\tau$. Add edge $(1,n)$ in order to close the line, with a delay
$\tau_{1n}=\tau^{\prime}$ with arbitrarily large $\tau^{\prime}$. If the added
Poisson intensity $p_{1n}$ satisfies $\tau_{1n}p_{1n}\to\infty$, then
according to Theorem 1, we have $K_{12}\to 0$ and $K_{n-1,n}\to 0$.
Consequently, since $\gamma=\mathcal{O}(\Delta_{G}(K)$, we have $\gamma\to 0$:
the weighted graph becomes close to disconnected. By adding an edge to the
graph, the convergence speed of delayed randomized gossip is degraded.

In order to alleviate the phenomenon, we would need to virtually delete the
edge, by setting $p_{1n}=0$. Figure 1 illustrates this phenomenon in the more
general setting: one can sparsify the communication graph by solving a
regularized optimization problem over the $p_{ij}$ in order to maximize
$\lambda_{2}(\Delta_{G}(K))$ ($K$ being a function of $p$), leading to both
faster consensus and smaller communication complexity (and thus lower energy
footprint).

In road-traffic, removing one or more roads in a road network can speed up the
overall traffic flow. This phenomenon, called _Braess’s paradox_ (Easley and
Kleinberg, 2010), also arises in loss networks (Bean et al., 1997). In our
problem, this translates to removing an edge $(ij)$ with a non-negligible
Poisson intensity $p_{ij}$. We take $G_{1}$ a dense Erdős-Rényi random graph
(Figure 1(a)) of parameters $n=30,p=0.75$. Delays $\tau_{ij}$ are taken equal
to 0.01 with probability 0.9, and to 1 with probability 0.1. Initially,
intensities are set as $p_{ij}^{(1)}=1/\tau_{ij}$. Maximizing:

$\lambda_{2}\left(\Delta_{G}\big{(}\frac{p_{ij}}{1+\sum_{kl\sim
ij}p_{kl}(\tau_{ij}+e\tau_{kl})}\big{)}\right)-\omega\sum_{(ij)\in
E}p_{ij}\tau_{ij}$

over $(p_{ij})_{ij}$, we obtain intensities $p^{(2)}$ and a graph $G_{2}$
(Figure 1(b)), sparser than $G_{1}$: we delete edges that have a null
intensity (_i.e._ such that $p_{ij}^{(2)}=0$). We then run our delayed gossip
algorithm for initialization $x_{0}$ a Dirac mass ($x_{0}(i)=I_{i=i_{0}}$), on
$G_{1}$ (blue curves) and $G_{2}$, for the choice of $K_{ij}$ as in Theorem 1.
The green curve is the synchronous gossip algorithm Dimakis et al. (2010) on
$G_{1}$, to illustrate the asynchronous speedup, where each iteration takes a
time $\tau_{\max}=1$. In Figure 1(c), the error to the consensus is measured
as a function of the continuous time, while it is measured in terms of number
of updates in Figure 1(d) and in terms of energy (defined as
$\sum_{k:T_{k}<t}\tau_{i_{k}j_{k}}$ at time $t$: the energy consumed by a
communication is assumed to be proportional to the time the communication
took) in Figure 1(e).

As expected, in terms of number of updates in the whole graph and energy
spent, the sparser graph is more effective: slow and costly edges were
deleted. Perhaps more surprising, but supported by our theory (Theorem 3) and
the resulting Braess’s paradox, this also holds in Figure 1(c): even though in
the same amount of time, less updates are made in the sparser graph $G_{2}$
than in $G_{1}$, delayed randomized gossip is still faster on $G_{2}$ than
$G_{1}$. Making less updates and deleting some communications make all other
communications more efficient.

We believe that this phenomenon could be exploited for efficient design of
large scale networks, beyond the maximization the spectral gap regardless of
physical constraints as in Ying et al. (2021) for instance.

(a) Graph $G_{1}$ (E-R)

(b) Graph $G_{2}$ (after sparsification)

(c) Continuous time

(d) Number of updates in the whole graph

(e) Energy spent

Figure 1. Experiments and Braess’s paradox.

##  8\. Decentralized generation of _truncated Poison point processes_

###  8.1. Practical Implementation and Limitations of Algorithm 3 (_DDO)_

In order for _DDO_ (or Delayed Randomized Gossip) to be implemented (with or
without _truncated P.p.p._), some conditions are required, leading to some
limitations that we discuss below. Communication steps at some time $t$ are of
the form $-\eta_{ij}(x_{i}(t-\tau_{ij})-x_{j}(t-\tau_{ij}))$ (on node $i$):
the (delayed) iterates of local variables $x_{i}$ and $x_{j}$ for this update
are required to have the exact same delay. This comes from our dual
formulation. Secondly, it is not clear who has the initiative of
communications in our algorithm, since we treat delays and communications
edge-wise. However, we propose here a practical implementation of _DDO_ ,
taking into account all these limitations: nodes have the initiative of
communications and delayed variables are enforced to have the same constant
delays (equal to an upper-bound on these delays).

#### Computation Updates at node $i$

let $\mathcal{N}_{i}^{{\rm comp}}(t)$ be the number of computations launched
at node $i$ between times $t$ and $t-\tau_{i}^{{\rm comp}}$. Initialize
$\mathcal{P}_{i}^{{\rm comp}}$ as $\\{t_{0}\\}$ where $t_{0}$ is a random time
of exponential law of parameter $p_{i}^{{\rm comp}}$. At any time
$t\in\mathcal{P}_{i}^{{\rm comp}}$:

  1. (1)

Compute a random time $T$ of exponential law of parameter $p_{i}^{{\rm
comp}}$, and add $t+T$ to $\mathcal{P}_{i}^{{\rm comp}}$;

  2. (2)

_Computation:_ at time $t$, if $\mathcal{N}_{i}^{{\rm comp}}(t)<q_{i}^{{\rm
comp}}$, $i$ computes $\nabla g_{i^{{\rm comp}}}^{*}(y_{i}^{{\rm comp}}(t))$
and saves into memory node-variable $x_{i}(t)$;

  3. (3)

_Update:_ at time $t+\tau_{i}^{{\rm comp}}$, the computation is finished, and
the computation update (29) can be performed.

#### Communication Updates at node $i$

let $\mathcal{N}_{i}^{{\rm comm}}(t)$ and $\mathcal{N}_{ij}(t)$ for $j\sim i$
respectively be the number of communications started by node $i$ between times
$t$ and $t-\tau_{i}^{{\rm comm}}$ and the number of communications started
between nodes $i$ and $j$ in $[t-\tau_{ij},t]$. Initialize
$\mathcal{P}_{i}^{{\rm comm}}$ as $\\{t_{0}\\}$ where $t_{0}$ is a random time
of exponential law of parameter $\sum_{j\sim i}p_{ij}/2$. At any time
$t\in\mathcal{P}_{i}^{{\rm comm}}$:

  1. (1)

Compute a random time $T$ of exponential law of parameter $\sum_{j\sim
i}p_{ij}/2$, and add $t+T$ to $\mathcal{P}_{i}^{{\rm comm}}$;

  2. (2)

_Local synchronization:_ at time $t$, if $\mathcal{N}_{i}^{{\rm
comm}}(t)<q_{i}^{{\rm comm}}$, $i$ chooses an adjacent node $j$ with
probability $p_{ij}/\sum_{k\sim i}p_{ik}$, and sends a _ping_ (smallest
message possible). We assume that sending a _ping_ takes a time upper-bounded
by $\tau_{ij}^{{\rm ping}}$. Upon reception of this _ping_ , if
$\mathcal{N}_{j}^{{\rm comm}}(t)<q_{j}^{{\rm comm}}$, $j$ returns the same
_ping_ to $i$. $i$ and $j$ are thus synchronized at time $t+2\tau_{ij}^{{\rm
ping}}$. Until the return of the feedback by node $j$, $i$ assumes in its
request list that this communication will happen.

  3. (3)

_Communication:_ if $\mathcal{N}_{ij}(t+2\tau_{ij}^{{\rm ping}})<q_{ij}$, $i$
sends $x_{i}(t)$ to $j$ and $j$ sends $x_{j}(t)$ to $i$, while each agent
keeps in memory the vector sent. For this to be possible, at a time $s$, node
$i$ needs to keep in memory its local values at times between $s-\max_{j\sim
i}\tau_{ij}^{{\rm ping}}$ and $s$ (a small number of values usually, so that
is not too restrictive).

  4. (4)

_Update:_ at time $t+2\tau_{ij}^{{\rm ping}}+\tau_{ij}$, update (9) can thus
be performed.

The induced process has the same law as the one studied and analyzed thanks to
the classical property that a P.p.p. with intensity $p$ has its distribution
unchanged after translation of all its points by some constant $\tau_{ij}$.
The communication/computation scheme above emphasizes the fact that quantities
$\tau_{ij},\tau_{i}^{{\rm comp}}$ are upper bounds on the delays of local
communication/computations. The delay is here $\tau_{ij}+2\tau_{ij}^{{\rm
ping}}$ instead of simply $\tau_{ij}$ yet these are of the same order since
$\tau_{ij}^{{\rm ping}}\leq\tau_{ij}$.

###  8.2. Discussion of our assumptions

#### Continuous time clocks

Implicitly we have assumed that agents in the networks share a continuous-time
clock.

We now discuss how critical this assumption is. One may wonder if clock skews,
drifts or shifts between agents could lead to unwanted behavior (instability).
First, computer clocks are synchronized via Network Time Protocol (NTP) or
other more recent and more robust protocols, justifying the assumption of a
common shared clock. However, failures in these protocols could lead to slight
skews, that need to be addressed. Looking at our algorithm, it in fact appears
that, using timestamps, nodes do not need to be perfectly synchronized, as
long as time in each local clock passes at the same speed. Shifts in time-
synchronization thus do not appear to be the core practical difficulty: clock
drifts (clocks that do not have the same frequency and where time thus passes
at a different speed) are the remaining issue. However, this can be dealt with
simply by augmenting pairwise delays to take that into account.

#### Local upper bounds of the local delays

Our rates depend on local upper bounds of the local delays, that need to be
known in order to tune the coefficients. The drawback is thus that, if a
node/edge has an erratic behavior (fast but rarely slow), we only use the
upper-bound on the delays, which can lead to slower convergence. However, we
believe that this is a drawback of most (if not all) asynchronous algorithms,
where delays are dealt with by diminishing step sizes. These step sizes are
tuned using upper bounds on the delays. Even if we did not artificially force
the delays to be equal to the local upper bound $\tau_{ij}$, we would have to
tune $K_{ij}$ based on these upper bounds, resulting in the same rates of
convergence. A natural extension would be to consider whether step sizes can
be adapted to the physical delay as in Mishchenko et al. (2022) for
asynchronous SGD, therefore obtaining an asynchronous speedup and guarantees
without requiring any knowledge on the delay upper bounds.

## Conclusion

We introduced a novel analysis framework for the study of algorithms in the
presence of delays, establishing that an _asynchronous speedup_ can be
achieved in decentralized optimization. Our results hold for explicit choices
of algorithm parameters based on local network characteristics. They derive
from the continuous-time analysis and assumptions handled in our continuized
framework. The explicit conditions and convergence rates we obtain allow us to
further discuss counter-intuitive effects akin to the Braess paradox, such as
the possibility to speed up convergence by suppressing communication links.
Although the algorithm requires dual updates, a fully primal algorithm could
be obtained by using Bregman gradients Hendrikx et al. (2020) or a primal-dual
formulation Kovalev et al. (2020).

##  Appendix A Appendix

###  A.1. Regularity

For $\sigma$-strongly convex and $L$-smooth functions $f_{1},\ldots,f_{n}$ on
$\mathbb{R}^{d}$ and for $A\in\mathbb{R}^{V\times E}$ such that
$Ae_{ij}=\mu_{ij}(e_{i}-e_{j})$ for $(ij)\in E$, define $F_{A}^{*}$ a function
$\mathbb{R}^{E\times d}\to\mathbb{R}$ as:

$F_{A}^{*}(\lambda)=\frac{1}{n}\sum_{i\in
V}f_{i}((A\lambda_{i}))\,,\quad\lambda\in\mathbb{R}^{E\times d}\,.$

######  Lemma 2.

For any $(ij)\in E$, $F_{A}^{*}$ is $L_{ij}:=4\mu_{ij}^{2}\sigma^{-1}$-smooth
on $E_{ij}$ the subspace of coordinates $(ij)\in E$.

###### Proof.

Let $h_{ij}\in\mathbb{R}^{d}$ and $\lambda\in\mathbb{R}^{E\times d}$. Using
the $\sigma^{-1}$-smoothness of $f_{i}^{*}$ and $f_{j}^{*}$:

$\displaystyle F_{A}^{*}(\lambda$
$\displaystyle+e_{ij}h_{ij}^{\top})-F_{A}^{*}(\lambda)=f_{i}^{*}((A(\lambda+e_{ij}h_{ij})^{\top})_{i})-f_{i}^{*}((A\lambda)_{i})$
$\displaystyle+f_{j}^{*}((A(\lambda+e_{ij}h_{ij}^{\top}))_{j})-f_{j}^{*}((A\lambda)_{j})$
$\displaystyle\leq\langle\nabla_{ij}F_{A}^{*}(\lambda),e_{ij}h_{ij}^{\top}\rangle$
$\displaystyle+\frac{\sigma^{-1}}{2}{{\left\|(Ae_{ij}h_{ij}^{\top})_{i}\right\|}}^{2}+\frac{\sigma^{-1}}{2}{{\left\|(Ae_{ij}h^{\top}_{ij})_{j}\right\|}}^{2}\,,$

concluding the proof, as
${{\left\|(Ae_{ij}h_{ij}^{\top})_{i}\right\|}}^{2}=2\mu_{ij}^{2}{{\left\|h_{ij}\right\|}}^{2}$.
∎

######  Lemma 3.

For any $(ij)\in E$, any $\lambda,\lambda^{\prime}\in\mathbb{R}^{E^{+}\times
d}$:

${{\left\|\nabla_{ij}F_{A}^{*}(\lambda)-\nabla_{ij}F_{A}^{*}(\lambda^{\prime})\right\|}}\leq\sum_{(kl)\sim(ij)}M_{(ij),(kl)}{{\left\|\lambda_{kl}-\lambda^{\prime}_{kl}\right\|}},$
(33)

where $M_{(ij),(kl)}=\sqrt{L_{ij}L_{kl}}$ and
$L_{ij}=4\mu_{ij}^{2}\sigma^{-1},L_{kl}=4\mu_{kl}^{2}\sigma^{-1}$.

###### Proof.

Since $\nabla_{ij}F_{A}^{*}(\lambda)=(Ae_{ij})^{\top}((\nabla
g_{i}^{*}((A\lambda)_{i})-\nabla g_{j}^{*}((A\lambda)_{j}))$, we have:

$\displaystyle{{\left\|\nabla_{ij}F_{A}^{*}(\lambda)-\nabla_{ij}F_{A}^{*}(\lambda^{\prime})\right\|}}$
$\displaystyle=\big{\|}(Ae_{ij})^{\top}((\nabla
f_{i}^{*}((A\lambda)_{i})-\nabla f_{i}^{*}((A\lambda^{\prime})_{i})$
$\displaystyle\quad-\nabla f_{j}^{*}((A\lambda)_{j})+\nabla
f_{j}^{*}((A\lambda^{\prime})_{j}))\big{\|}$
$\displaystyle\leq{{\left\|Ae_{ij}\right\|}}\big{(}{{\left\|\nabla
f_{i}^{*}((A\lambda)_{i})-\nabla f_{i}^{*}((A\lambda^{\prime})_{i})\right\|}}$
$\displaystyle\quad+{{\left\|\nabla f_{j}^{*}((A\lambda)_{j})-\nabla
f_{j}^{*}((A\lambda^{\prime})_{j})\right\|}}\big{)}$
$\displaystyle\leq\sqrt{2}|\mu_{ij}|\big{(}\sigma_{i}^{-1}{{\left\|(A\lambda)_{i}-(A\lambda^{\prime})_{i}\right\|}}+\sigma_{j}^{-1}{{\left\|(A\lambda)_{j}-(A\lambda^{\prime})_{j}\right\|}}\big{)}$
$\displaystyle=\sqrt{2}|\mu_{ij}|\left(\sigma_{i}^{-1}{{\left\|\sum_{k\sim
i}\mu_{ik}(\lambda_{ik}-\lambda^{\prime}_{ik})\right\|}}\right.$
$\displaystyle\quad\left.+\sigma_{j}^{-1}{{\left\|\sum_{l\sim
j}\mu_{jl}(\lambda_{jl}-\lambda^{\prime}_{jl})\right\|}}\right)$
$\displaystyle\leq\sqrt{2}|\mu_{ij}|\left(\sigma_{i}^{-1}\sum_{k\sim
i}|\mu_{ik}|{{\left\|\lambda_{ik}-\lambda^{\prime}_{ik}\right\|}})\right.$
$\displaystyle\quad\left.+\sigma_{j}^{-1}\sum_{l\sim
j}|\mu_{jl}|{{\left\|\lambda_{jl}-\lambda^{\prime}_{jl}\right\|}})\right)$
$\displaystyle\leq\sqrt{2}|\mu_{ij}|\left(\sqrt{\sigma_{i}^{-1}+\sigma_{j}^{-1}}\sqrt{\sigma_{i}^{-1}+\sigma_{k}^{-1}}\sum_{k\sim
i}|\mu_{ik}|{{\left\|\lambda_{ik}-\lambda^{\prime}_{ik}\right\|}})\right.$
$\displaystyle\quad+\left.\sqrt{\sigma_{i}^{-1}+\sigma_{j}^{-1}}\sqrt{\sigma_{l}^{-1}+\sigma_{j}^{-1}}\sum_{l\sim
j}|\mu_{jl}|{{\left\|\lambda_{jl}-\lambda^{\prime}_{jl}\right\|}})\right)$
$\displaystyle\leq\sum_{(kl)\sim(ij)}\sqrt{L_{ij}L_{kl}}{{\left\|\lambda_{kl}-\lambda^{\prime}_{kl}\right\|}},$

where $L_{ij},L_{kl}$ as in Lemma 2. ∎

######  Lemma 4 (Strong convexity).

The strong convexity parameter $\sigma_{A}$ of $F_{A}^{*}$ on the orthogonal
of $\ker(A)$ is lower bounded by
$L^{-1}\lambda_{2}(\Delta_{G}(\mu_{ij}^{2}))$, where we recall that
$\lambda_{2}(\Delta_{G}(\mu_{ij}^{2}))$ is the graph Laplacian with weights
$\mu_{ij}^{2}$.

###### Proof.

Let $\lambda,\lambda^{\prime}\in\mathbb{R}^{E\times d}$. For $i\in V$, by
$L^{-1}$-strong convexity of $f_{i}^{*}$:

$\displaystyle f_{i}^{*}((A\lambda)_{i})-f_{i}^{*}((A\lambda^{\prime})_{i})$
$\displaystyle\geq\langle\nabla
f_{i}^{*}((A\lambda^{\prime})_{i}),(A(\lambda-\lambda^{\prime}))_{i}\rangle$
$\displaystyle\quad+\frac{1}{2L}\|(A(\lambda-\lambda^{\prime}))_{i}\|^{2}.$

Summing over all $i\in V$ and using $\nabla
F_{A}^{*}(\lambda^{\prime})=A^{\top}(\nabla_{i}f_{i}^{*}((A\lambda^{\prime})_{i}))_{i\in
V}$ leads to:

$\displaystyle F_{A}^{*}(\lambda)-F_{A}^{*}(\lambda^{\prime})$
$\displaystyle\geq\langle\nabla
F_{A}^{*}(\lambda^{\prime}),\lambda-\lambda^{\prime}\rangle+\frac{1}{2L}\|A(\lambda^{\prime}-\lambda\|^{2}$
$\displaystyle\geq\langle\nabla
F_{A}^{*}(\lambda^{\prime}),\lambda-\lambda^{\prime}\rangle+\frac{\lambda^{+}_{\min}(A^{T}A)}{4}{\|\lambda-\lambda^{\prime}\|^{*}}^{2}.$

where $\|.\|^{*}$ is the euclidean norm on the orthogonal of $Ker(A)$.
Finally, notice that $AA^{\top}=\Delta_{G}(\mu_{ij}^{2})$ and has same
eigenvalues as $A^{\top}A$. ∎

###  A.2. The smallest positive eigenvalue of the augmented graph’s weighted
Laplacian matrix

Let $G=(V,E)$ be the “physical” graph, augmented as $G^{+}=(V^{+},E^{+})$,
where $V^{+}=V\cup{{\left\\{i^{\rm comp},i\in V\right\\}}}$ and
$E^{+}=E\cup{{\left\\{(ii^{\rm comp}),i\in V\right\\}}}$ as in Section 5.

######  Lemma 5.

For $\nu^{+}=(\nu_{ij})_{(ij)\in E^{+}}$ non negative weights, the smallest
positive eigenvalue of the Laplacian of the augmented graph $G^{+}$ with
weights $\nu^{+}$ satisfies:

$\lambda_{2}\big{(}\Delta_{G^{+}}(\nu^{+})\big{)}\geq\frac{1}{4}\min\left(\lambda_{2}\big{(}\Delta_{G}(\nu)\big{)}\,,\,\min_{i\in
V}\nu_{ii^{\rm comp}}\right)\,,$

where $\lambda_{2}\big{(}\Delta_{G}(\nu)\big{)}$ is the smallest eigenvalue of
the original graph, with weights $\nu=(\nu_{ij})_{(ij)\in E}$.

###### Proof.

Let $m=\min_{i\in V}\nu_{ii^{\rm comp}}$ and
$\lambda=\lambda_{2}\big{(}\Delta_{G}(\nu)\big{)}$. For any
$X=(x,y)\in\mathbb{R}^{V^{+}}$, we have:

$\displaystyle X^{\top}\Delta_{G^{+}}(\nu^{+})X$ $\displaystyle=\sum_{(ij)\in
E^{+}}\nu_{ij}(X_{i}-X_{j})^{2}$
$\displaystyle=x^{\top}\Delta_{G}(\nu)x+\sum_{i\in V}\nu_{ii^{\rm
comp}}(x_{i}-y_{i})^{2}$
$\displaystyle\geq\lambda{{\left\|x-\bar{X}\right\|}}^{2}+m{{\left\|x-y\right\|}}^{2}\,.$

Then, for $c>0$ sufficiently small such that for any
$z,z^{\prime}\in\mathbb{R}$, $\lambda z^{2}+m(z-z^{\prime})^{2}\geq
cz^{2}+cz^{\prime 2}$, we have $X^{\top}\Delta_{G^{+}}(\nu^{+})X\geq
c{{\left\|X-\bar{X}\right\|}}^{2}$ and so
$\lambda_{2}\big{(}\Delta_{G^{+}}(\nu^{+})\big{)}\geq c$. Let us now compute
such a value $c$, to conclude this proof.

For $z,z^{\prime}\in\mathbb{R}$,

$\displaystyle\lambda z^{2}+m(z-z^{\prime})^{2}-cz^{2}+cz^{\prime 2}$
$\displaystyle=(\lambda+m-c)z^{2}+(m-c)z^{\prime 2}-2mzz^{\prime}$
$\displaystyle=\left(\sqrt{\lambda+m-c}z-\frac{m}{\sqrt{\lambda+m-c}z^{\prime}}\right)$
$\displaystyle\quad+\left(m-c+\frac{m^{2}}{\lambda+m-c}\right)z^{\prime}\,,$

and this quantity is non-negative as long as $c\leq\min(\lambda,m)/4$. ∎

## References

  * Assran et al. [2020] Mahmoud Assran, Arda Aytekin, Hamid Reza Feyzmahdavian, Mikael Johansson, and Michael G Rabbat.  Advances in asynchronous parallel and distributed optimization.  _Proceedings of the IEEE_ , 108(11):2013–2031, 2020.
  * Assran and Rabbat [2021] Mahmoud S. Assran and Michael G. Rabbat.  Asynchronous gradient push.  _IEEE Transactions on Automatic Control_ , 66(1):168–183, 2021.
  * Bean et al. [1997] N. G. Bean, F. P. Kelly, and P. G. Taylor.  Braess’s paradox in a loss network.  _Journal of Applied Probability_ , 34(1):155–159, 1997.
  * Bertsekas [1989] Dimitri P Bertsekas.  _Parallel and distributed computation: numerical methods_ , volume 23.  Prentice hall Englewood Cliffs, NJ, 1989.
  * Boyd et al. [2006] Stephen Boyd, Arpita Ghosh, Balaji Prabhakar, and Devavrat Shah.  Randomized gossip algorithms.  _IEEE transactions on information theory_ , 52(6):2508–2530, 2006.
  * Bubeck [2015] Sébastien Bubeck.  Convex optimization: Algorithms and complexity.  _Found. Trends Mach. Learn._ , 8(3–4):231–357, November 2015.
  * Cheung et al. [2020] Yun Kuen Cheung, Richard Cole, and Yixin Tao.  Fully asynchronous stochastic coordinate descent: a tight lower bound on the parallelism achieving linear speedup.  _Mathematical Programming_ , pages 1–63, 2020.
  * Cooke [1963] Kenneth L Cooke.  Differential—difference equations.  In _International symposium on nonlinear differential equations and nonlinear mechanics_ , pages 155–171. Elsevier, 1963.
  * Davis [1984] M. H. A. Davis.  Piecewise-deterministic markov processes: A general class of non-diffusion stochastic models.  _Journal of the Royal Statistical Society. Series B (Methodological)_ , 46(3):353–388, 1984.  ISSN 00359246.  URL http://www.jstor.org/stable/2345677.
  * Dimakis et al. [2010] A. G. Dimakis, S. Kar, J. M. F. Moura, M. G. Rabbat, and A. Scaglione.  Gossip algorithms for distributed signal processing.  _Proceedings of the IEEE_ , 98(11):1847–1864, 2010.
  * Easley and Kleinberg [2010] David Easley and Jon Kleinberg.  _Networks, Crowds, and Markets: Reasoning about a Highly Connected World_.  Cambridge University Press, 2010.
  * Even et al. [2020] Mathieu Even, Hadrien Hendrikx, and Laurent Massoulié.  Asynchrony and acceleration in gossip algorithms.  _arXiv preprint arXiv:2011.02379_ , 2020.
  * Even et al. [2021] Mathieu Even, Raphaël Berthier, Francis Bach, Nicolas Flammarion, Pierre Gaillard, Hadrien Hendrikx, Laurent Massoulié, and Adrien Taylor.  A continuized view on nesterov acceleration for stochastic gradient descent and randomized gossip.  _arXiv preprint arXiv:2106.07644_ , 2021.
  * Gu and Liu [2009] Keqin Gu and Yi Liu.  Lyapunov–krasovskii functional for uniform stability of coupled differential-functional equations.  _Automatica_ , 45(3):798–804, 2009.
  * Hannah et al. [2019] Robert Hannah, Fei Feng, and Wotao Yin.  A2BCD: Asynchronous acceleration with optimal complexity.  In _International Conference on Learning Representations_ , 2019.
  * Hendrikx et al. [2019a] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié.  An accelerated decentralized stochastic proximal algorithm for finite sums.  In _Advances in Neural Information Processing Systems_ , 2019a.
  * Hendrikx et al. [2019b] Hadrien Hendrikx, Francis Bach, and Laurent Massoulie.  Accelerated decentralized optimization with local updates for smooth and strongly convex objectives.  In _International Conference on Artificial Intelligence and Statistics_ , volume 89 of _Proceedings of Machine Learning Research_ , pages 897–906. PMLR, 16–18 Apr 2019b.
  * Hendrikx et al. [2020] Hadrien Hendrikx, Francis Bach, and Laurent Massoulié.  Dual-free stochastic decentralized optimization with variance reduction.  In _Advances in Neural Information Processing Systems_ , 2020.
  * Horn [2012] Roger Horn.  _Matrix analysis_.  Cambridge University Press, Cambridge New York, 2012.
  * Kelly [1991] F. P. Kelly.  Loss networks.  _The Annals of Applied Probability_ , 1(3):319–378, 1991.
  * Klenke [2014] Achim Klenke.  _The Poisson Point Process_ , pages 543–561.  Springer London, 2014.
  * Koloskova et al. [2019] Anastasia Koloskova, Sebastian Stich, and Martin Jaggi.  Decentralized stochastic optimization and gossip algorithms with compressed communication.  In _International Conference on Machine Learning_ , volume 97, pages 3478–3487. PMLR, 2019.
  * Kovalev et al. [2020] Dmitry Kovalev, Adil Salim, and Peter Richtárik.  Optimal and practical algorithms for smooth and strongly convex decentralized optimization.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Kovalev et al. [2021] Dmitry Kovalev, Elnur Gasanov, Alexander Gasnikov, and Peter Richtárik.  Lower bounds and optimal algorithms for smooth and strongly convex decentralized optimization over time-varying networks.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.
  * Le Gall [2016] Jean-François Le Gall.  _Brownian Motion, Martingales, and Stochastic Calculus_ , volume 274\.  Springer, 01 2016.
  * Leblond et al. [2018] Remi Leblond, Fabian Pedregosa, and Simon Lacoste-Julien.  Improved asynchronous parallel optimization analysis for stochastic incremental methods.  _Journal of Machine Learning Research_ , 19(81):1–68, 2018.
  * Li et al. [2016] Jueyou Li, Guo Chen, Zhao Yang Dong, and Zhiyou Wu.  Distributed mirror descent method for multi-agent optimization with delay.  _Neurocomputing_ , 177:643–650, 2016.
  * Lian et al. [2018] Xiangru Lian, Wei Zhang, Ce Zhang, and Ji Liu.  Asynchronous decentralized parallel stochastic gradient descent.  In Jennifer Dy and Andreas Krause, editors, _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 3043–3052. PMLR, 10–15 Jul 2018.  URL https://proceedings.mlr.press/v80/lian18a.html.
  * Lu et al. [2015] Jie Lu, Hamid Reza Feyzmahdavian, and Mikael Johansson.  Dual coordinate descent algorithms for multi-agent optimization.  In _2015 European Control Conference (ECC)_ , pages 715–720, 2015\.
  * Mania et al. [2017] Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan.  Perturbed iterate analysis for asynchronous stochastic optimization.  _SIAM Journal on Optimization_ , 27(4):2202–2229, January 2017.
  * Massoulié [2002] Laurent Massoulié.  Stability of distributed congestion control with heterogeneous feedback delays.  _Automatic Control, IEEE Transactions on_ , 47:895 – 902, 07 2002.
  * Mishchenko et al. [2022] Konstantin Mishchenko, Francis Bach, Mathieu Even, and Blake Woodworth.  Asynchronous sgd beats minibatch sgd under arbitrary delays, 2022.  URL https://arxiv.org/abs/2206.07638.
  * Mohar et al. [1991] Mohar, Y Alavi, G Chartrand, and OR Oellermann.  The laplacian spectrum of graphs.  _Graph theory, combinatorics, and applications_ , 1991.
  * Moradian and Kia [2018] Hossein Moradian and Solmaz S Kia.  A study on rate of convergence increase due to time delay for a class of linear systems.  In _2018 IEEE Conference on Decision and Control (CDC)_ , pages 5433–5438. IEEE, 2018.
  * Nedic and Ozdaglar [2009] A. Nedic and A. Ozdaglar.  Distributed subgradient methods for multi-agent optimization.  _IEEE Transactions on Automatic Control_ , 54(1):48–61, 2009.
  * Nedich et al. [2018] Angelia Nedich, Alex Olshevsky, and Michael G. Rabbat.  Network topology and communication-computation tradeoffs in decentralized optimization.  _Proceedings of the IEEE_ , 106(5):953–976, May 2018.
  * Niculescu [2001] Silviu-Iulian Niculescu.  _Delay effects on stability: a robust control approach_ , volume 269\.  Springer Science & Business Media, 2001.
  * Phat and Niamsup [2006] Vu N. Phat and Piyapong Niamsup.  Stability of linear time-varying delay systems and applications to control problems.  _Journal of Computational and Applied Mathematics_ , 194(2):343–356, 2006.
  * R. Bellman [1965] K. L. Cooke R. Bellman.  Differential-difference equations.  _Journal of Applied Mathematics and Mechanics_ , 45(6):448–448, 1965.
  * Recht et al. [2011] Benjamin Recht, Christopher Re, Stephen Wright, and Feng Niu.  Hogwild!: A lock-free approach to parallelizing stochastic gradient descent.  In _Advances in Neural Information Processing Systems_ , volume 24. Curran Associates, Inc., 2011.
  * Rump [1997] S.M. Rump.  Theorems of perron-frobenius type for matrices without sign restrictions.  _Linear Algebra and its Applications_ , 266:1–42, 1997\.
  * Scaman et al. [2017] 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 _International Conference on Machine Learning_ , volume 70, pages 3027–3036. PMLR, 2017.
  * Scaman et al. [2019] Kevin Scaman, Francis Bach, Sébastien Bubeck, Yin Lee, and Laurent Massoulié.  Optimal convergence rates for convex distributed optimization in networks.  _Journal of Machine Learning Research_ , 20:1–31, 2019\.
  * Shi et al. [2015] Wei Shi, Qing Ling, Gang Wu, and Wotao Yin.  EXTRA: An exact first-order algorithm for decentralized consensus optimization.  _SIAM Journal on Optimization_ , 25(2):944–966, 2015.
  * Sirb and Ye [2018] Benjamin Sirb and Xiaojing Ye.  Decentralized consensus algorithm with delayed and stochastic gradients.  _SIAM Journal on Optimization_ , 28(2):1232–1254, 2018.
  * Stich and Karimireddy [2019] Sebastian U. Stich and Sai Praneeth Karimireddy.  The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication.  _arXiv_ , 2019.
  * Sun et al. [2017] Tao Sun, Robert Hannah, and Wotao Yin.  Asynchronous coordinate descent under more realistic assumption.  In _Proceedings of the 31st International Conference on Neural Information Processing Systems_ , NIPS’17, page 6183–6191, 2017.
  * Tian et al. [2020] Ye Tian, Ying Sun, and Gesualdo Scutari.  Achieving linear convergence in distributed asynchronous multiagent optimization.  _IEEE Transactions on Automatic Control_ , 65(12):5264–5279, 2020.  doi: 10.1109/TAC.2020.2977940.
  * Uribe et al. [2020] César A Uribe, Soomin Lee, Alexander Gasnikov, and Angelia Nedić.  A dual approach for optimal algorithms in distributed optimization over networks.  In _2020 Information Theory and Applications Workshop (ITA)_ , pages 1–37. IEEE, 2020.
  * Wang et al. [2015] Huiwei Wang, Xiaofeng Liao, Tingwen Huang, and Chaojie Li.  Cooperative distributed optimization in multiagent networks with delays.  _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , 45(2):363–369, 2015.  doi: 10.1109/TSMC.2014.2332306.
  * Wang et al. [2019] Jianyu Wang, Anit Kumar Sahu, Zhouyi Yang, Gauri Joshi, and Soummya Kar.  Matcha: Speeding up decentralized sgd via matching decomposition sampling.  In _2019 Sixth Indian Control Conference (ICC)_ , pages 299–300, 2019\.  doi: 10.1109/ICC47138.2019.9123209.
  * Wu et al. [2018] Tianyu Wu, Kun Yuan, Qing Ling, Wotao Yin, and Ali H. Sayed.  Decentralized consensus optimization with asynchrony and delays.  _IEEE Transactions on Signal and Information Processing over Networks_ , 4(2):293–307, 2018.  doi: 10.1109/TSIPN.2017.2695121.
  * Xi et al. [2018] Chenguang Xi, Van Sy Mai, Ran Xin, Eyad H. Abed, and Usman A. Khan.  Linear convergence in optimization over directed graphs with row-stochastic matrices.  _IEEE Transactions on Automatic Control_ , 63(10):3558–3565, 2018.
  * Xu et al. [2020] Jinming Xu, Ye Tian, Ying Sun, and Gesualdo Scutari.  Accelerated primal-dual algorithms for distributed smooth convex optimization over networks.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2381–2391. PMLR, 2020.
  * Ying et al. [2021] Bicheng Ying, Kun Yuan, Yiming Chen, Hanbin Hu, Pan Pan, and Wotao Yin.  Exponential graph is provably efficient for decentralized deep training.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.
  * Zhou et al. [2018] Zhengyuan Zhou, Panayotis Mertikopoulos, Nicholas Bambos, Peter Glynn, Yinyu Ye, Li-Jia Li, and Li Fei-Fei.  Distributed asynchronous optimization with unbounded delays: How slow can you go?  In Jennifer Dy and Andreas Krause, editors, _International Conference on Machine Learning_ , volume 80, pages 5970–5979. PMLR, 2018.