# Asynchronous Distributed Optimization with Delay-free Parameters

Xuyang Wu, Changxin Liu, Sindri Magnússon, and Mikael Johansson X. Wu, C. Liu,
and M. Johansson are with the Division of Decision and Control Systems, School
of EECS, KTH Royal Institute of Technology, SE-100 44 Stockholm, Sweden.
Email<EMAIL_ADDRESS>Magnússon is with the Department
of Computer and System Science, Stockholm University, SE-164 07 Stockholm,
Sweden. Email<EMAIL_ADDRESS>work was supported by WASP and
the Swedish Research Council (Vetenskapsrådet) under grants 2019-05319 and
2020-03607.

###### Abstract

Existing asynchronous distributed optimization algorithms often use
diminishing step-sizes that cause slow practical convergence, or use fixed
step-sizes that depend on and decrease with an upper bound of the delays. Not
only are such delay bounds hard to obtain in advance, but they also tend to be
large and rarely attained, resulting in unnecessarily slow convergence. This
paper develops asynchronous versions of two distributed algorithms, Prox-DGD
and DGD-ATC, for solving consensus optimization problems over undirected
networks. In contrast to alternatives, our algorithms can converge to the
fixed point set of their synchronous counterparts using step-sizes that are
independent of the delays. We establish convergence guarantees for strongly
and weakly convex problems under both partial and total asynchrony. We also
show that the convergence speed of the two asynchronous methods adapts to the
actual level of asynchrony rather than being constrained by the worst-case.
Numerical experiments demonstrate a strong practical performance of our
asynchronous algorithms.

##  I Introduction

Distributed optimization has attracted much attention in the last decade and
has found applications in diverse areas such as cooperative control, machine
learning, and power systems. The literature on distributed optimization has
primarily focused on synchronous methods that iterate in a serialized manner,
proceeding to the next iteration only after the current one is completed.
Synchronous methods require all nodes to maintain a consistent view of the
optimization variables without any information delay. This makes the
algorithms easier to analyze, but more difficult to realize. Global
synchronization through a network can be challenging in practice.
Additionally, synchronized updates are inefficient and unreliable since the
time taken per iteration is determined by the slowest node and the
optimization process is vulnerable to single-node failures.

Asynchronous distributed methods that do not require synchronization between
nodes are often better suited for practical implementation [1, 2]. However,
asynchronous methods must account for information delays and allow for nodes
to work with inconsistent views of the optimization variables, which makes
them difficult to analyze. Despite the inherent challenges, there have been
notable successes in studying the mathematical properties of asynchronous
optimization algorithms. One focus area has been the asynchronous consensus
optimization algorithms [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]. These include
asynchronous variants of well-established algorithms such as decentralized
gradient descent (DGD), PG-EXTRA, and gradient-tracking-based methods.
Asynchronous distributed algorithms developed for other settings encompass
Asy-FLEXA [13], the asynchronous primal-dual algorithm [14], the asynchronous
dual decomposition [15], the asynchronous coordinate descent method [16, 17,
18], and ADGD [19].

04080120160$0.00$$0.10$$0.20$$0.30$$0.40$delay frequency  Figure 1:
distribution of real delays (30 nodes).

Most of the studies cited above use diminishing step-sizes [5, 6, 7, 8] or
fixed step-sizes that depend on the amount of asynchrony in the system [10,
11, 13, 15, 14, 9, 16, 12]. Diminishing step-sizes are effective in stochastic
optimization, but can result in unnecessarily slow convergence on
deterministic problems. At the same time, asynchronous algorithms that use
fixed step-sizes often determine step-sizes based on an upper bound $\tau$ on
the maximal delay and use step-size selection policies that decrease with
$\tau$, either as $O(\frac{1}{\tau+1})$ [9, 10] or as
$O(\frac{1}{(\tau+1)^{2}})$ [14]. Since the worst-case delay is hard to
estimate before actually running the algorithm, it is difficult to use these
methods in a theoretically justified way. Moreover, even when the maximal
information delay is known, these methods tend to converge slowly since worst-
case delays are often (very) large, while the majority of delays are small. To
demonstrate this dilemma, we have conducted real experiments depicted in Fig.
1111Asynchronous implementation of DGD [20] on a multi-thread computer using
MPI4py [21] for distributed training of a classifier. Each local loss function
is a logistic function defined by $2000$ samples in MNIST [22], all threads
are homogeneous and each serves as a node, and the communication network is a
line graph. We use a global iteration number to index the iterates, which is
increased by one whenever a node updates its local iterate. The delays are
defined as the difference between the current iteration index and the indexes
of the iterates used in the update. All delays are generated by real
interactions between threads rather than any theoretical models., which plots
the delay distribution over $1000$ iterations in a 30-node network. In this
experiment, the maximum delay was $160$, while over $95\%$ delays were smaller
than $40$. Similar phenomena were observed in [4, 18]. For example, [4]
implemented asynchronous SGD on a 40-core CPU and reported maximum and average
delays of $1200$ and $40$, respectively.

The papers [3, 17, 19, 4, 18] show that some asynchronous distributed
algorithms can converge with fixed step-sizes that can be determined without
any information about the level of asynchrony. Compared with the delay-
dependent ones in [10, 11, 13, 15, 14, 9, 16, 12], such delay-free step-sizes
can be safely determined prior to deployment. Moreover, since they do not
guard against the worst-case delay, their convergence tends to governed to the
actual experienced delays and not be hampered by large and rare worst-case
delays. For example, consider an extreme scenario where the algorithm
experiences a large delay $\tau$ in a single iteration, while all remaining
delays are $0$. In such a case, delay-dependent step-sizes will be reduced to
guard against the worst case, and the algorithm will converge slower also in
iterations where there are no delays. Under delay-free step-sizes, on the
other hand, the algorithm will only have slow progress in iterations with
large delays. However, existing research on delay-free step-sizes only
addresses quadratic problems [3, 17] or star networks [19, 4, 18].

This paper studies asynchronous variants of two popular distributed algorithms
for consensus-optimization over undirected networks, proximal decentralized
gradient descent (Prox-DGD) [23] and DGD using the adapt-then-combine
technique (DGD-ATC) [24]. Our contributions include:

  1. 1.

We bound the optimality gap between the fixed-points of the two synchronous
methods under fixed step-sizes and the optimum of the consensus optimization
problem. Our results on Prox-DGD are more comprehensive than the current
literature, and those on DGD-ATC were absent.

  2. 2.

We show theoretically that, i) with strongly convex objective functions under
total asynchrony, and ii) with convex objective functions and under partial
asynchrony, the proposed methods can use _fixed step-sizes that are set
without any information about the delays_ , and still converge to fixed-points
of their synchronous counterparts.

  3. 3.

By assuming both partial asynchrony and strongly convex objective functions,
we improve the convergence guarantee from asymptotic to linear and show that
the convergence can adapt to the actual level of asynchrony, rather than be
determined by the worst-case.

  4. 4.

Our algorithms can handle non-quadratic objective functions and general
undirected networks, while existing methods with fixed delay-free step-sizes
[3, 17, 4] require quadratic objective functions or star networks.

  5. 5.

Our algorithms are guaranteed to converge under total asynchrony while those
using delay-dependent fixed step-sizes [10, 9, 11, 12] or diminishing step-
sizes [5, 8, 6, 7] are not.

Many algorithms that use delay-dependent fixed step-sizes [10, 9, 11, 12] or
diminishing step-sizes [5, 8, 6, 7] can converge to the optimal consensus
solution. Our algorithms, on the other hand, suffer from an unfavourable
inexact convergence inherited from their synchronous counterparts. However,
they admit delay-free step-sizes that are easy to tune and may yield faster
practical convergence as shown by our numerical experiments.

A preliminary conference version can be found in [25]. It studies the
asynchronous DGD and DGD-ATC for solving smooth and strongly convex problems,
does not show any adaptivity of the convergence rates to the actual delays,
and includes no proofs. Compared to [25], this article extends the
asynchronous DGD to the asynchronous Prox-DGD which allows for composite
objective functions, provides convergence results for weakly convex functions,
proves that the convergence rates adapt to the actual levels of asynchrony
rather than the worst-case, and includes all the proofs.

### Paper Organization and Notation

The outline of this paper is as follows: Section II formulates the consensus
optimization problem, revisits the synchronous algorithm Prox-DGD for solving
the problem with composite objective functions, and establishes its optimality
error bound. Section III introduces the asynchronous Prox-DGD and analyses its
convergence. Section IV studies the DGD-ATC variant of DGD for smooth
problems, introduces its asynchronous counterpart, and proves similar
convergence results as for the asynchronous Prox-DGD. Finally, Section V
evaluates the practical performance of the asynchronous algorithms using
numerical experiments and Section VI concludes the paper.

We use $\mathbf{1}_{d}$, $\mathbf{0}_{d\times d}$, and $I_{d}$ to denote the
$d$-dimensional all-one vector, the $d\times d$ all-zero matrix, and the
$d\times d$ identity matrix, respectively. Subscripts are omitted when it is
clear from context. The notation $\otimes$ represents the Kronecker product
and $\mathbb{N}_{0}$ is the set of natural numbers including $0$. For any
symmetric matrix $W\in\mathbb{R}^{n\times n}$, $\lambda_{i}(W)$, $1\leq i\leq
n$ denotes the $i$th largest eigenvalue of $W$, $\operatorname{Null}(W)$ is
its null space, and $W\succ\mathbf{0}$ means that $W$ is positive definite.
For any vector $x\in\mathbb{R}^{n}$, we use $\|x\|$ to represent the
$\ell_{2}$ norm and define $\|x\|_{W}=\sqrt{x^{T}Wx}$ for any positive
definite matrix $W\in\mathbb{R}^{n\times n}$. For any function
$f:\mathbb{R}^{d}\rightarrow\mathbb{R}\cup\\{+\infty\\}$, we define

$\operatorname{prox}_{f}(x)=\operatorname{\arg\;\min}_{y}f(y)+\frac{1}{2}\|y-x\|^{2}.$

For any differentiable function $f:\mathbb{R}^{d}\rightarrow\mathbb{R}$, we
say that it is $L$-smooth for some $L>0$ if

$\|\nabla f(y)-\nabla f(x)\|\leq L\|y-x\|,~{}\forall x,y\in\mathbb{R}^{d}$

and it is $\mu$-strongly convex for some $\mu>0$ if

$\langle\nabla f(y)-\nabla f(x),y-x\rangle\geq\mu\|y-x\|^{2},~{}\forall
x,y\in\mathbb{R}^{d}.$

##  II Problem Formulation and Prox-DGD

This section formulates the consensus optimization problem, revisits the
synchronous proximal distributed gradient descent (Prox-DGD) [23] for solving
it, and derives bounds on the optimality error of the fixed points of Prox-
DGD.

###  II-A Consensus Optimization

Consider a network of $n$ nodes described by an undirected, connected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\\{1,\ldots,n\\}$
is the vertex set and $\mathcal{E}\subseteq\mathcal{V}\times\mathcal{V}$ is
the edge set. In the network, each node $i$ observes local cost functions
$f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ and
$h_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}\cup\\{+\infty\\}$, and can only
interact with its neighbors in
$\mathcal{N}_{i}=\\{j:\\{i,j\\}\in\mathcal{E}\\}$. Consensus optimization aims
to find a common decision vector that minimizes

$\begin{split}\underset{x\in\mathbb{R}^{d}}{\operatorname{minimize}}~{}&\sum_{i\in\mathcal{V}}f_{i}(x)+h_{i}(x),\end{split}$
(1)

where popular choices of $h_{i}$ include $\ell_{1}$-norm and indicator
function of a convex set. Problem (1) describes many engineering problems in
control and machine learning for networked systems, including distributed
model predictive control [26], empirical risk minimization [27], etc.

Distributed algorithms for solving problem (1) include the distributed
subgradient method [28], Prox-DGD [23], distributed gradient-tracking-based
algorithm [29], distributed dual averaging[30], and PG-EXTRA [31]. While these
algorithms were originally designed to be executed synchronously, they have
been extended to allow for asynchronous implementations. However, existing
asynchronous methods for solving (1) often suffer from slow convergence due to
the use of either diminishing step-sizes, or small fixed step-sizes that
depend on a (usually unknown and large) upper bound on all delays.

###  II-B Synchronous Prox-DGD

To present the algorithm in a compact form, let $x_{i}\in\mathbb{R}^{d}$ be a
local copy of $x$ in (1) held by node $i\in\mathcal{V}$, and define

$\displaystyle\mathbf{x}=(x_{1}^{T},\ldots,x_{n}^{T})^{T},~{}~{}f(\mathbf{x})=\sum_{i\in\mathcal{V}}f_{i}(x_{i}),$
$\displaystyle
h(\mathbf{x})=\sum_{i\in\mathcal{V}}h_{i}(x_{i}),~{}~{}F(\mathbf{x})=f(\mathbf{x})+h(\mathbf{x}).$

Also let $\mathbf{W}=W\otimes I_{d}$ where $W$ is an averaging matrix222We say
a matrix $W=(w_{ij})\in\mathbb{R}^{n\times n}$ is an averaging matrix
associated with $\mathcal{G}$ if it is non-negative, symmetric, stochastic,
and satisfies $w_{ij}=0$ if and only if $\\{i,j\\}\notin\mathcal{E}$ and
$i\neq j$. This matrix can be easily formed in a distributed manner, with many
options listed in [32, Section 2.4]. associated with $\mathcal{G}$. We use
$k\in\mathbb{N}_{0}$ as iteration index and $\mathbf{x}^{k}$ as the value of
$\mathbf{x}$ at iteration $k$. Then, the Prox-DGD algorithm progresses
according to the following iteration:

$\mathbf{x}^{k+1}=\operatorname{prox}_{\alpha
h}(\mathbf{W}\mathbf{x}^{k}-\alpha\nabla f(\mathbf{x}^{k})),$ (2)

where the parameter $\alpha>0$ is the step-size.

Prox-DGD can be seen as the proximal gradient descent method for solving the
following penalized problem of (1):

$\underset{\mathbf{x}\in\mathbb{R}^{nd}}{\operatorname{minimize}}~{}f(\mathbf{x})+h(\mathbf{x})+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}.$
(3)

Every fixed point of Prox-DGD is an optimum to (3) and vice versa. As a
result, when studying Prox-DGD, it is natural to assume that the optimal
solution set of (3) is non-empty.

######  Assumption 1.

For any $\alpha>0$, the minimizer of
$F(\mathbf{x})+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}$
exists.

When $F$ is proper, lower semicontinuous, and convex, Assumption 1 can be
guaranteed by coercivity of $F$ [33, Proposition 11.15], i.e.,
$\lim_{\|\mathbf{x}\|\rightarrow+\infty}F(\mathbf{x})=+\infty$, which holds
when $F$ is strongly convex or has a bounded domain. However, even if the
coercivity condition fails to hold, the minimizer may still exist for many
practical problems. For example, if each
$f_{i}(x_{i})=\|A_{i}x_{i}-b_{i}\|^{2}$ and $h_{i}\equiv 0$, then even if
$A_{i}$ does not have full row rank so that $F$ is not coercive, the minimizer
of $F(\mathbf{x})+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}$
still exists (proof in Appendix -A).

###  II-C Optimality of the Fixed Points of Prox-DGD

The fixed points of Prox-DGD, or equivalently, the optimal solutions of
problem (3), are generally not optimal to (1). This subsection bounds the
error of the fixed points of Prox-DGD relative to the optimizers of (1) under
proper assumptions.

We first impose the assumption below.

######  Assumption 2.

Each $f_{i}$ and $h_{i}$ are proper, closed, and convex, and each $f_{i}$ is
$L_{i}$-smooth for some $L_{i}>0$. Moreover, each $f_{i}+h_{i}$ is bounded
from the below and problem (1) has a non-empty optimal solution set.

Under Assumption 2, we introduce our first optimality gap result. To this end,
let $F_{\operatorname{opt}}$ be the optimal value of (1).

######  Lemma 1.

Suppose that Assumptions 1–2 hold. For any fixed point $\mathbf{x}^{\star}$ of
Prox-DGD, it holds that $F(\mathbf{x}^{\star})\leq F_{\operatorname{opt}}$ and

$\|x_{i}^{\star}-\bar{x}^{\star}\|\leq
O\left(\sqrt{\frac{\alpha}{1-\beta}}\right),\quad\forall i\in\mathcal{V},$ (4)

where $\bar{x}^{\star}=\frac{1}{n}\sum_{i\in\mathcal{V}}x_{i}^{\star}$ and
$\beta=\max\\{|\lambda_{2}(W)|,|\lambda_{n}(W)|\\}\in[0,1)$.

###### Proof.

See Appendix -B. ∎

The above error bound can be improved under additional assumptions. We first
consider the general case where the nonsmooth functions may be different.

######  Assumption 3 (non-identical $h_{i}$’s).

One of the following statements is true:

  1. i)

each $f_{i}+h_{i}$ is Lipschitz continuous;

  2. ii)

each $\operatorname{dom}h_{i}=\mathbb{R}^{d}$ and $f_{i}+h_{i}$ is coercive.

If all the non-smooth functions are identical, then even if Assumption 3 fails
to hold, we are still able to improve the bound in Lemma 1 under the following
assumption.

######  Assumption 4 (identical $h_{i}$’s).

All the $h_{i}$’s are identical, and either of the following holds:

  1. i)

each $f_{i}$ and $h_{i}$ are bounded from the below;

  2. ii)

each $f_{i}$ is Lipschitz continuous;

  3. iii)

each $f_{i}+h_{i}$ is coercive.

######  Lemma 2.

Suppose that Assumptions 1–2 hold. For any fixed point $\mathbf{x}^{\star}$ of
Prox-DGD,

  1. 1.

Under Assumption 3,

$\|x_{i}^{\star}-\bar{x}^{\star}\|\leq O\left(\frac{\alpha}{1-\beta}\right);$
(5)

  2. 2.

Under Assumption 4, (5) holds and

$\begin{split}F(\bar{\mathbf{x}}^{\star})&\leq
F_{\operatorname{opt}}+O\left(\frac{\alpha}{1-\beta}+\frac{L\alpha^{2}}{2(1-\beta)^{2}}\right),\end{split}$
(6)

where $\bar{\mathbf{x}}^{\star}=\mathbf{1}_{n}\otimes\bar{x}^{\star}$ and
$L=\max_{i\in\mathcal{V}}L_{i}$.

###### Proof.

See Appendix -C. ∎

Lemma 2 extends and generalizes several results from the literature. For
example, [20, 23] considered the special case that all $f_{i}$’s are smooth
and no regularizers are present ($h_{i}\equiv 0$), and reference [34] studied
a set-up where all $f_{i}$’s are smooth and the $h_{i}$’s are all equal and
encode a projection onto the same set $X$. Our results, on the other hand,
allow for general and non-identical $h_{i}$’s. We also provide an optimality
gap (4) in Lemma 1 that can be applied to more general problems without
requiring Assumptions 3 or 4. This allows us to study a broader range of
problems, such as problem (1) where the $f_{i}$ functions are smooth, and the
$h_{i}$ functions encode projections onto distinct, convex, and compact sets.
An optimality gap of the same order as (4) is provided in [35], which allows
distinct $h_{i}$’s but requires strong convexity of $f_{i}$’s.

##  III Asynchronous Prox-DGD

In this section, we introduce the asynchronous Prox-DGD and analyze its
convergence. The algorithm is fully asynchronous in the sense that it requires
neither global synchronization between nodes nor access to a global clock.

###  III-A Algorithm Description

In the asynchronous Prox-DGD algorithm, each node is activated at discrete
points in time. When node $i\in{\mathcal{V}}$ is activated, it updates its
local iterate $x_{i}\in{\mathbb{R}}^{d}$ and shares it with its neighbors
$j\in{\mathcal{N}}_{i}$ before going back to sleep. A node does not need to be
active to receive information from its neighbors. Instead, each node $i$ uses
a buffer ${\mathcal{B}}_{i}$ to store the information it receives from its
neighbors between activation times. When node $i$ is activated, it reads all
$x_{ij}$ (the most recent $x_{j}$ it has received from neighboring node $j$)
from the buffer, performs the local update

$x_{i}\leftarrow\operatorname{prox}_{\alpha
h_{i}}\biggl{(}w_{ii}x_{i}+\sum_{j\in\mathcal{N}_{i}}w_{ij}x_{ij}-\alpha\nabla
f_{i}(x_{i})\biggr{)},$ (7)

and broadcasts the new $x_{i}$ to all its neighbors. Once a node
$j\in\mathcal{N}_{i}$ receives this new $x_{i}$, it stores $x_{i}$ in its
buffer $\mathcal{B}_{j}$. A detailed implementation is given in Algorithm 1.

To describe the asynchronous Prox-DGD mathematically, we index the iterates by
$k\in\mathbb{N}_{0}$. The index is increased by $1$ whenever an update is
performed on any local variable $x_{i}$ by any node $i\in\mathcal{V}$, and
does not need to be known by the nodes – $k$ is only introduced to order
events in our theoretical analysis. With this indexing, each $x_{ij}$ in (7)
is simply a delayed version of $x_{j}$ and the execution of (7) can be written
as

$x_{i}^{k+1}\\!=\\!\begin{cases}\operatorname{prox}_{\alpha
h_{i}}\bigl{(}\sum_{j\in\bar{\mathcal{N}_{i}}}w_{ij}x_{j}^{s_{ij}^{k}}\\!-\alpha\nabla
f_{i}(x_{i}^{k})\bigr{)},&k\in\mathcal{K}_{i},\\\
x_{i}^{k},&\text{otherwise}.\end{cases}$ (8)

where $\mathcal{K}_{i}\subseteq\mathbb{N}_{0}$ is the set of iterations in
which node $i$ is active, $\bar{\mathcal{N}}_{i}=\mathcal{N}_{i}\cup\\{i\\}$,
$s_{ij}^{k}\in[0,k]$ is the index when the most recent version of $x_{j}$
available to node $i$ at iteration $k$ was computed, and $s_{ii}^{k}=k$. Note
that if $\mathcal{K}_{i}=\mathbb{N}_{0}$ $\forall i\in\mathcal{V}$ and
$s_{ij}^{k}=k$ $\forall\\{i,j\\}\in\mathcal{E},\forall k\in\mathbb{N}_{0}$,
then (8) reduces to the synchronous Prox-DGD iteration (2).

Algorithm 1 Asynchronous Prox-DGD

1: Initialization: All the nodes agree on $\alpha>0$, and cooperatively set
$w_{ij}$ $\forall\\{i,j\\}\in\mathcal{E}$.

2: Each node $i\in\mathcal{V}$ chooses $x_{i}\in\mathbb{R}^{d}$, creates a
local buffer $\mathcal{B}_{i}$, and shares $x_{i}$ with all neighbors in
$\mathcal{N}_{i}$.

3: for each node $i\in\mathcal{V}$ do

4: keep _receiving $x_{j}$ from neighbors and store $x_{j}$ in
$\mathcal{B}_{i}$ until activation_333In the first iteration, each node
$i\in\mathcal{V}$ can be activated only after it received $x_{j}$ from all
$j\in\mathcal{N}_{i}$.. If for some $j\in\mathcal{N}_{i}$, node $i$ receives
multiple $x_{j}$’s, then store the most recently received one.

5: set $x_{ij}=x_{j}$ for all $x_{j}\in\mathcal{B}_{i}$.

6: empty $\mathcal{B}_{i}$.

7: update $x_{i}$ according to (7).

8: send $x_{i}$ to all neighbors $j\in\mathcal{N}_{i}$.

9: Until a termination criterion is met.

###  III-B Convergence Analysis

In this section, we analyse the convergence of the asynchronous Prox-DGD under
two typical models of asynchrony and show that the convergence can adapt to
real delays rather than be determined by the worst-case delay. A key
difference with the literature is that our results are established under a
condition on the step-size $\alpha$ that does not depend on any information
about the delays. We refer to this type of condition as a _delay-free_ step-
size condition. Our first result allows for total asynchrony in the sense of
Bertsekas and Tsitsiklis [36], _i.e._ the information delays $k-s_{ij}^{k}$
may grow arbitrarily large but no node can cease to update and old information
must eventually be purged from the system.

######  Assumption 5 (total asynchrony).

The following holds:

  1. 1.

$\mathcal{K}_{i}$ is an infinite subset of $\mathbb{N}_{0}$ for each
$i\in\mathcal{V}$.

  2. 2.

$\lim_{k\rightarrow+\infty}s_{ij}^{k}=+\infty$ for any $i\in\mathcal{V}$ and
$j\in\mathcal{N}_{i}$.

This assumption is well-suited for scenarios where communication and
computation delays are unpredictable, e.g., in massively parallel computing
grids with heterogeneous computing nodes where delays can quickly add up if a
node is saturated [37]. Under total asynchrony, even the asynchronous
consensus method [3], which is equivalent to the asynchronous Prox-DGD for
solving problem (1) with $f_{i}=h_{i}\equiv 0$, cannot be guaranteed to
converge [36, Example 7.1.1.2]. Therefore, to establish convergence of the
asynchronous Prox-DGD under total asynchrony, we assume all $f_{i}$’s to be
strongly convex.

######  Assumption 6.

Each $f_{i}$ is $\mu_{i}$-strongly convex.

Clearly, Assumptions 2 and 6 imply Assumption 1. In the following theorem, we
show that in contrast to the literature [10, 11, 13, 15, 14, 9, 16, 12] in
which the parameters depend on the delay, the asynchronous Prox-DGD can
converge to the same fixed point set as its synchronous counterpart, even
under the total asynchrony assumption and a _delay-free_ step-size condition.

######  Theorem 1 (total asynchrony).

Suppose that Assumptions 2, 5, 6 hold and

$\alpha\in\left(0,2\min_{i\in\mathcal{V}}\frac{w_{ii}}{L_{i}}\right).$ (9)

Then, $\\{\mathbf{x}^{k}\\}$ generated by the asynchronous Prox-DGD converges
to a fixed point of the synchronous Prox-DGD.

###### Proof.

See Appendix -D. ∎

Under total asynchrony, there is no lower bound on the update frequency of
nodes and no upper bound on the delays, and we are only able to give
asymptotic convergence guarantees and handle strongly convex objective
functions. To derive non-asymptotic convergence rates and handle weakly convex
objective functions, we assume the more restrictive notion of partial
asynchrony [36].

######  Assumption 7 (partial asynchrony).

There exist non-negative integers $B$ and $D$ such that

  1. 1.

For every $i\in\mathcal{V}$ and for every $k\in\mathbb{N}_{0}$, at least one
element in the set $\\{k,\ldots,k+B\\}$ belongs to $\mathcal{K}_{i}$.

  2. 2.

There holds

$k-D\leq s_{ij}^{k}\leq k$

for all $i\in\mathcal{V}$, $j\in\mathcal{N}_{i}$, and $k\in\mathcal{K}_{i}$.

In Assumption 7, $B$ and $D$ characterize the minimum update frequency and the
maximal information delay, respectively. If $B=D=0$, then Assumption 7 reduces
to the synchronous scheme where all local variables $x_{i}^{k}$ $\forall
i\in\mathcal{V}$ are instantaneously updated at every iteration
$k\in\mathbb{N}_{0}$ and there are no information delays. Moreover, it is
worth noting that different from the bounded transmission delay assumption in
[5, 9, 8] that does not allow for packet loss, both Assumptions 5, 7 allow for
packet losses. Specifically, packets can be classified as “successfully
transmitted” and “lost or transmitting”, and Assumptions 5, 7 only pose
restrictions on the delay of the “successfully transmitted” packets.

To state our convergence result, we define the block-wise maximum norm for any
$\mathbf{x}=(x_{1}^{T},\ldots,x_{n}^{T})^{T}\in\mathbb{R}^{nd}$ as

$\|\mathbf{x}\|_{\infty}^{b}=\max_{i\in\mathcal{V}}\|x_{i}\|.$

The following theorem establishes asymptotic convergence of the asynchronous
Prox-DGD for weakly convex objective functions under partial asynchrony, and
improves the rate to linear when the objective functions are strongly convex.

######  Theorem 2 (partial asynchrony).

Suppose that Assumptions 1, 2, 7 and the step-size condition (9) hold. Then,
$\\{\mathbf{x}^{k}\\}$ generated by the asynchronous Prox-DGD converges to a
fixed point $\mathbf{x}^{\star}$ of its synchronous counterpart.

If, in addition, Assumption 6 holds, then

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\rho^{\lfloor
k/(B+D+1)\rfloor}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b},$

where

$\displaystyle\rho=\sqrt{1-\alpha\min_{i\in\mathcal{V}}\left(\mu_{i}\left(2-\frac{\alpha
L_{i}}{w_{ii}}\right)\right)}.$ (10)

###### Proof.

See Appendix -E. ∎

By Lemmas 1–2 and Theorems 1–2, the asynchronous Prox-DGD can converge to an
approximate optimum of problem (1), where the optimality gap is given in
Lemmas 1–2. Note that the step-size range (9) is independent of the level of
asynchrony in the system. Moreover, the convergence guarantees that we can
give improve as the amount of asynchrony decreases from total to partial
asynchrony.

####  III-B1 Comparison with related methods

To appreciate the novelties of the asynchronous Prox-DGD, we categorize the
literature [3, 5, 6, 8, 9, 10, 11, 7, 17, 4, 12] on asynchronous consensus
optimization according to their step-sizes:

_Diminishing step-size_ : References [5, 6, 8, 7] consider diminishing step-
sizes that decrease to zero as the number of iterations increases to infinity.
The step-sizes are delay-free, but decrease rapidly and can often lead to slow
practical convergence, especially for deterministic optimization problems.

_Delay-dependent fixed step-size_ : This line of work includes [10, 11, 9,
12]. They assume the existence of a known upper bound on the information delay
and use fixed parameters that rely on (and decrease with) the delay bound.
These step-sizes are difficult to use because the delay bound is usually
unknown in practice. Moreover, in many systems, the worst-case delay is large
but rarely attained, so step-sizes tuned in this way are unnecessarily small
and lead to slow convergence.

_Delay-free fixed step-size_ : This category includes [3, 17, 4]. The step-
sizes are easier to determine and are typically larger than the delay-
dependent ones, leading to a faster practical convergence compared to the
other two types of step-sizes. However, existing works in this category can
only handle quadratic problems [3, 17] or star networks [4].

Our step-size (9) belongs to the last category, and has several novelties with
respect to the state-of-the art.

  1. 1.

Existing works using delay-free fixed step-sizes can only handle quadratic
problems [3, 17] or star networks [4]. In contrast, Algorithm 1 can deal with
both non-quadratic objective functions and non-star communication networks
(Theorems 1–2), which is a substantial improvement.

  2. 2.

Only Algorithm 1 and the algorithm in [10] can address weakly convex, non-
quadratic objective functions and non-identical local constraints over non-
star networks. However, [10] uses a probabilistic model to characterize the
node that updates at each iteration, which is easier to analyse but less
practical than partial asynchrony.

  3. 3.

Although [5, 6, 8, 9, 10, 11, 7, 12] can converge to the exact optimum, while
Algorithm 1 only converges to an approximate minimum, the parameter range of
Algorithm 1 is wider which typically leads to faster practical convergence.

Admittedly, the algorithms in [3, 11, 5, 7, 8, 9] can handle directed
networks, which is more general than the undirected network model in our work.

###  III-C Adaptivity to the Realized Level of Asynchrony

As shown in Fig. 1, the typical delays in real systems may be (and often are)
much smaller than the worst-case. In these scenarios, the convergence of
asynchronous methods whose parameters depend on the worst-case delay may be
slowed down significantly (See Fig. 1 in [18]). In this subsection, we will
show that the convergence of the asynchronous Prox-DGD adapts to the actual
level of asynchrony rather than being hampered by the worst-case delay. To
this end, define

$t_{i}^{k}=\max\\{\ell:\ell\leq k,\ell\in\mathcal{K}_{i}\\}$ (11)

as the iteration of the most recent update of node $i$, so that

$x_{i}^{k+1}=\operatorname{prox}_{\alpha
h_{i}}\left(\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}x_{j}^{s_{ij}^{t_{i}^{k}}}-\alpha\nabla
f_{i}(x_{i}^{t_{i}^{k}})\right)$ (12)

holds for all $i\in\mathcal{V}$. The maximum age of the information used to
obtain each block of $\mathbf{x}^{k+1}$ is then

$\tau^{k}=k-\min_{i\in\mathcal{V}}\min_{j\in\bar{\mathcal{N}}_{i}}s_{ij}^{t_{i}^{k}}.$
(13)

We also define a sequence $\\{k^{m}\\}_{m\in\mathbb{N}_{0}}$ as: $k^{0}=0$ and

$k^{m+1}=\min\\{k:t-\tau^{t}\geq k^{m}~{}\forall t\geq k\\}+1,\forall
m\in\mathbb{N}_{0},$ (14)

which describes the following Markov property: for any $m\in\mathbb{N}_{0}$,
when $k+1\geq k^{m+1}$, the computation of $\mathbf{x}^{k+1}$ using (12) does
not depend on any $\mathbf{x}^{\ell}$ with $\ell<k^{m}$ (since $k-\tau^{k}\geq
k^{m}$).

######  Theorem 3 (delay adaptivity).

Suppose that Assumptions 2, 6, and the step-size condition (9) hold. Let
$\\{\mathbf{x}^{k}\\}$ be generated by the asynchronous Prox-DGD. If $k\geq
k^{m}$, then

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\rho^{m}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b},$

where $\rho$ is given in (10).

###### Proof.

See Appendix -F. ∎

By Theorem 3, the convergence speed of the asynchronous Prox-DGD is determined
by $m^{k}=\max\\{m:k^{m}\leq k\\}$. Under Assumption 7, [38] shows that
$\tau^{k}\leq B+D$ $\forall k\in\mathbb{N}_{0}$ so by the definition of
$\\{k^{m}\\}$, we have $k^{m}\leq m(B+D+1)$. Therefore,

$m^{k}\geq\left\lfloor\frac{k}{B+D+1}\right\rfloor,~{}\forall
k\in\mathbb{N}_{0},$ (15)

which recovers the guarantees in Theorem 2. However, $m^{k}$ may be much
larger than the lower bound (15), especially if the typical level of
asynchrony is much smaller than the worst case, indicating a faster
convergence. To make the discussion more precise, we consider two extreme
cases.

  * •

At one extreme is a scenario where the worst-case bounds $B$ and $D$ are
attained only once, and the algorithm runs cyclically without information
delays afterward. Then,

$m^{k}\geq\frac{k-(B+D+1)}{n},\forall k\in\mathbb{N}_{0}.$ (16)

  * •

At the other extreme are scenarios where (15) hold with equality. This
happens, for example, in a system where for every $t\in\mathbb{N}_{0}$, if a
node updates at the $t(B+D+1)$th iteration, its last update is delayed by $D$
and occurs at the $t(B+D+1)-B$th iteration.

By (16), the quantity $m^{k}$ under the most favorable delays is determined by
$n$ rather than $B$ and $D$ and is much larger than that of the worst-case
(15). In practice, the convergence will be somewhere in between these two
extremes. To illustrate this, we run the asynchronous Prox-DGD for $10,000$
iterations in a similar setting as we used for recording the delays shown in
Fig. 1. Specifically, we used $n=10$ and recorded $B=37$ and $D=40$ during the
execution. In Fig. 2, we plot the realized $\\{m^{k}\\}$ (“simu”) with those
obtained under the “best” and “worst” partial asynchronous realizations
defined above. We see that the actual $m^{k}$ values lie between the two
theoretical extremes and are roughly triple those of the “worst” model.

Figure 2: Adaptivity to delays

##  IV Asynchronous DGD-ATC for Smooth Problems

DGD-ATC [24] is a variant of DGD [20] using the adapt-then-combine technique.
It solves problem (1) with $h_{i}\equiv 0$ $\forall i\in\mathcal{V}$ through
the updates

$\mathbf{x}^{k+1}=\mathbf{W}(\mathbf{x}^{k}-\alpha\nabla f(\mathbf{x}^{k})),$
(17)

where $\mathbf{W}$ is the same as in (2) and $\alpha>0$ is the step-size. We
also require $W$ to be positive definite, which can be achieved by letting
$W=(W^{\prime}+I)/2$ for any averaging matrix
$W^{\prime}\in\mathbb{R}^{n\times n}$ associated with $\mathcal{G}$ [32,
section 2.3]. In this section, we will show that similar to the asynchronous
Prox-DGD, the asynchronous DGD-ATC can also converge under a delay-free step-
size condition and has an even faster convergence when handling smooth
problems, which will be demonstrated theoretically later and numerically in
Section V.

We are unaware of any previous work that analyses the convergence of DGD-ATC
with fixed step-sizes. In the lemma below, we show that under Assumption 2,
DGD-ATC admits at least one fixed-point, and the optimality gap is similar to
that of the asynchronous Prox-DGD in Lemma 2.

######  Lemma 3.

Suppose that Assumption 2 holds, $h_{i}\equiv 0$ $\forall i\in\mathcal{V}$,
and the optimal set of problem (1) is bounded. Then the fixed point set of
DGD-ATC (17) is non-empty and for any fixed point
$\mathbf{x}^{\star}\in\mathbb{R}^{nd}$, $F(\mathbf{x}^{\star})\leq
F_{\operatorname{opt}}$ and (5)–(6) hold.

###### Proof.

See Appendix -G. ∎

###  IV-A Algorithm Description

The asynchronous DGD-ATC algorithm can be implemented in a similar setting as
Algorithm 1 – each node $i\in{\mathcal{V}}$ is activated at discrete points in
time, does not need to be active to receive information from its neighbors,
and uses a buffer ${\mathcal{B}}_{i}$ to store the information it receives
from its neighbors between activation times. In the initialization, it shares
$y_{i}=x_{i}-\alpha\nabla f_{i}(x_{i})$ with all neighbors. When it is
activated, it reads all $y_{ij}$ (the most recent $y_{j}$ it has received from
neighboring node $j$) from the buffer, performs the update

$x_{i}\leftarrow w_{ii}y_{i}+\sum_{j\in\mathcal{N}_{i}}w_{ij}y_{ij},$ (18)

and broadcasts $y_{i}=x_{i}-\alpha\nabla f_{i}(x_{i})$ to all
$j\in\mathcal{N}_{i}$ before going back to sleep. Once a node
$j\in\mathcal{N}_{i}$ receives $y_{i}$, it stores $y_{i}$ in its buffer
$\mathcal{B}_{j}$; see the detailed implementation in Algorithm 2.

Algorithm 2 Asynchronous DGD-ATC

1: Initialization: All the nodes agree on $\alpha>0$, and cooperatively set
$w_{ij}$ $\forall\\{i,j\\}\in\mathcal{E}$.

2: Each node $i\in\mathcal{V}$ chooses $x_{i}\in\mathbb{R}^{d}$, creates a
local buffer $\mathcal{B}_{i}$, sets $y_{i}=x_{i}-\alpha\nabla f_{i}(x_{i})$
and shares it with all $j\in\mathcal{N}_{i}$.

3: for each node $i\in\mathcal{V}$ do

4: keep _receiving $y_{j}$ from neighbors and store $y_{j}$ in
$\mathcal{B}_{i}$ until it is activated_444In the first iteration, each node
$i\in\mathcal{V}$ can be activated only after it received $y_{j}$ from all
$j\in\mathcal{N}_{i}$.. If for some $j\in\mathcal{N}_{i}$, node $i$ receives
multiple $y_{j}$’s, then store the most recently received one.

5: set $y_{ij}=y_{j}$ for all $y_{j}\in\mathcal{B}_{i}$.

6: empty $\mathcal{B}_{i}$.

7: update $x_{i}$ by (18).

8: set $y_{i}=x_{i}-\alpha\nabla f_{i}(x_{i})$.

9: share $y_{i}$ with all neighbors $j\in\mathcal{N}_{i}$.

10: Until a termination criterion is met.

Note that each $y_{ij}$ in (18) is a delayed $x_{j}-\alpha\nabla
f_{j}(x_{j})$. Then, similar to (8), the asynchronous DGD-ATC can be described
as follows. For each $i\in\mathcal{V}$ and $k\in\mathbb{N}_{0}$,

$x_{i}^{k+1}\\!\\!=\\!\begin{cases}\sum_{j\in\bar{\mathcal{N}_{i}}}w_{ij}(x_{j}^{s_{ij}^{k}}\\!-\\!\alpha\nabla
f_{j}(x_{j}^{s_{ij}^{k}})),&k\in\mathcal{K}_{i},\\\
x_{i}^{k},&\\!\text{otherwise},\end{cases}$ (19)

where $k\in\mathbb{N}_{0}$ is the iteration index,
$\mathcal{K}_{i}\subseteq\mathbb{N}_{0}$ denotes the set of iterations where
node $i$ updates $x_{i}$, $s_{ij}^{k}\in[0,k]$, $j\in\mathcal{N}_{i}$ is the
iteration index of the most recent $y_{j}$ that node $i$ has received from
$j$, and $s_{ii}^{k}=k$. When $\mathcal{K}_{i}=\mathbb{N}_{0}$ $\forall
i\in\mathcal{V}$ and $s_{ij}^{k}=k$ $\forall\\{i,j\\}\in\mathcal{E},\forall
k\in\mathbb{N}_{0}$, the asynchronous DGD-ATC reduces to the synchronous DGD-
ATC.

###  IV-B Convergence Analysis

We show similar convergence results for the asynchronous DGD-ATC as Theorems
1-3.

######  Theorem 4 (total asynchrony).

Suppose that all the conditions in Lemma 3 and Assumptions 5, 6 hold and

$\alpha\in\left(0,\frac{2}{\max_{i\in\mathcal{V}}L_{i}}\right).$ (20)

Then, $\\{\mathbf{x}^{k}\\}$ generated by the asynchronous DGD-ATC converges
to some fixed point of its synchronous counterpart.

###### Proof.

See Appendix -H. ∎

######  Theorem 5 (partial asynchrony).

Suppose that all the conditions in Lemma 3, Assumption 7, and the step-size
condition (20) hold. Then, $\\{\mathbf{x}^{k}\\}$ generated by the
asynchronous DGD-ATC converges to some fixed point $\mathbf{x}^{\star}$ of its
synchronous counterpart. If, in addition, Assumption 6 holds, then

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\hat{\rho}^{\lfloor
k/(B+D+1)\rfloor}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b},$

where

$\displaystyle\hat{\rho}=\sqrt{1-\alpha\min_{i\in\mathcal{V}}\left(\mu_{i}(2-\alpha
L_{i})\right)}\in(0,1).$ (21)

###### Proof.

See Appendix -I. ∎

######  Theorem 6 (delay-adaptivity).

Suppose that all the conditions in Lemma 3, Assumptions 6, 7, and the step-
size condition (20) hold. Let $\\{\mathbf{x}^{k}\\}$ be generated by the
asynchronous DGD-ATC. If $k\geq k^{m}$ for some $m\in\mathbb{N}_{0}$, then

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\hat{\rho}^{m}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b}.$

###### Proof.

See Appendix -J. ∎

Lemma 3 and Theorems 4–6 indicate that the asynchronous DGD-ATC has the same
error bounds as the asynchronous Prox-DGD on smooth problems, but it may
converge faster. Since $w_{ii}\in(0,1)$, the asynchronous DGD-ATC allows for
larger stepsizes (20) than the asynchronous prox-DGD (9). A larger step-size
$\alpha$ tends to lead to faster convergence in practice. Indeed, even when
using the same $\alpha$, asynchronous DGD-ATC has a stronger convergence
guarantee since $w_{ii}\in(0,1)$ implies that $\hat{\rho}\leq\rho$. With the
popular Metropolis averaging matrix [29] where,
$w_{ii}=1-\sum_{j\in\mathcal{N}_{i}}\frac{1}{\max(|\mathcal{N}_{i}|,|\mathcal{N}_{j}|)+1}$,
the advantage of the asynchronous DGD-ATC over Prox-DGD becomes stronger in
denser networks.

The comparison of the asynchronous DGD-ATC with the literature follows that of
the asynchronous Prox-DGD in Section III-B1), with the exception that the
former cannot solve non-smooth problems. We omit the comparison for brevity.

##  V Numerical Experiments

We evaluate the practical performance of the asynchronous Prox-DGD and DGD-ATC
on decentralized training. Each node has its own local data set and
collaborates to train a common classifier using logistic regression with an
elastic-net regularization. This problem is on the form (1) with

$\displaystyle f_{i}(x)$
$\displaystyle=\frac{1}{|\mathcal{D}_{i}|}\sum_{j\in\mathcal{D}_{i}}\left(\log(1+e^{-b_{j}(a_{j}^{T}x)})+\frac{\lambda_{2}}{2}\|x\|^{2}\right),$
$\displaystyle h_{i}(x)$ $\displaystyle=\lambda_{1}\|x\|_{1}.$

where $\mathcal{D}_{i}$ represents the set of samples held by node $i$,
$a_{j}$ is the feature of the $j$th sample, $b_{j}$ is its label, and
$\lambda_{1},\lambda_{2}$ are regularization parameters. We set
$\lambda_{2}=10^{-3}$ and consider two values $10^{-3}$ and $0$ for
$\lambda_{1}$ to simulate non-smooth and smooth problems, respectively. The
experiments use the training sets of Covertype [39] and MNIST [22] summarized
in Table I.

TABLE I: Training data sets. Data set | sample number $N$ | feature dimension $d$
---|---|---
MNIST | 60000 | 784
Covertype | 581012 | 54

We compare our algorithms with their synchronous counterparts and the
asynchronous PG-EXTRA [10]. We do not compare with the algorithms in [5, 6, 7,
8, 12, 9, 11] because they require either Lipschitz continuous objective
functions [5, 6, 7] that does not hold for the simulated problem or negligibly
small step-sizes ($<10^{-5}$ in our setting) [8, 9, 11, 12].

We set $n=16$, partition and allocate the data sets uniformly to each node,
and implement all the methods on a multi-thread computer using the message-
passing framework MPI4py [21] where each thread serves as a node. Different
from experiments in existing work, that use theoretical models of the
computation and communication time [12, 10, 11] or delays [6, 5], the timing
in our experiments are generated from real computations and communications of
the threads. The communication graph $\mathcal{G}$ has $20$ links and is
connected, with a randomly generated topology. Each node $i\in\mathcal{V}$ is
activated once its buffer $\mathcal{B}_{i}$ includes messages from at least
$|\mathcal{N}_{i}|-1$ neighbours. We set
$\alpha=\min_{i\in\mathcal{V}}w_{ii}/\max_{i\in\mathcal{V}}L_{i}$ in the
asynchronous and synchronous Prox-DGD and
$\alpha=1/\max_{i\in\mathcal{V}}L_{i}$ in the asynchronous and synchronous
DGD-ATC, which satisfy the conditions in Theorems 1–2. We fine-tune the
parameters of asynchronous PG-EXTRA within its theoretical ranges for
convergence. The theoretical ranges involve the maximum delay, which is set to
the maximum observed delay during a 10-second run of the method.

(a) MNIST (b) Covertype

Figure 3: Convergence for solving smooth Logistic regression ($\lambda_{1}=0$)

(a) MNIST (b) Covertype

Figure 4: Convergence for solving $\ell_{1}$-regularized Logistic regression
($\lambda_{1}=10^{-3}$) Figure 5: Number of local iterations in asynchronous
and synchronous Prox-DGD

We run all methods for $10$ seconds and plot the training error
$f(\bar{x}(t))-f^{\star}$ at the average iterate
$\bar{x}(t)=\frac{1}{n}\sum_{i=1}^{n}x_{i}(t)$ in Figs. 3–4, where $x_{i}(t)$
is the value of $x_{i}$ at time $t$ and $f^{\star}$ is the optimal value of
(1). From these two figures, we make the following observations. First, when
solving the smooth problem, the asynchronous DGD-ATC outperforms the
asynchronous Prox-DGD on both datasets, which is in agreement with our theory,
as discussed below Theorem 5. Second, in all scenarios, the asynchronous Prox-
DGD converges faster than the asynchronous PG-EXTRA. This is because the
parameters of asynchronous PG-EXTRA are conservative due to the large maximum
delay, while the asynchronous Prox-DGD allows for much more relaxed delay-free
parameters. Third, the asynchronous Prox-DGD and DGD-ATC are comparable with
(for MNIST) or converge faster than (for Covertype) their synchronous
counterparts. This is a big improvement over existing asynchronous methods
with fixed step-sizes since most of them are much slower than their
synchronous counterparts when implemented in practice using the theoretically
justified step-sizes. Fig. 5 plots the numbers of local iterations in the
nodes during a 10-second run of both the asynchronous and synchronous Prox-
DGD, which shows the average number of local iterations in the asynchronous
implementation is around $1.46$ times that in the synchronous implementation.

##  VI Conclusion

We have investigated the asynchronous version of two distributed algorithms,
Prox-DGD and DGD-ATC, for solving consensus optimization problems. We analysed
the optimality gap of the synchronous Prox-DGD and DGD-ATC, and proved that
their asynchronous variants can converge to the fixed point set of the
synchronous counterparts under _delay-free_ parameter conditions. We also show
that the convergence of both asynchronous algorithms adapts to the actual
delays and is not determined by the worst-case delay. Finally, we demonstrated
superior practical convergence of the two asynchronous algorithms in
implementations on a multi-core computer.

###  -A Assumption 1 holds for quadratic $f_{i}$ and zero $h_{i}$

Let $A=\operatorname{diag}(A_{1},\ldots,A_{n})$ and
$b=(b_{1}^{T},\ldots,b_{n}^{T})^{T}$. Because $f_{i}(x)=\|A_{i}x-b_{i}\|^{2}$
and $h_{i}\equiv 0$, we have $F(\mathbf{x})=\|A\mathbf{x}-b\|^{2}$, so that

$F(\mathbf{x})+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}=\|A\mathbf{x}-b\|^{2}+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}.$

Minimizing the above function is equivalent to solving
$(2A^{T}A+(I-\mathbf{W})/\alpha)\mathbf{x}=A^{T}b$, which has a solution if

$A^{T}b\in\operatorname{Range}(2A^{T}A+(I-\mathbf{W})/\alpha).$ (22)

Equation (22) indeed holds and, because
$A^{T}b\in\operatorname{Range}(A^{T}A)$, it can be proved by showing

$\operatorname{Range}(A^{T}A)\subseteq\operatorname{Range}(2A^{T}A+(I-\mathbf{W})/\alpha).$
(23)

Moreover, because the range of a real symmetric matrix is the orthogonal
complement of its null space, (23) is equivalent to

$\operatorname{Null}(2A^{T}A+(I-\mathbf{W})/\alpha)\subseteq\operatorname{Null}(A^{T}A).$
(24)

For any $\mathbf{x}\in\operatorname{Null}(2A^{T}A+(I-\mathbf{W})/\alpha)$,
because $I-\mathbf{W}\succeq\mathbf{0}$,

$\mathbf{x}^{T}A^{T}A\mathbf{x}\leq\mathbf{x}^{T}(2A^{T}A+(I-\mathbf{W})/\alpha)\mathbf{x}=0,$
(25)

which, together with $A^{T}A\succeq\mathbf{0}$, yields
$\mathbf{x}\in\operatorname{Null}(A^{T}A)$ and also (24). Concluding all the
above, the minimizer of
$F(\mathbf{x})+\frac{1}{2\alpha}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}$
exists.

###  -B Proof of Lemma 1

Because $\mathcal{G}$ is connected [29], we have $\beta\in[0,1)$.

Next, we prove a property of $\mathbf{W}$. Because $\mathcal{G}$ is connected
and $\mathbf{W}=W\otimes I_{d}$, we have

$\operatorname{Null}(I-\mathbf{W})=\\{\mathbf{x}\in\mathbb{R}^{nd}:x_{1}=x_{2}=\ldots=x_{n}\\},$
(26)

and because $\lambda_{1}(W)=1$ and $\lambda_{2}(W)\leq\beta<1$, the minimum
non-zero eigenvalue of $I-\mathbf{W}$ is $1-\lambda_{2}(W)\geq 1-\beta>0$.
These, together with the fact that for any $\mathbf{x}\in\mathbb{R}^{nd}$,
$\mathbf{x}-\bar{\mathbf{x}}$, where
$\bar{\mathbf{x}}=\mathbf{1}_{n}\otimes\frac{1}{n}\sum_{i\in\mathcal{V}}x_{i}$,
is the projection of $\mathbf{x}$ onto $\operatorname{Range}(I-\mathbf{W})$,
yields

$\begin{split}\mathbf{x}^{T}(I-\mathbf{W})\mathbf{x}^{T}=&(\mathbf{x}-\bar{\mathbf{x}})^{T}(I-\mathbf{W})(\mathbf{x}-\bar{\mathbf{x}})\allowdisplaybreaks\\\
\geq&(1-\beta)\|\mathbf{x}-\bar{\mathbf{x}}\|^{2}.\end{split}$ (27)

Finally, we use (27) to show (4). Because $\mathbf{x}^{\star}$ is the optimum
of (3), we have

$\begin{split}F(\mathbf{x}^{\star})+\frac{1}{2\alpha}(\mathbf{x}^{\star})^{T}(I-\mathbf{W})\mathbf{x}^{\star}\leq
F_{\operatorname{opt}},\end{split}$ (28)

which, together with $F(\mathbf{x}^{\star})\geq\min F(\mathbf{x})$ and (27),
yields that for any $i\in\mathcal{V}$,

$\begin{split}\|x_{i}^{\star}-\bar{x}^{\star}\|&\leq\|\mathbf{x}^{\star}-\mathbf{1}_{n}\otimes\bar{x}^{\star}\|\allowdisplaybreaks\\\
&\leq\sqrt{\frac{(\mathbf{x}^{\star})^{T}(I-\mathbf{W})\mathbf{x}^{\star}}{1-\beta}}\allowdisplaybreaks\\\
&\leq\sqrt{\frac{2\alpha(F_{\operatorname{opt}}-\min
F(\mathbf{x}))}{1-\beta}}.\end{split}$

Completes the proof.

###  -C Proof of Lemma 2

We first consider the case of non-identical $h_{i}$’s.

####  -C1 Non-identical $h_{i}$’s

Because $\mathbf{x}^{\star}$ is optimal to (3), by the first-order optimality
condition,

$\frac{(I-\mathbf{W})\mathbf{x}^{\star}}{\alpha}\in\partial
F(\mathbf{x}^{\star}).$ (29)

_Case i)_ : each $f_{i}+h_{i}$ is Lipschitz continuous. In this case, $F$ is
Lipschitz and we denote its Lipschitz constant as $G>0$. Then, the norm of all
subgradients of $F$ is bounded above by $G$, so that by (29),

$\frac{\|(I-\mathbf{W})\mathbf{x}^{\star}\|}{\alpha}\leq G.$ (30)

Moreover, because $\mathbf{1}_{n}$ is the eigenvector of $W$ corresponding to
the unique maximal eigenvalue $1$, we have

$\|W-\frac{\mathbf{1}_{n}\mathbf{1}_{n}^{T}}{n}\|\leq\max(|\lambda_{2}(W)|,|\lambda_{n}(W)|)=\beta,$
(31)

which, together with $(\frac{\mathbf{1}_{n}\mathbf{1}_{n}^{T}}{n}\otimes
I_{d})\mathbf{x}^{\star}=\bar{\mathbf{x}}^{\star}$ and $\mathbf{W}=W\otimes
I_{d}$, gives

$\begin{split}\|\mathbf{W}(\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star})\|&=\|(\mathbf{W}-\frac{\mathbf{1}_{n}\mathbf{1}_{n}^{T}}{n}\otimes
I_{d})(\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star})\|\\\
&\leq\|\mathbf{W}-\frac{\mathbf{1}_{n}\mathbf{1}_{n}^{T}}{n}\otimes
I_{d}\|\cdot\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|\\\
&\leq\beta\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|.\end{split}$ (32)

By (32) and $\mathbf{W}\bar{\mathbf{x}}^{\star}=\bar{\mathbf{x}}^{\star}$,

$\begin{split}\|(I-\mathbf{W})\mathbf{x}^{\star}\|&=\|(I-\mathbf{W})(\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star})\|\\\
&\geq\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|-\|\mathbf{W}(\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star})\|\\\
&\geq(1-\beta)\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|,\end{split}$
(33)

substituting which into (30) gives

$\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|\leq\frac{\alpha G}{1-\beta},$
(34)

which yields (5).

_Case ii)_ : $\operatorname{dom}h=\mathbb{R}^{nd}$ and $f_{i}+h_{i}$ is
coercive. Because $\operatorname{dom}F=\mathbb{R}^{nd}$ and $F$ is coercive,
$\mathcal{S}$ is compact and, therefore,

$\max_{\mathbf{x}\in\mathcal{S},\mathbf{v}\in\partial
F(\mathbf{x})}\|\mathbf{v}\|<+\infty.$ (35)

By the above equation, (29), and (33), we have

$\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|\leq\frac{\alpha\max_{\mathbf{x}\in\mathcal{S},\mathbf{v}\in\partial
F(\mathbf{x})}\|\mathbf{v}\|}{1-\beta},$ (36)

which yields (5).

####  -C2 Identical $h_{i}$’s

Define $\mathbf{y}^{\star}=\operatorname{prox}_{\alpha
h}(\bar{\mathbf{x}}^{\star})$. Because

$\mathbf{x}^{\star}=\operatorname{prox}_{\alpha
h}(\mathbf{W}\mathbf{x}^{\star}-\alpha\nabla f(\mathbf{x}^{\star})),$ (37)

using the non-expansiveness of the proximal operator, we have

$\begin{split}&\|\mathbf{x}^{\star}-\mathbf{y}^{\star}\|\\\
=&\|\operatorname{prox}_{\alpha h}(\mathbf{W}\mathbf{x}^{\star}-\alpha\nabla
f(\mathbf{x}^{\star}))-\operatorname{prox}_{\alpha
h}(\bar{\mathbf{x}}^{\star})\|\\\
\leq&\|\mathbf{W}\mathbf{x}^{\star}-\alpha\nabla
f(\mathbf{x}^{\star})-\bar{\mathbf{x}}^{\star}\|\\\
\leq&\|\mathbf{W}(\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star})\|+\alpha\|\nabla
f(\mathbf{x}^{\star})\|\\\
\leq&\beta\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|+\alpha\|\nabla
f(\mathbf{x}^{\star})\|,\end{split}$ (38)

where the last two step use
$\mathbf{W}\bar{\mathbf{x}}^{\star}=\bar{\mathbf{x}}^{\star}$ and (32),
respectively. Because $h_{i}$’s are identical, so are all blocks of
$\mathbf{y}^{\star}$, i.e., $\mathbf{y}^{\star}$ belongs to the consensus set
$\\{\mathbf{x}:x_{1}=\ldots=x_{n}\\}$. Moreover, $\bar{\mathbf{x}}^{\star}$ is
the projection of $\mathbf{x}^{\star}$ onto the consensus set. Therefore,

$\|\mathbf{x}^{\star}-\mathbf{y}^{\star}\|\geq\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|.$

By the above equation and (38),

$\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|\leq\frac{\alpha}{1-\beta}\|\nabla
f(\mathbf{x}^{\star})\|.$ (39)

Moreover, because $f$ is $L$-smooth and because of (39),

$\begin{split}f(\bar{\mathbf{x}}^{\star})-f(\mathbf{x}^{\star})&\leq\langle\nabla
f(\mathbf{x}^{\star}),\bar{\mathbf{x}}^{\star}-\mathbf{x}^{\star}\rangle+\frac{L}{2}\|\bar{\mathbf{x}}^{\star}-\mathbf{x}^{\star}\|^{2}\\\
&\leq\|\nabla
f(\mathbf{x}^{\star})\|\cdot\|\bar{\mathbf{x}}^{\star}-\mathbf{x}^{\star}\|+\frac{L}{2}\|\bar{\mathbf{x}}^{\star}-\mathbf{x}^{\star}\|^{2}\\\
&\leq\left(\frac{\alpha}{1-\beta}+\frac{L\alpha^{2}}{2(1-\beta)^{2}}\right)\|\nabla
f(\mathbf{x}^{\star})\|^{2}.\end{split}$ (40)

Also, because all the $h_{i}$’s are convex and identical, we have

$\begin{split}h(\bar{\mathbf{x}}^{\star})&=\sum_{i\in\mathcal{V}}h_{i}(\frac{1}{n}\sum_{j\in\mathcal{V}}x_{j}^{\star})\\\
&\leq\sum_{i\in\mathcal{V}}\frac{1}{n}\sum_{j\in\mathcal{V}}h_{i}(x_{j}^{\star})\\\
&=h(\mathbf{x}^{\star}).\end{split}$ (41)

By (40)–(41) and $F(\mathbf{x}^{\star})\leq F_{\operatorname{opt}}$ yield by
(28), we obtain

$\begin{split}F(\bar{\mathbf{x}}^{\star})&\leq
F(\mathbf{x}^{\star})+\left(\frac{\alpha}{1-\beta}+\frac{L\alpha^{2}}{2(1-\beta)^{2}}\right)\|\nabla
f(\mathbf{x}^{\star})\|^{2}\\\ &\leq
F_{\operatorname{opt}}+\left(\frac{\alpha}{1-\beta}+\frac{L\alpha^{2}}{2(1-\beta)^{2}}\right)\|\nabla
f(\mathbf{x}^{\star})\|^{2}.\end{split}$ (42)

_Case i)_ : both $f_{i}$ and $h_{i}$ are bounded from the below. Let
$\underline{f}$ and $\underline{h}$ be lower bounds of all $f_{i}$’s and all
$h_{i}$’s, respectively. Because each $f_{i}$ is $L_{i}$-smooth,

$\begin{split}f_{i}(x_{i}^{\star})&\geq
f_{i}(x_{i}^{\star}-\frac{1}{L_{i}}\nabla
f_{i}(x_{i}^{\star}))+\frac{1}{2L_{i}}\|\nabla f_{i}(x_{i}^{\star})\|^{2}\\\
&\geq\underline{f}+\frac{1}{2L_{i}}\|\nabla
f_{i}(x_{i}^{\star})\|^{2},\end{split}$

so that

$\|\nabla f(\mathbf{x}^{\star})\|^{2}\leq
2L(f(\mathbf{x}^{\star})-n\underline{f}).$ (43)

Moreover, by (28),

$\begin{split}f(\mathbf{x}^{\star})&=F(\mathbf{x}^{\star})-h(\mathbf{x}^{\star})\leq
F_{\operatorname{opt}}-n\underline{h}.\end{split}$ (44)

Substituting (44) into (43) gives

$\|\nabla
f(\mathbf{x}^{\star})\|\leq\sqrt{2L(F_{\operatorname{opt}}-n(\underline{f}+\underline{h}))}.$

Then by using (39) and (42), we obtain (5) and (6).

_Case ii)_ : Lipschitz continuous $f_{i}$. In this case, $\nabla
f(\mathbf{x})$ is bounded. Then by (39) and (42), we have (5) and (6).

_Case iii)_ : each $f_{i}+h_{i}$ is coercive. In this case, $F$ is coercive,
so that the following set is compact:

$\mathcal{S}=\\{\mathbf{x}:F(\mathbf{x})\leq F_{\operatorname{opt}}\\}.$ (45)

Moreover, due to (28), $\mathbf{x}^{\star}\in\mathcal{S}$. Therefore,

$\|\nabla f(\mathbf{x}^{\star})\|\leq\max_{\mathbf{x}\in\mathcal{S}}\|\nabla
f(\mathbf{x})\|<+\infty.$ (46)

substituting which into by (39) and (42) yields (5) and (6).

###  -D Proof of Theorem 1

The proof includes two steps. Step 1 rewrites the asynchronous Prox-DGD as an
asynchronous fixed-point update in order to use an existing convergence
theorem. Step 2 proves that the asynchronous fixed-point update satisfies the
conditions in the convergence theorem, which guarantees the convergence of the
asynchronous Prox-DGD.

Step 1: asynchronous fixed-point iteration. Prox-DGD (2) can be described by

$\mathbf{x}^{k+1}=\operatorname{T}(\mathbf{x}^{k}),$ (47)

where

$\displaystyle\operatorname{T}(\mathbf{x})=\operatorname{prox}_{\alpha
h}(\mathbf{W}\mathbf{x}-\alpha\nabla f(\mathbf{x})),$ (48)

Let $\operatorname{T}_{i}:\mathbb{R}^{nd}\rightarrow\mathbb{R}^{d}$ be the
$i$th block of $\operatorname{T}$ for any $i\in\mathcal{V}$ and consider the
asynchronous version of (47):

$x_{i}^{k+1}=\begin{cases}\operatorname{T}_{i}(\mathbf{z}_{i}^{k}),&k\in\mathcal{K}_{i},\\\
x_{i}^{k},&\text{otherwise},\end{cases}$ (49)

where $\mathbf{z}_{i}^{k}=(x_{1}^{t_{i1}^{k}},\ldots,x_{n}^{t_{in}^{k}})$ for
some non-negative integers $t_{ij}^{k}$. By letting

$t_{ij}^{k}=\begin{cases}s_{ij}^{k},&j\in\bar{\mathcal{N}}_{i},\\\
k,&\text{otherwise},\end{cases}\forall
i\in\mathcal{V},~{}k\in\mathcal{K}_{i}.$ (50)

(49) with $\operatorname{T}$ in (48) describes the asynchronous Prox-DGD.

For the asynchronous update (49), [38] presents the following convergence
results for pseudo-contractive operator $\operatorname{T}$ defined as: for
some $c\in(0,1)$,

$\\!\|\operatorname{T}(\mathbf{x})-\mathbf{x}^{\star}\|_{\infty}^{b}\leq
c\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b},\forall\mathbf{x}\in\mathbb{R}^{nd},\mathbf{x}^{\star}\in\operatorname{Fix}\operatorname{T},$
(51)

where $\operatorname{Fix}\operatorname{T}$ is the fixed point set of
$\operatorname{T}$.

######  Lemma 4 (Theorem 23, [38]).

Suppose that Assumption 5 holds and

$\displaystyle 0\in\mathcal{K}_{i},\forall i\in\mathcal{V}.$ (52)

If (51) holds for some $c\in(0,1)$, then $\\{\mathbf{x}^{k}\\}$ generated by
the iteration (49) converges to the unique fixed point of $\operatorname{T}$.

Although Theorem 23 in [38] assumes (52) for simplicity, the convergence still
holds without (52). With Lemma 4, to show Theorem 1, it suffices to show (51)
for $\operatorname{T}$ in (48).

Step 2: Proof of pseudo-contractivity (51). Note that by (37), any optimum of
problem (3) is a fixed point of $\operatorname{T}$ in (48). For simplicity of
representation, we define

$\displaystyle y_{i}$
$\displaystyle=\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}x_{j}-\alpha\nabla
f_{i}(x_{i}),$ (53) $\displaystyle y_{i}^{\star}$
$\displaystyle=\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}x_{j}^{\star}-\alpha\nabla
f_{i}(x_{i}^{\star}).$ (54)

Then,

$\displaystyle\operatorname{T}_{i}(\mathbf{x})=\operatorname{prox}_{\alpha
h_{i}}(y_{i}),~{}\operatorname{T}_{i}(\mathbf{x}^{\star})=\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star}).$

For any $i\in\mathcal{V}$, by
$x_{i}^{\star}=\operatorname{T}_{i}(\mathbf{x}^{\star})$ and the non-
expansiveness of the proximal operator,

$\begin{split}&\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}=\|\operatorname{T}_{i}(\mathbf{x})-\operatorname{T}_{i}(\mathbf{x}^{\star})\|^{2}\\\
=&\|\operatorname{prox}_{\alpha h_{i}}(y_{i})-\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star})\|^{2}\leq\|y_{i}-y_{i}^{\star}\|^{2}\\\
=&\|\sum_{j\in\mathcal{N}_{i}}w_{ij}(x_{j}-x_{j}^{\star})+\\\ &\quad
w_{ii}(x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star})))\|^{2}\\\
\leq&\sum_{j\in\mathcal{N}_{i}}w_{ij}\|x_{j}-x_{j}^{\star}\|^{2}+\\\
&w_{ii}\|x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}))\|^{2},\end{split}$ (55)

where the last step uses Jensen’s inequality on the norm square. Since each
$f_{i}$ is $\mu_{i}$-strongly convex and $\nabla f_{i}$ is Lipschitz
continuous, by [40, Equation (2.1.8)],

$\displaystyle\langle\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}),x_{i}-x_{i}^{\star}\rangle\geq\mu_{i}\|x_{i}-x_{i}^{\star}\|^{2},$
(56) $\displaystyle\langle\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}),x_{i}-x_{i}^{\star}\rangle\geq\frac{\|\nabla
f_{i}(x_{i})-\nabla f_{i}(x_{i}^{\star})\|^{2}}{L_{i}}.$ (57)

Then,

$\begin{split}&\|x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla
f_{i}(x_{i})-\nabla f_{i}(x_{i}^{\star}))\|^{2}\allowdisplaybreaks\\\
=&\|x_{i}-x_{i}^{\star}\|^{2}-2\frac{\alpha}{w_{ii}}\langle\nabla
f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}),x_{i}-x_{i}^{\star}\rangle\allowdisplaybreaks\\\
&+\left(\frac{\alpha}{w_{ii}}\right)^{2}\|\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star})\|^{2}\allowdisplaybreaks\\\
\overset{\eqref{eq:proofsmooth}}{\leq}&\|x_{i}-x_{i}^{\star}\|^{2}\\!\\!-\\!\frac{\alpha}{w_{ii}}\left(2\\!-\\!\frac{L_{i}\alpha}{w_{ii}}\right)\langle\nabla
f_{i}(x_{i})\\!-\\!\nabla
f_{i}(x_{i}^{\star}),x_{i}-x_{i}^{\star}\rangle\allowdisplaybreaks\\\
\overset{\eqref{eq:proofstrongconvexity}}{\leq}&\left(1-\frac{\alpha}{w_{ii}}\left(2-\frac{L_{i}\alpha}{w_{ii}}\right)\mu_{i}\right)\|x_{i}-x_{i}^{\star}\|^{2}\allowdisplaybreaks.\end{split}$
(58)

Substituting (58) into (55) yields

$\begin{split}\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}\leq\rho^{2}(\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b})^{2}\end{split}$
(59)

with $\rho$ in (10), i.e., (51) holds with $c=\rho$. Then by Lemma 4, the
convergence of $\\{\mathbf{x}^{k}\\}$ in Theorem 1 holds.

###  -E Proof of Theorem 2

####  -E1 Asymptotic convergence

The proof uses Proposition 2.3 in [36, Section 7.2]. Although it only
considers the scalar case, i.e., $d=1$, its proof holds for the general case
of $d>1$ by simply extending the absolute value to the Euclidean norm. The
proposition is rewritten below for convenience.

######  Proposition 1 (Proposition 7.2.3,[36]).

Suppose that Assumption 7 holds. The sequence $\\{\mathbf{x}^{k}\\}$ generated
by (49) converges to some points in the fixed point set $X^{\star}$ of
$\operatorname{T}$ if

  1. (a)

$X^{\star}$ is non-empty and closed.

  2. (b)

$\operatorname{T}$ is continuous and non-expansive in terms of the block-
maximum norm: for all $\mathbf{x}\in\mathbb{R}^{nd}$ and
$\mathbf{x}^{\star}\in X^{\star}$,

$\|\operatorname{T}(\mathbf{x})-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}.$
(60)

  3. (c)

For every $\mathbf{x}\in\mathbb{R}^{nd}$ and $\mathbf{x}^{\star}\in X^{\star}$
such that $\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}=\inf_{\mathbf{y}\in
X^{\star}}\|\mathbf{x}-\mathbf{y}\|_{\infty}^{b}$, let

$\displaystyle\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})=\\{i|~{}\|x_{i}-x_{i}^{\star}\|=\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}\\}$
$\displaystyle\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})=\\{\mathbf{y}:~{}y_{i}=x_{i}\text{
for all }i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star}),$
$\displaystyle\text{and
}\|y_{i}-x_{i}^{\star}\|<\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}\text{
for all }i\notin\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})\\}.$

If $\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}>0$, then there exists some
$i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$ such that
$\operatorname{T}_{i}(\mathbf{y})\neq y_{i}$ for all
$\mathbf{y}\in\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})$.

  4. (d)

If $\mathbf{x}\in\mathbb{R}^{nd}$, $\operatorname{T}_{i}(\mathbf{x})\neq
x_{i}$, and $\mathbf{x}^{\star}\in X^{\star}$, then

$\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|<\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}.$
(61)

Next, we prove that all the conditions in Proposition 1 hold for
$\operatorname{T}$ in (48). Because the fixed point set of (48) is the optimal
solution set of (3) and, by Assumption 1, the optimal set of problem (3) is
closed and non-empty, so is the fixed point set of (48), i.e., condition (a)
holds for $\operatorname{T}$ in (48).

Proof of condition (b): Since $\operatorname{T}$ in (48) is continuous, to
show condition (b), it suffices to show the non-expansiveness. For any
$i\in\mathcal{V}$, by (9) and the first two steps of (58),

$\begin{split}&\|x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla
f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}))\|^{2}\leq\|x_{i}-x_{i}^{\star}\|^{2},\end{split}$ (62)

substituting which into (55) yields

$\begin{split}\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}&\leq\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}\|x_{j}-x_{j}^{\star}\|^{2}\\\
&\leq(\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b})^{2}.\end{split}$ (63)

Since (63) holds for all $i\in\mathcal{V}$, condition (b) holds.

Proof of condition (c). We prove this condition by contradiction. Let
$\mathbf{x}$ and $\mathbf{x}^{\star}$ be such that
$\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}=\inf_{\mathbf{y}\in
X^{\star}}\|\mathbf{x}-\mathbf{y}\|_{\infty}^{b}>0$. Suppose that for any
$i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$, there exists a vector
$\mathbf{y}^{i}\in\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})$ such that

$\operatorname{T}_{i}(\mathbf{y}^{i})=y_{i}^{i}.$ (64)

Below we will show that this contradicts the assumption
$\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}>0$. Fix
$i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$. By (64) and (48),

$y_{i}^{i}=\operatorname{T}_{i}(\mathbf{y}^{i})=\operatorname{prox}_{\alpha
h_{i}}\biggl{(}\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}y_{j}^{i}-\alpha\nabla
f_{i}(y_{i}^{i})\biggr{)}.$ (65)

Moreover, by the third equality in (55), the convexity of norm, and (62),

$\begin{split}&\|y_{i}^{i}-x_{i}^{\star}\|\\\
=&\|\sum_{j\in\mathcal{N}_{i}}w_{ij}(y_{j}^{i}-x_{j}^{\star})+\\\ &\quad
w_{ii}(y_{i}^{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla
f_{i}(y_{i}^{i})-\nabla f_{i}(x_{i}^{\star})))\|\\\
\leq&\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}\|y_{j}^{i}-x_{j}^{\star}\|,\end{split}$
(66)

which, together with $i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$ and
$\mathbf{y}^{i}\in\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})$, yields

$\begin{split}&\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}=\|x_{i}-x_{i}^{\star}\|=\|y_{i}^{i}-x_{i}^{\star}\|\\\
\leq&\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}\|y_{j}^{i}-x_{i}^{\star}\|.\end{split}$
(67)

Because
$\|y_{j}^{i}-x_{j}^{\star}\|\leq\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}$
for all $j\in\bar{\mathcal{N}}_{i}$, $w_{ij}\in(0,1]$, and
$\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}=1$, equation (67) implies

$\|y_{j}^{i}-x_{j}^{\star}\|=\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}~{}\forall
j\in\bar{\mathcal{N}}_{i},$

which, together with
$\mathbf{y}^{i}\in\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})$, indicates

$\bar{\mathcal{N}}_{i}\subseteq\mathcal{I}(\mathbf{x},\mathbf{x}^{\star}).$

Following this process for every $j\in\mathcal{N}_{i}$, we will have
$\bar{\mathcal{N}}_{j}\subseteq\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$. By
the connectivity of the graph $\mathcal{G}$ and following this process, we can
derive

$\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})=\mathcal{V},$

and therefore, $\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})=\\{\mathbf{x}\\}$
which also indicates $\mathbf{y}^{i}=\mathbf{x}$ $\forall i\in\mathcal{V}$.
Then, by (64), $\operatorname{T}(\mathbf{x})=\mathbf{x}$, i.e., $\mathbf{x}\in
X^{\star}$. Note that we require $\mathbf{x}$ and $\mathbf{x}^{\star}$ be such
that $\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}=\inf_{\mathbf{y}\in
X^{\star}}\|\mathbf{y}-\mathbf{x}^{\star}\|_{\infty}^{b}$. This, together with
$\mathbf{x}\in X^{\star}$, yields $\mathbf{x}=\mathbf{x}^{\star}$, which
contradicts the assumption that
$\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}>0$.

Concluding the above, there exists
$i\in\mathcal{I}(\mathbf{x},\mathbf{x}^{\star})$ such that
$\operatorname{T}_{i}(\mathbf{y})\neq y_{i}$ for all
$\mathbf{y}\in\mathcal{U}(\mathbf{x},\mathbf{x}^{\star})$, i.e., condition (c)
holds.

Proof of condition (d). To proceed, we first derive the following lemma.

######  Lemma 5.

Let $\beta>0$ and $v_{1},\ldots,v_{m}\in\mathbb{R}^{d}$ be vectors satisfying
$\|v_{i}\|\leq\beta$ for all $1\leq i\leq m$. If there exists positive
constants $\alpha_{1},\ldots,\alpha_{m}$ such that
$\sum_{i=1}^{m}\alpha_{i}=1$ and

$\|\sum_{i=1}^{m}\alpha_{i}v_{i}\|=\beta,$ (68)

then

$v_{1}=\ldots=v_{m}.$ (69)

###### Proof.

Since $\|v_{i}\|\leq\beta$ for all $1\leq i\leq m$ and

$\beta=\|\sum_{i=1}^{m}\alpha_{i}v_{i}\|\leq\sum_{i=1}^{m}\alpha_{i}\|v_{i}\|,$

we have $\|v_{i}\|=\beta$ $\forall i\in\mathcal{V}$ and

$\|\sum_{i=1}^{m}\alpha_{i}v_{i}\|=\sum_{i=1}^{m}\alpha_{i}\|v_{i}\|.$ (70)

Because all the $v_{i}$’s have the same norm, (70) is possible only when all
the $v_{i}$’s are identical, i.e., (69) holds. ∎

Next, based on Lemma 5, we prove condition (d) by contradiction. Because of
(63), if (61) fails to hold, then for some $i\in\mathcal{V}$,

$\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|=\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}.$
(71)

Below we will show that (71) contradicts $\operatorname{T}_{i}(\mathbf{x})\neq
x_{i}$. Let $y_{i},y_{i}^{\star}$ be defined as (53)–(54). Our proof uses

$\displaystyle\operatorname{T}_{i}(\mathbf{x})-y_{i}=x_{i}^{\star}-y_{i}^{\star},$
(72) $\displaystyle\nabla f_{i}(x_{i})=\nabla f_{i}(x_{i}^{\star}),$ (73)
$\displaystyle x_{i}-x_{i}^{\star}=x_{j}-x_{j}^{\star},~{}\forall
j\in\mathcal{N}_{i},$ (74)

which will be proved later. Using (72)–(74), we have

$\begin{split}\\!\operatorname{T}_{i}(\mathbf{x})&\overset{\eqref{eq:Tixyixistar}}{=}y_{i}+x_{i}^{\star}-y_{i}^{\star}\allowdisplaybreaks\\\
&=\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}x_{j}-\alpha\nabla
f_{i}(x_{i})+x_{i}^{\star}-y_{i}^{\star}\allowdisplaybreaks\\\
&\overset{\eqref{eq:xixjidentical}}{=}\\!\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}(x_{j}^{\star}\\!+x_{i}\\!-x_{i}^{\star})-\\!\alpha\nabla
f_{i}(x_{i})+\\!x_{i}^{\star}-y_{i}^{\star}\allowdisplaybreaks\\\
&\overset{\eqref{eq:identicalgra}}{=}x_{i}+\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}x_{j}^{\star}-\alpha\nabla
f_{i}(x_{i}^{\star})-y_{i}^{\star}=x_{i},\end{split}$ (75)

where the second and the last step use the definitions of $y_{i}$ and
$y_{i}^{\star}$, respectively. Note that
$\operatorname{T}_{i}(\mathbf{x})=x_{i}$ contradicts the requirement in
condition (d). Concluding the above, condition (d) holds if (72)–(74) hold.

Next, we prove (72)–(74). Because
$\|x_{j}-x_{j}^{\star}\|\leq\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}$
for all $j\in\bar{\mathcal{N}}_{i}$, (71) holds only if every inequality in
(55), (62), and (63) holds with equality, which yields

$\displaystyle\|\operatorname{prox}_{\alpha
h_{i}}(y_{i})-\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star})\|^{2}=\|y_{i}-y_{i}^{\star}\|^{2},$ (76)
$\displaystyle\frac{\alpha}{w_{ii}}\left(2\\!-\\!\frac{L_{i}\alpha}{w_{ii}}\right)\langle\nabla
f_{i}(x_{i})\\!-\\!\nabla f_{i}(x_{i}^{\star}),x_{i}-x_{i}^{\star}\rangle=0,$
(77)
$\displaystyle\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}=\|\sum_{j\in\mathcal{N}_{i}}w_{ij}(x_{j}-x_{j}^{\star})+$
$\displaystyle\quad w_{ii}(x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla
f_{i}(x_{i})-\nabla f_{i}(x_{i}^{\star})))\|^{2}.$ (78)

According to [33, Proposition 12.27],

$\displaystyle\|\operatorname{prox}_{\alpha
h_{i}}(y_{i})-\operatorname{prox}_{\alpha h_{i}}(y_{i}^{\star})\|^{2}$
$\displaystyle\leq$
$\displaystyle\|y_{i}-y_{i}^{\star}\|^{2}-\|y_{i}-\operatorname{prox}_{\alpha
h_{i}}(y_{i})-(y_{i}^{\star}-\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star}))\|^{2},$

by which and (76), we have

$y_{i}-\operatorname{prox}_{\alpha
h_{i}}(y_{i})=y_{i}^{\star}-\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star}).$

Moreover, $\operatorname{prox}_{\alpha
h_{i}}(y_{i})=\operatorname{T}_{i}(\mathbf{x})$, $\operatorname{prox}_{\alpha
h_{i}}(y_{i}^{\star})=\operatorname{T}_{i}(\mathbf{x}^{\star})=x_{i}^{\star}$,
so that

$\operatorname{T}_{i}(\mathbf{x})-y_{i}=\operatorname{T}_{i}(\mathbf{x}^{\star})-y_{i}^{\star}=x_{i}^{\star}-y_{i}^{\star},$

i.e., (72) holds. By (9), (77), and (57), we have (73). To prove (74), we let
$m=|\bar{\mathcal{N}}_{i}|$, $v_{1},\ldots,v_{m}$ in Lemma 5 be
$x_{j}-x_{j}^{\star}$, $j\in\mathcal{N}_{i}$ and
$x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla f_{i}(x_{i})-\nabla
f_{i}(x_{i}^{\star}))$, and
$\beta=\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b}$. By (62), for any
$1\leq\ell\leq m$, $\|v_{\ell}\|\leq\beta$, which, together with (78), implies
that all the conditions in Lemma 5 hold and therefore,

$x_{j}-x_{j}^{\star}=x_{i}-x_{i}^{\star}-\frac{\alpha}{w_{ii}}(\nabla
f_{i}(x_{i})-\nabla f_{i}(x_{i}^{\star})),~{}\forall j\in\mathcal{N}_{i}.$
(79)

By the above equation and (73), we obtain (74), which completes the proof.

####  -E2 Linear convergence

The proof uses [38, Theorem 24].

######  Lemma 6 (Theorem 24, [38]).

Suppose that Assumption 7 and (52) hold. If (51) holds for some $c\in(0,1)$,
then $\\{\mathbf{x}^{k}\\}$ generated by the asynchronous iteration (49)
satisfy

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq
c^{\frac{k}{B+D+1}}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b}.$ (80)

Note that in Step 2 of Appendix -D, we have shown the pseudo-contractivity. In
addition, although we do not assume (52), the proof of [38, Theorem 24] still
holds, with the convergence rate (80) becomes

$\|\mathbf{x}^{k}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq
c^{\lfloor\frac{k}{B+D+1}\rfloor}\|\mathbf{x}^{0}-\mathbf{x}^{\star}\|_{\infty}^{b}.$
(81)

Completes the proof.

###  -F Proof of Theorem 3

By (59) and the proof of Theorem 24 in [38],

$\|\mathbf{x}^{k+1}-\mathbf{x}^{\star}\|_{\infty}^{b}\leq\rho\max_{k-\tau^{k}\leq
t\leq k}\|\mathbf{x}^{t}-\mathbf{x}^{\star}\|_{\infty}^{b},$

which, together with the definition of $\\{k^{m}\\}$ in (14), yields the
result.

###  -G Proof of Lemma 3

DGD-ATC (17) can be viewed as a weighted gradient method [41, Section 1.2.1]
with weight matrix $\mathbf{W}$ for solving

$\underset{\mathbf{x}\in\mathbb{R}^{nd}}{\operatorname{minimize}}~{}f(\mathbf{x})+\frac{\mathbf{x}^{T}(\mathbf{W}^{-1}-I)\mathbf{x}}{2\alpha}.$
(82)

Therefore, the existence of fixed point to DGD-ATC can be guaranteed by the
non-emptiness of the optimal solution set of problem (82).

####  -G1 Non-empty solution set of (82)

Let $z^{\star}$ be an optimum to (1). Define
$\mathbf{z}^{\star}=\mathbf{1}_{n}\otimes z^{\star}$,
$\mathcal{L}_{\alpha}(\mathbf{x})=F(\mathbf{x})+\frac{\|\mathbf{x}\|_{\mathbf{W}^{-1}-I}^{2}}{2\alpha}$,
and

$\mathcal{C}=\\{\mathbf{x}:\mathcal{L}_{\alpha}(\mathbf{x})\leq\mathcal{L}_{\alpha}(\mathbf{z}^{\star})\\}.$

Since $\min_{\mathbf{x}\in\mathbb{R}^{nd}}\mathcal{L}_{\alpha}(\mathbf{x})$ is
equivalent to
$\min_{\mathbf{x}\in\mathcal{C}}\mathcal{L}_{\alpha}(\mathbf{x})$, the minimum
of $\mathcal{L}_{\alpha}$ exists if the optimum of the later problem exists
which can be guaranteed by the nonemptiness and compactness of $\mathcal{C}$.
Clearly, $\mathcal{C}$ is non-empty since $\mathbf{z}^{\star}\in\mathcal{C}$.

Below, we prove that $\mathcal{C}$ is compact. Let $\mathbf{x}$ be an
arbitrary vector in $\mathcal{C}$ and denote
$\bar{\mathbf{x}}=\mathbf{1}_{n}\otimes\frac{1}{n}\sum_{i\in\mathcal{V}}x_{i}$.
By the $L$-smoothness of $f$,

$\begin{split}f(\bar{\mathbf{x}})-f(\mathbf{x})&\leq\langle\nabla
f(\mathbf{x}),\bar{\mathbf{x}}-\mathbf{x}\rangle+\frac{L}{2}\|\bar{\mathbf{x}}-\mathbf{x}\|^{2}\\\
&\leq\|\nabla
f(\mathbf{x})\|\cdot\|\bar{\mathbf{x}}-\mathbf{x}\|+\frac{L}{2}\|\bar{\mathbf{x}}-\mathbf{x}\|^{2}.\end{split}$
(83)

By Assumption 2 and $h_{i}\equiv 0$, each $f_{i}$ is bounded from the below,
and we let $\underline{f}$ be a lower bound for all $f_{i}$’s. Then, by the
$L_{i}$-smoothness of $f_{i}$,

$\underline{f}\leq f_{i}(x_{i}-\frac{1}{L_{i}}\nabla f_{i}(x_{i}))\leq
f_{i}(x_{i})-\frac{1}{2L_{i}}\|\nabla f_{i}(x_{i})\|^{2},$

so that

$\|\nabla f(\mathbf{x})\|^{2}\leq 2L(f(\mathbf{x})-n\underline{f})\leq
2L(f^{\star}-n\underline{f})$ (84)

where the last step is due to
$f(\mathbf{x})\leq\mathcal{L}_{\alpha}(\mathbf{x})\leq\mathcal{L}_{\alpha}(\mathbf{z}^{\star})=f^{\star}$.
In addition, because $f(\mathbf{x})\geq n\underline{f}$ and
$\mathcal{L}_{\alpha}(\mathbf{x})\leq f^{\star}$, we have

$\|\mathbf{x}\|_{\mathbf{W}^{-1}-I}^{2}=2\alpha(\mathcal{L}_{\alpha}(\mathbf{x})-f(\mathbf{x}))\leq
2\alpha(f^{\star}-n\underline{f}).$ (85)

Since $\mathcal{G}$ is connected, we have
$\operatorname{Range}(\mathbf{W}^{-1}-I)=\\{\mathbf{x}:x_{1}+\ldots+x_{n}=\mathbf{0}\\}$,
so that $\mathbf{x}-\bar{\mathbf{x}}$ is the projection of $\mathbf{x}$ onto
$\operatorname{Range}(\mathbf{W}^{-1}-I)$. Moreover, because
$W\succ\mathbf{0}$, we have $\beta=\lambda_{2}(W)$, so that the minimum non-
zero eigenvalue of $\mathbf{W}^{-1}-I$ is
$\frac{1}{\lambda_{2}(W)}-1=\frac{1}{\beta}-1=\frac{1-\beta}{\beta}$.
Therefore,

$\|\mathbf{x}-\bar{\mathbf{x}}\|^{2}\leq\frac{\beta\|\mathbf{x}\|_{\mathbf{W}^{-1}-I}^{2}}{1-\beta},$

which, together with (85) and $\beta\leq 1$, yields

$\|\mathbf{x}-\bar{\mathbf{x}}\|^{2}\leq\frac{2\alpha(f^{\star}-n\underline{f})}{1-\beta}.$
(86)

Substituting (84) and (86) into (83) and using $f(\mathbf{x})\leq f^{\star}$
gives

$f(\bar{\mathbf{x}})\leq C_{0}:=f^{\star}+\left(\sqrt{\frac{\alpha
L}{1-\beta}}+\frac{\alpha L}{1-\beta}\right)(f^{\star}-h),$

or equivalently,
$\sum_{i\in\mathcal{V}}f_{i}(\frac{1}{n}\sum_{i\in\mathcal{V}}x_{i})\leq
C_{0}$. Moreover, by [41, Proposition B.9] and the bounded optimum set of
problem (1), every level set of $\sum_{i\in\mathcal{V}}f_{i}(x)$ is bounded,
which yields the compactness of

$\displaystyle\bigg{\\{}y\in\mathbb{R}^{d}:\sum_{i\in\mathcal{V}}f_{i}(y)\leq
C_{0}\bigg{\\}}.$ (87)

Due to the arbitrariness of $\mathbf{x}\in\mathcal{C}$, we have that for any
$\mathbf{x}\in\mathcal{C}$, $\frac{1}{n}\sum_{i=1}^{n}x_{i}$ belongs to the
compact set (87) and (86) holds. Therefore, $\mathcal{C}$ is compact.

Concluding all the above, the optimal solution set of problem (82) is non-
empty.

####  -G2 Optimality gap

Because $\mathbf{x}^{\star}$ is a fixed point of (17),

$\mathbf{x}^{\star}=\mathbf{W}(\mathbf{x}^{\star}-\alpha\nabla
f(\mathbf{x}^{\star})),$ (88)

which, together with $I\succeq\mathbf{W}\succ\mathbf{0}$, yields

$\begin{split}\|(I-\mathbf{W})\mathbf{x}^{\star}\|=\alpha\|\mathbf{W}\nabla
f(\mathbf{x}^{\star})\|\leq&\alpha\|\nabla
f(\mathbf{x}^{\star})\|.\end{split}$ (89)

Moreover, because $\mathbf{x}^{\star}\in\mathcal{C}$, (84) with
$\mathbf{x}=\mathbf{x}^{\star}$ holds, i.e.,

$\|\nabla f(\mathbf{x}^{\star})\|^{2}\leq 2L(f^{\star}-n\underline{f}).$ (90)

By (33), (89), and (90), we obtain

$\|\mathbf{x}^{\star}-\bar{\mathbf{x}}^{\star}\|\leq\frac{\alpha}{1-\beta}\sqrt{2L(f^{\star}-n\underline{f})},$
(91)

i.e., (5) holds.

Next, we prove (6). Since $\mathbf{z}^{\star}$ is the minimum of
$\mathcal{L}_{\alpha}$,

$f(\mathbf{x}^{\star})\leq\mathcal{L}_{\alpha}(\mathbf{x}^{\star})\leq\mathcal{L}_{\alpha}(\mathbf{z}^{\star})=f^{\star}.$
(92)

By letting $\mathbf{x}=\mathbf{x}^{\star}$ in (83) and using (90)–(91), we
obtain

$\begin{split}f(\bar{\mathbf{x}}^{\star})\leq&f(\mathbf{x}^{\star})+\left(\frac{\alpha}{1-\beta}+\frac{L\alpha^{2}}{2(1-\beta)^{2}}\right)\cdot
2L(f^{\star}-n\underline{f}),\end{split}$

which, together with (92), yields (6) and completes the proof.

###  -H Proof of Theorem 4

The proof is similar to that of Theorem 1. We first rewrite the update (17) in
an operator form and prove the pseudo-contractivity (51), and then use Lemma 4
to show convergence.

DGD-ATC (17) can be described by the general fixed-point update (47), where

$\displaystyle\operatorname{T}(\mathbf{x})=\mathbf{W}(\mathbf{x}-\alpha\nabla
f(\mathbf{x})).$ (93)

Let $\operatorname{T}_{i}:\mathbb{R}^{nd}\rightarrow\mathbb{R}^{d}$ be the
$i$th block of $\operatorname{T}$. The update (49) with $\operatorname{T}$ in
(93) describes the asynchronous DGD-ATC.

Below, we show (51). For any $i\in\mathcal{V}$, since
$x_{i}^{\star}=\operatorname{T}_{i}(\mathbf{x}^{\star})$,

$\begin{split}&\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}=\|\operatorname{T}_{i}(\mathbf{x})-\operatorname{T}_{i}(\mathbf{x}^{\star})\|^{2}\\\
=&\|\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}(x_{j}-x_{j}^{\star}-\alpha(\nabla
f_{j}(x_{j})-\nabla f_{j}(x_{j}^{\star})))\|^{2}\\\
\leq&\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}\|x_{j}-x_{j}^{\star}-\alpha(\nabla
f_{j}(x_{j})-\nabla f_{j}(x_{j}^{\star}))\|^{2},\end{split}$ (94)

where the last step uses Jensen’s inequality on the norm square. Similar to
(58) with $w_{ii}=1$,

$\begin{split}&\|x_{j}-x_{j}^{\star}-\alpha(\nabla f_{j}(x_{j})-\nabla
f_{j}(x_{j}^{\star}))\|^{2}\\\
\leq&(1-\alpha(2-L_{j}\alpha))\|x_{j}-x_{j}^{\star}\|^{2}\\\
\leq&\hat{\rho}^{2}(\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b})^{2}.\end{split}$

Substituting the above equation into (94) yields

$\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}\leq\hat{\rho}^{2}(\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b})^{2},$
(95)

which results in (51) with $c=\hat{\rho}$.

By (51) and Lemma 4, the convergence result holds.

###  -I Proof of Theorem 5

The proof is similar to the proof of Theorem 2.

####  -I1 Asymptotic convergence

We prove the asymptotic convergence by showing that all the conditions in
Proposition 1 hold. Because the fixed point set of $\operatorname{T}$ in (93)
is the optimal solution set of minimizing the convex and closed function
$\mathcal{L}_{\alpha}$ defined at the beginning of Appendix -G, it is closed.
The non-emptiness of the fixed point set is shown by Lemma 3. As a result,
condition (a) in Proposition 1 holds. The proofs of the conditions (c), (d)
for the asynchronous DGD-ATC are very similar to their proof for the
asynchronous Prox-DGD and are therefore omitted for simplicity.

Below, we prove that condition (b) also holds. Since $\operatorname{T}$ in
(93) is continuous, to show condition (b), it suffices to show the non-
expansiveness. By using (20) and similar derivation of (62), we have

$\begin{split}&\|x_{j}-x_{j}^{\star}-\alpha(\nabla f_{j}(x_{j})-\nabla
f_{j}(x_{j}^{\star}))\|^{2}\leq\|x_{j}-x_{j}^{\star}\|^{2}.\end{split}$

Substituting the above equation into (94) yields

$\begin{split}\|\operatorname{T}_{i}(\mathbf{x})-x_{i}^{\star}\|^{2}&\leq\sum_{j\in\bar{\mathcal{N}}_{i}}w_{ij}\|x_{j}-x_{j}^{\star}\|^{2}\\\
&\leq(\|\mathbf{x}-\mathbf{x}^{\star}\|_{\infty}^{b})^{2}.\end{split}$

This completes the proof of condition (b) for $\operatorname{T}$ in (93). Then
by Proposition 1, $\\{\mathbf{x}^{k}\\}$ converges to a fixed point of
$\operatorname{T}$.

####  -I2 Linear convergence

By (95), the pseudo-contractivity condition in Lemma 6 holds with
$c=\hat{\rho}$. Then by (81), the linear convergence holds.

###  -J Proof of Theorem 6

By (95) and following the proof in Appendix -F, we obtain the result.

## References

  * [1] M. Assran, A. Aytekin, H. R. Feyzmahdavian, M. Johansson, and M. G. Rabbat, “Advances in asynchronous parallel and distributed optimization,” _Proceedings of the IEEE_ , vol. 108, no. 11, pp. 2013–2031, 2020.
  * [2] D. Huba, J. Nguyen, K. Malik, R. Zhu, M. Rabbat, A. Yousefpour, C.-J. Wu, H. Zhan, P. Ustinov, H. Srinivas _et al._ , “Papaya: Practical, private, and scalable federated learning,” _Proceedings of Machine Learning and Systems_ , vol. 4, pp. 814–832, 2022.
  * [3] A. Nedić and A. Ozdaglar, “Convergence rate for consensus with delays,” _Journal of Global Optimization_ , vol. 47, pp. 437–456, 2010.
  * [4] K. Mishchenko, F. Iutzeler, J. Malick, and M.-R. Amini, “A delay-tolerant proximal-gradient algorithm for distributed learning,” in _International Conference on Machine Learning_. PMLR, 2018, pp. 3587–3595.
  * [5] J. Zhang and K. You, “AsySPA: An exact asynchronous algorithm for convex optimization over digraphs,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 6, pp. 2494–2509, 2019.
  * [6] T. T. Doan, C. L. Beck, and R. Srikant, “On the convergence rate of distributed gradient methods for finite-sum optimization under communication delays,” _Proceedings of the ACM on Measurement and Analysis of Computing Systems_ , vol. 1, no. 2, pp. 1–27, 2017.
  * [7] V. Kungurtsev, M. Morafah, T. Javidi, and G. Scutari, “Decentralized asynchronous non-convex stochastic optimization on directed graphs,” __accepted to_ IEEE Transactions on Control of Network Systems_, 2023\.
  * [8] M. S. Assran and M. G. Rabbat, “Asynchronous gradient push,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 1, pp. 168–183, 2020.
  * [9] J. Zhang and K. You, “Fully asynchronous distributed optimization with linear convergence in directed networks,” _arXiv preprint arXiv:1901.08215_ , 2019\.
  * [10] T. Wu, K. Yuan, Q. Ling, W. Yin, and A. H. Sayed, “Decentralized consensus optimization with asynchrony and delays,” _IEEE Transactions on Signal and Information Processing over Networks_ , vol. 4, no. 2, pp. 293–307, 2017.
  * [11] Y. Tian, Y. Sun, and G. Scutari, “Achieving linear convergence in distributed asynchronous multiagent optimization,” _IEEE Transactions on Automatic Control_ , vol. 65, no. 12, pp. 5264–5279, 2020.
  * [12] M. Bianchi, W. Ananduta, and S. Grammatico, “The distributed dual ascent algorithm is robust to asynchrony,” _IEEE Control Systems Letters_ , vol. 6, pp. 650–655, 2022.
  * [13] L. Cannelli, F. Facchinei, G. Scutari, and V. Kungurtsev, “Asynchronous optimization over graphs: Linear convergence under error bound conditions,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 10, pp. 4604–4619, 2020.
  * [14] P. Latafat and P. Patrinos, “Primal-dual algorithms for multi-agent structured optimization over message-passing architectures with bounded communication delays,” _Optimization Methods and Software_ , vol. 37, no. 6, pp. 2052–2079, 2022.
  * [15] Y. Su, Z. Wang, M. Cao, M. Jia, and F. Liu, “Convergence analysis of dual decomposition algorithm in distributed optimization: Asynchrony and inexactness,” _IEEE Transactions on Automatic Control_ , 2022.
  * [16] M. Ubl and M. T. Hale, “Faster asynchronous nonconvex block coordinate descent with locally chosen stepsizes,” in _IEEE Conference on Decision and Control (CDC)_ , 2022, pp. 4559–4564.
  * [17] M. Ubl and M. Hale, “Totally asynchronous large-scale quadratic programming: Regularization, convergence rates, and parameter selection,” _IEEE Transactions on Control of Network Systems_ , vol. 8, no. 3, pp. 1465–1476, 2021\.
  * [18] X. Wu, C. Liu, S. Magnússon, and M. Johansson, “Delay-agnostic asynchronous coordinate update algorithm,” in _Proceedings of the 40th International Conference on Machine Learning_ , vol. 202. PMLR, 2023, pp. 37 582–37 606.
  * [19] Y. Wang, Q. Zhao, and X. Wang, “An asynchronous gradient descent based method for distributed resource allocation with bounded variables,” _IEEE Transactions on Automatic Control_ , vol. 67, no. 11, pp. 6106–6111, 2021.
  * [20] K. Yuan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” _SIAM Journal on Optimization_ , vol. 26, no. 3, pp. 1835–1854, 2016.
  * [21] L. Dalcín, R. Paz, M. Storti, and J. D’Elía, “MPI for python: Performance improvements and MPI-2 extensions,” _Journal of Parallel and Distributed Computing_ , vol. 68, no. 5, pp. 655–662, 2008.
  * [22] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,” _Proceedings of the IEEE_ , vol. 86, no. 11, pp. 2278–2324, 1998.
  * [23] J. Zeng and W. Yin, “On nonconvex decentralized gradient descent,” _IEEE Transactions on signal processing_ , vol. 66, no. 11, pp. 2834–2848, 2018.
  * [24] S. Pu, A. Olshevsky, and I. C. Paschalidis, “Asymptotic network independence in distributed stochastic optimization for machine learning: Examining distributed and centralized stochastic gradient descent,” _IEEE signal processing magazine_ , vol. 37, no. 3, pp. 114–122, 2020.
  * [25] X. Wu, C. Liu, S. Magnusson, and M. Johansson, “Delay-agnostic asynchronous distributed optimization,” __accepted to_ IEEE Conference on Decision and Control (CDC)_, 2023.
  * [26] P. Giselsson, M. D. Doan, T. Keviczky, B. De Schutter, and A. Rantzer, “Accelerated gradient methods and dual decomposition in distributed model predictive control,” _Automatica_ , vol. 49, no. 3, pp. 829–833, 2013.
  * [27] V. Vapnik, “An overview of statistical learning theory,” _IEEE Transactions on Neural Networks_ , vol. 10, no. 5, pp. 988–999, 1999.
  * [28] A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” _IEEE Transactions on Automatic Control_ , vol. 54, no. 1, pp. 48–61, 2009.
  * [29] A. Nedić, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” _SIAM Journal on Optimization_ , vol. 27, no. 4, pp. 2597–2633, 2017.
  * [30] C. Liu, Z. Zhou, J. Pei, Y. Zhang, and Y. Shi, “Decentralized composite optimization in stochastic networks: A dual averaging approach with linear convergence,” __accepted to_ IEEE Transactions on Automatic Control_, 2022.
  * [31] W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” _IEEE Transactions on Signal Processing_ , vol. 63, no. 22, pp. 6013–6023, 2015.
  * [32] ——, “EXTRA: An exact first-order algorithm for decentralized consensus optimization,” _SIAM Journal on Optimization_ , vol. 25, no. 2, pp. 944–966, 2015.
  * [33] H. H. Bauschke, P. L. Combettes _et al._ , _Convex analysis and monotone operator theory in Hilbert spaces (second edition)_. Springer, 2017.
  * [34] W. Choi and J. Kim, “On the convergence analysis of the decentralized projected gradient descent,” _arXiv preprint arXiv:2303.08412_ , 2023.
  * [35] J. Zhang, H. Liu, A. M.-C. So, and Q. Ling, “A penalty alternating direction method of multipliers for convex composite optimization over decentralized networks,” _IEEE Transactions on Signal Processing_ , vol. 69, pp. 4282–4295, 2021.
  * [36] D. Bertsekas and J. Tsitsiklis, _Parallel and distributed computation: numerical methods_. Athena Scientific, 2015\.
  * [37] Z. Zhou, P. Mertikopoulos, N. Bambos, P. Glynn, Y. Ye, L.-J. Li, and L. Fei-Fei, “Distributed asynchronous optimization with unbounded delays: How slow can you go?” in _Proceedings of the 35th International Conference on Machine Learning_ , vol. 80. PMLR, 10–15 Jul 2018, pp. 5970–5979.
  * [38] H. R. Feyzmahdavian and M. Johansson, “Asynchronous iterations in optimization: New sequence results and sharper algorithmic guarantees.” _J. Mach. Learn. Res._ , vol. 24, pp. 158–1, 2023.
  * [39] D. Dua and C. Graff, “UCI machine learning repository,” 2017. [Online]. Available: http://archive.ics.uci.edu/ml
  * [40] Y. Nesterov, _Introductory lectures on convex optimization: A basic course_. Springer Science & Business Media, 2003, vol. 87.
  * [41] D. P. Bertsekas _et al._ , “Nonlinear programming,” 1995.