# On the convergence result of the gradient-push algorithm on directed graphs
with constant stepsize

Woocheol Choi  Department of Mathematics, Sungkyunkwan University, Suwon
440-746, Republic of Korea<EMAIL_ADDRESS>,  Doheon Kim  Department of
Applied Mathematics, Hanyang University, Hanyangdaehak-ro 55, Sangnok-gu,
Ansan, Gyeonggi-do 15588, Republic of Korea<EMAIL_ADDRESS>and
Seok-Bae Yun  Department of Mathematics, Sungkyunkwan University, Suwon
440-746, Republic of Korea<EMAIL_ADDRESS>
###### Abstract.

Gradient-push algorithm has been widely used for decentralized optimization
problems when the connectivity network is a direct graph. This paper shows
that the gradient-push algorithm with stepsize $\alpha>0$ converges
exponentially fast to an $O(\alpha)$-neighborhood of the optimizer under the
assumption that each cost is smooth and the total cost is strongly convex.
Numerical experiments are provided to support the theoretical convergence
results.

###### Key words and phrases:

Gradient-push algorithm, Push-sum algorithm, Convex optimization

###### 2010 Mathematics Subject Classification:

Primary 90C25, 68Q25

###### Contents

  1. 1 Introduction
  2. 2 Gradient-push algorithm and related basic results
  3. 3 The intuition behind the gradient-push algorithm
  4. 4 Main convergence result
  5. 5 Weighted Consensus
  6. 6 Estimates on the distance between the average and the optimizer
  7. 7 Uniform boundedness of the sequence
  8. 8 Convergence estimates
  9. 9 Numerical experiments
    1. 9.1 Convex local cost case
    2. 9.2 Nonconvex local cost case

##  1\. Introduction

In this paper we are concerned with the distributed optimization

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

where $n$ denotes the number of the agents in the network, and
$f_{i}:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is the local objective function
available only to the agent $i$ for each $1\leq i\leq n$. We can reformulate
this problem as

$\begin{split}\min_{x_{i}\in\mathbb{R}^{d}}&~{}\sum_{i=1}^{n}f_{i}(x_{i})\\\
s.t.&~{}x_{i}=x_{j},\quad\forall~{}j\in N_{i},\end{split}$

where $N_{i}$ is the set of in-neighbors of agent $i$ in the directed network.

Distributed optimization has been studied extensively in the last years, since
it appears in various applications, including wireless sensor networks [15,
29], multi-agent control [5, 6, 7], smart grids [10, 11], and machine learning
[1, 2, 3, 4, 12].

To solve the distributed optimization on networks, there have been a numerous
research in the context of the distributed optimization. We refer to [23, 26,
31, 32], and references therin. Among the algorithms, one fundamental
algorithm is the distributed gradient descent algorithm (DGD) introduced in
[23]. Although this algorithm has led to great progress in distributed
optimization, it is known that the exact convergence is achieved only using a
diminishing stepsize, which is contrast to the centralized gradient descent
method. This fact motivated the development of various distributed
optimization algorithms such as EXTRA [31], decentralized gradient trakcing
(DGD) [26, 27, 38]. Recently there has been an interest in designing the
communication efficient algorithm for the distributed optimization [28, 18,
19, 16].

We are interested in the distributed optimization posed on directed graphs,
which has gained increasing attention in recent years. Nedic-Olshevsky [23,
25] developed the gradient-push algorithm, which is based on the push-sum
algorithm for consensus [20, 35] on directed graphs. The gradient-push
algorithm has been widely used by numerous researchers. The algorithm has been
studied for online distributed optimization [13, 22, 46, 42, 47]. The work
[Q1] studied the gradient-push algorithm involving the quantized
communications and the paper [21] designed the gradient-push algorithm with
the event-triggred communication. In addition, the gradient-push algorithm has
been used for constrained distributed optimization [45] and zeroth-order
distributed optimization [40]. See also [44] for the asynchronous gradient-
push algorithm. We also refer to the works [26, 36, 38] for the variants of
gradient-push algorithm involving the communication of gradient informations.

Despite its wide applications, the convergence analysis of the gradient-push
algorithm has not been fully exploited in the literature. In the original work
[23], Nedic-Olshevsky established the convergence result for convex cost
functions when the stepsize $\alpha(t)$ is given as $\alpha(t)=1/\sqrt{t}$ or
satisfies the condition $\sum_{t=1}^{\infty}\alpha(t)=\infty$ and
$\sum_{t=1}^{\infty}\alpha(t)^{2}<\infty$. In the work [25], the convergence
result was obtained when the cost function is strongly convex and
$\alpha(t)=c/t$ for some $c>0$. Recently, the work [33] established a
convergence result for non-convex cost functions. The results are summarized
in Table 1. We remark that the convergence results in the previous works [23,
25, 33] assumed that the gradient of the cost functions are uniformly bounded.

In this paper, we will obtain a convergence result of the gradient-push
algorithm without assuming the uniform boundedness of the gradients of the
cost functions. We will only assume that each cost function is $L$-smooth and
the total cost is strongly convex. Under these assumptions, we will show that
the gradient-push algorithm with a constant stepsize $\alpha(t)\equiv\alpha>0$
converges exponentially fast to an $O(\alpha)$-neighborhood of the optimizer
$x_{*}$. This result can be seen as an extension of the works [39, 9] where
the authors obtained the exponential convergence results of the decentralized
gradient descent on undirected graph.

This paper is organized as follows: In Section 2, we review the push-sum
algorithm and related properties. In Section 3, we provide the intuition
behind the push-sum algorithm for reader’s understanding. In Section 4, we
state the main convergence results of this paper. In Section 5, the estimate
measuring the effect of the weighted consensus process is obtained. In Section
6, we derive a sequential estimate on the distance between the average and the
optimizer. Combining the estimates from Section 5 and 6, we prove the uniform
boundedness of the sequence in Section 7, and establish the main convergence
result in Section 8. In the final Section 9, we provide numerical results
supporting our theoretical results.

| Convex | Regularity | Learning rate | Error | Rate
---|---|---|---|---|---
[25] | C | $\|\nabla f_{i}\|_{{\infty}}<\infty$ |  $\sum_{t=1}^{\infty}\alpha(t)=\infty$ $\sum_{t=1}^{\infty}\alpha(t)^{2}<\infty$ | $\|x_{i}(t)-x_{*}\|$ | $o(1)$
[25] | C | $\|\nabla f_{i}\|_{{\infty}}<\infty$ | $\alpha(t)=1/\sqrt{t}$ | $f(\hat{z}_{i}(t))-f(z_{*})$ | $O\Big{(}\frac{\log t}{\sqrt{t}}\Big{)}$
[24] | SC | $\|z_{i}(t)\|_{{\infty}}<\infty$ | $\alpha(t)=\frac{c}{t}$ | $f(\hat{z}_{i}(t))-f(z_{*})$ | $O\Big{(}\frac{\log t}{t}\Big{)}$
[33] | NC |  $\|\nabla f_{i}\|_{\infty}<\infty$ $L$-smooth |  $\sum_{t=1}^{\infty}\alpha(t)=\infty$ $\sum_{t=1}^{\infty}\alpha(t)^{2}<\infty$ | $\|x_{k}(t)-x_{*}\|$ | o(1)
[33] | NC |  $\|\nabla f_{i}\|_{\infty}<\infty$ $L$-smooth | $\alpha(t)=\frac{c}{t}$ | $\|x_{k}(t)-x_{*}\|$ | $O\Big{(}\frac{1}{t}\Big{)}$
This work | SC |  $L$-smooth | $\alpha(t)\equiv\alpha$ | $\|x_{k}(t)-x_{*}\|$ | $O(e^{-ct})+O({\alpha})$
Table 1. This table summarizes the convergene results for the gradient-push
algorithm. Here C (resp., SC) means that the total cost function is assumed to
be convex (resp., strongly convex). NC is an abbreviation for nonconvex. Also
$x_{*}$ is an optimizer of (1.1) and $\hat{z}_{i}(t)$ is an weighted average
of $\\{z_{i}(1),\cdots,z_{i}(t)\\}$.

##  2\. Gradient-push algorithm and related basic results

In this section, we review the gradient-push algorithm and some preliminary
results for obtaining the convergence estimates of the gradient-push
algorithm.

We consider a directed graph $G=(V,E)$ with the vertex set
$V=\\{1,2,\cdots,n\\}$ and the edge set $E\subset V\times V$, where the
communication between agents are performed. Here $(i,j)\in E$ means that there
is a directed edge from agent $i$ to $j$. We define the set of in-neighbors of
agent $i$ by

$N_{i}^{in}=\\{j\in V~{}\mid~{}(j,i)\in E\\},$

and the set of out-neighbors of agent $i$ is defined by

$N_{i}^{out}=\\{j\in V~{}\mid~{}(i,j)\in E\\}.$

Throughout this paper, we assume that $G$ satisfies the following two
assumptions:

  * •

(G1) Every vertex of $G$ has a self-loop, i.e.,

$(i,i)\in E\quad(\Leftrightarrow i\in N_{i}^{in}~{}\Leftrightarrow~{}i\in
N_{i}^{out}),\quad\forall~{}i\in V.$

  * •

(G2) $G$ is strongly connected, i.e., $G$ contains a directed path from $i$ to
$j$ for every $(i,j)\in V\times V$.

We set $d_{j}=|N_{j}^{out}|$ and

$W_{ij}=\left\\{\begin{array}[]{ll}{\frac{1}{d_{j}}}&\textrm{if}~{}j\in
N_{i}^{in}\quad{(\mbox{or, equivalently, }i\in N_{j}^{out})}\\\
0&\textrm{if}~{}j\notin N_{i}^{in}.\end{array}\right.$ (2.1)

The gradient-push algorithm [23] is described as follows: Given inital data
$x_{i}(0)\in\mathbb{R}^{d}$, $y_{i}(0)=1$, for each $1\leq i\leq n$, and
$t\in\mathbb{N}\cup\\{0\\}$, we update

$\begin{split}w_{i}(t+1)&=\sum_{j=1}^{n}W_{ij}x_{j}(t)\\\
y_{i}(t+1)&=\sum_{j=1}^{n}W_{ij}y_{j}(t)\\\
z_{i}(t+1)&=\frac{w_{i}(t+1)}{y_{i}(t+1)}\\\
x_{i}(t+1)&=w_{i}(t+1)-\alpha\nabla f_{i}(z_{i}(t+1)).\end{split}$ (2.2)

Let us denote by
$w(t)=\mathrm{col}(w_{1}(t),\cdots,w_{n}(t))\in\mathbb{R}^{nd}$ the column
vector obtained by stacking $w_{1}(t),\dots,w_{n}(t)$, and similarly for
$x(t)\in\mathbb{R}^{nd}$, $y(t)\in\mathbb{R}^{d}$, and
$z(t)\in\mathbb{R}^{nd}$. Then we may write the above algorithm as

$\begin{split}w(t+1)&=(W\otimes I_{d})x(t)\\\ y(t+1)&=Wy(t)\\\
z_{i}(t+1)&=\frac{w_{i}(t+1)}{y_{i}(t+1)},\quad 1\leq i\leq n,\\\
x(t+1)&=w(t+1)-\alpha\nabla F(z(t+1)),\end{split}$ (2.3)

where we define $\nabla F(x):=\mathrm{col}(\nabla f_{1}(x_{1}),\cdots,\nabla
f_{n}(x_{n}))$ for any $x=\mathrm{col}(x_{1},\dots,x_{n})$, $I_{d}$ is the
$d\times d$ identity matrix, and $\otimes$ is the Kronecker product. We assume
that $y_{i}(0)=1,\quad i=1,\dots,n$. Note that the positivity of $y(t)$ is
ensured by the following inductive argument:

$y_{i}(t+1)=\sum_{j=1}^{n}W_{ij}y_{j}(t)\geq
W_{ii}y_{i}(t)=\frac{y_{i}(t)}{d_{i}}>0.$

We notice that $W$ is column stochastic, by the following relation:

$\sum_{i=1}^{n}W_{ij}=\sum_{i=1}^{n}\frac{1_{N_{i}^{in}}(j)}{d_{j}}=\sum_{i=1}^{n}\frac{1_{N_{j}^{out}}(i)}{|N_{j}^{out}|}=1,\quad
j=1,\dots,n.$

Note that column stochasticity of $W$ is equivalent to
$1_{n}^{\top}W=1_{n}^{\top}$. Also note that by (2.1), $W_{ij}>0$ if and only
if $(j,i)\in E$. By (G2), $W$ is an irreducible matrix, so we can apply the
Perron-Frobenius theorem to deduce that $W$ has a right eigenvector
$\pi=(\pi_{1},\cdots,\pi_{n})^{\top}$ associated with the eigenvalue 1, of
which all entries are positive and satisfy

$\sum_{j=1}^{n}\pi_{j}=1.$ (2.4)

Moreover, by (G1), $G$ is aperiodic. Since $G$ is both strongly connected and
aperiodic, $W$ is primitive, and it is known that

$W^{\infty}:=\lim_{k\to\infty}W^{k}=\pi 1_{n}^{\top}$ (2.5)

with convergence speed geometrically fast [30]. We denote the Euclidean norm
by $\|\cdot\|$ and for a matrix $A\in\mathbb{R}^{n\times n}$, and set the
matrix norm
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
by

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}=\sup_{x\in\mathbb{R}^{n}\setminus\\{0\\}}\frac{\|Ax\|}{\|x\|}.$

Now we define a weighted inner product as $\langle
x,y\rangle_{\pi}=x^{\top}\textrm{diag}(\pi)^{-1}y$ and its induced norm
$\|x\|_{\pi}=\|\textrm{diag}(\sqrt{\pi})^{-1}x\|$. We also set
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}$
as the matrix norm induced by $\|\cdot\|_{\pi}$ for $A\in\mathbb{R}^{n\times
n}$, i.e.,

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}=\sup_{x\in\mathbb{R}^{n}\setminus\\{0\\}}\frac{\|Ax\|_{\pi}}{\|x\|_{\pi}}.$

It is easy to check that
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\textrm{diag}(\sqrt{\pi})^{-1}A\textrm{diag}(\sqrt{\pi})\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$.
Also we have

$\|\cdot\|_{\pi}\leq\frac{1}{\sqrt{\pi_{a}}}\|\cdot\|\quad\textrm{and}\quad\|\cdot\|\leq\sqrt{\pi_{b}}\|\cdot\|_{\pi},$

where $\pi_{a}$ and $\pi_{b}$ denote the minimum and maximum values of $\pi$.
We state a basic lemma for $W$.

######  Lemma 2.1.

We have

$|||W|||_{\pi}=|||W^{\infty}|||_{\pi}=1.$

###### Proof.

We give a proof of this lemma for reader’s convenience. Using Cauchy-Schwartz
inequality, we deduce the following inequality

$\begin{split}\|Wx\|_{\pi}^{2}&=\sum_{i=1}^{n}\Big{(}\sum_{j=1}^{n}w_{ij}\sqrt{\pi_{j}}\frac{x_{j}}{\sqrt{\pi}_{j}}\Big{)}^{2}\pi_{i}^{-1}\\\
&\leq\sum_{i=1}^{n}\Big{(}\sum_{j=1}^{n}w_{ij}\pi_{j}\Big{)}\Big{(}\sum_{j=1}^{n}w_{ij}\frac{x_{j}^{2}}{\pi_{j}}\pi_{i}^{-1}\Big{)}\\\
&=\sum_{i=1}^{n}\sum_{j=1}^{n}w_{ij}\frac{x_{j}^{2}}{\pi_{j}}=\sum_{j=1}^{n}\frac{x_{j}^{2}}{\pi_{j}}=\|x\|_{\pi}^{2},\end{split}$

which proves $|||W|||_{\pi}\leq 1$. Also this directly implies that
$|||W^{\infty}|||_{\pi}\leq 1$. Combining these inequalities with the fact
$W\pi=\pi$ yields that

$|||W|||_{\pi}=|||W^{\infty}|||_{\pi}=1.$

This finishes the proof. ∎

We recall the following result from [37, Lemma 1]:

######  Lemma 2.2 ([37]).

Under assumptions $(G1)$ and $(G2)$, we have the estimate
$\sigma_{W}:=|||W-W^{\infty}|||_{\pi}<1$.

Using this lemma, one may derive the following convergence estimate of
$y(t)\in\mathbb{R}^{n}$ towards $n\pi\in\mathbb{R}^{n}$:

$\|y(t)-n\pi\|_{\pi}=\left\|(W-W^{\infty})^{t}(1_{n}-n\pi)\right\|_{\pi}\leq\sigma_{W}^{t}\|1_{n}-n\pi\|_{\pi}$
(2.6)

We can similarly define a weighted inner product on $\mathbb{R}^{nd}$ by

$\langle x,y\rangle_{\pi\otimes 1_{d}}:=x^{\top}\textrm{diag}(\pi\otimes
1_{d})^{-1}y=x^{\top}(\textrm{diag}(\pi)^{-1}\otimes I_{d})y,$

and its induced norm and matrix norm can be defined analogously.

######  Lemma 2.3.

For any $n\times n$ matrix $A$, we have

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\otimes
I_{d}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi\otimes
1_{d}}={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}.$

###### Proof.

We proceed in the following way:

$\displaystyle{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\otimes
I_{d}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi\otimes 1_{d}}$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\textrm{diag}(\sqrt{\pi\otimes
1_{d}})^{-1}(A\otimes I_{d})\textrm{diag}(\sqrt{\pi\otimes
1_{d}})\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|(\textrm{diag}(\sqrt{\pi})^{-1}\otimes
I_{d})(A\otimes I_{d})(\textrm{diag}(\sqrt{\pi})\otimes
I_{d})\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|[\textrm{diag}(\sqrt{\pi})^{-1}A\textrm{diag}(\sqrt{\pi})]\otimes
I_{d}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\textrm{diag}(\sqrt{\pi})^{-1}A\textrm{diag}(\sqrt{\pi})\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
$\displaystyle={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|A\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}.$

In the fourth inequality, we have used that the matrix norm
${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|\cdot\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}$
is equal to the largest singular value of the matrix. ∎

##  3\. The intuition behind the gradient-push algorithm

In this section, we give an intuition behind the gradient-push algorithm
(2.3). We may write the algorithm (2.3) in terms of $w(t)$ as

$w(t+1)=(W\otimes I_{d})(w(t)-\alpha\nabla F(z(t)).$ (3.1)

In order to understand the algorithm (2.3) in the above form, one needs to
find why we define $z(t)$ as $z_{i}(t)=w_{i}(t)/y_{i}(t)$. First, we prove
that regardless of the value of the variable $z(t)$, the variable $w(t)$ in
(3.1) achieves a weighted consensus up to an $O(\alpha)$ error under a mild
boundedness assumption. Precisely, we have the following lemma.

######  Lemma 3.1.

Assume that $\sup_{s\geq 0}\|\nabla F(z(s))\|<\infty$. Then there exist
constants $D>0$ and $\zeta\in(0,1)$ determined by the graph such that

$\|w(t)-n\pi\otimes\bar{w}(t)\|\leq D\zeta^{t}\|w(0)\|-\frac{(\alpha
D)\zeta}{1-\zeta}\sup_{s\geq 0}\|\nabla F(z(s))\|$

for all $t\geq 0$.

###### Proof.

Using (3.1) iteratively, we have

$w(t)=W^{t}\otimes I_{d}(w(0))-\alpha\sum_{k=1}^{t-1}\Big{(}W^{t-k}\otimes
I_{d}\Big{)}\nabla F(z(k)).$ (3.2)

Multiplying $\pi 1_{n}^{T}$ in front of the both sides and using the property
that $\pi 1_{n}^{T}W=\pi 1_{n}^{T}$, we get the following equation

$\pi\otimes\bar{w}(t)=\pi 1_{n}^{T}\otimes
I_{d}(w(0))-\alpha\sum_{k=1}^{t-1}\pi 1_{n}^{T}\otimes I_{d}\nabla F(z(k)).$
(3.3)

Combining (3.2) and (3.3) gives the following identity

$w(t)-n\pi\otimes\bar{w}(t)=\Big{(}W^{t}-\pi 1_{n}^{T}\Big{)}\otimes
I_{d}(w(0))-\alpha\sum_{k=1}^{t-1}\Big{[}(W^{t-k}-\pi 1_{n}^{T})\otimes
I_{d}\Big{]}\nabla F(z(k)).$ (3.4)

By the property (2.6), there exist constants $D>0$ and $\zeta>0$ such that

${\left|\kern-1.07639pt\left|\kern-1.07639pt\left|W^{t}-\pi
1_{n}^{T}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}\leq D\zeta^{t}$

for all $t\geq 0$. Inserting this estimate in (3.4) we deduce

$\begin{split}&\|w(t)-n\pi\otimes\bar{w}(t)\|\\\ &\hskip 19.91684pt\leq
D\zeta^{t}\|w(0)\|-D\alpha\sum_{k=1}^{t-1}\zeta^{t-k}\|\nabla F(z(k))\|\\\
&\hskip 19.91684pt\leq D\zeta^{t}\|w(0)\|-\alpha D\sup_{s\geq 0}\|\nabla
F(z(s))\|\sum_{k=1}^{t-1}\zeta^{t-k}\\\ &\hskip
19.91684pt=D\zeta^{t}\|w(0)\|-\frac{(\alpha D)\zeta}{1-\zeta}\sup_{s\geq
0}\|\nabla F(z(s))\|.\end{split}$

The proof is done. ∎

The above lemma shows that $w(t)/n\pi$ gets close to the consensus
$\bar{w}(t)$ as $t\rightarrow\infty$ up to an error $O(\alpha)$. Now, we
multiply $\pi 1_{n}^{T}$ in front of both sides of (3.1), we find

$\begin{split}\bar{w}(t+1)&=\bar{w}(t)-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}(z_{i}(t))\\\ &=\bar{w}(t)-\alpha\nabla
f(\bar{w}(t))+\frac{\alpha}{n}\sum_{i=1}^{n}\Big{(}\nabla
f_{i}(\bar{w}(t))-\nabla f_{i}(z_{i}(t))\Big{)}.\end{split}$

From this expression, we see that $\\{\bar{w}(t)\\}_{t\geq 0}$ follows
approximately the gradient descent method of the global cost function $f$
provided that $z_{i}(t)$ is close enough to $\bar{w}(t)$ for each $1\leq i\leq
n$. On the other hand, the above lemm yields that $\frac{w_{i}(t)}{n\pi_{i}}$
gets close to $\bar{w}(t)$ up to an $O(\alpha)$-error.

Therefore, if we want the solution $\bar{w}(t)$ to converge to the minimizer
$w_{*}$ of $f$, the natural choice of $z_{i}(t)$ would be
${w_{i}(t)}/n\pi_{i}$ if we konw $\pi_{i}$ in advance. However, it is often
the case that the value $\pi_{i}$ should be calculated in a distributed manner
when a graph of network is given. Having said this, a natural choice of
$z_{i}(t)$ is given by $z_{i}(t)=w_{i}(t)/y_{i}(t)$ with the balancing
constants $y(t)$ of (2.2) in view of the exponential convergence of $y(t)$ to
$n\pi$ (see (2.6)).

##  4\. Main convergence result

Throughout this paper, we assume that the cost functions satisfy the following
two assumptions.

  * •

(F1) The gradient of each function $f_{i}$ is Lipschitz continuous with
constant $L_{i}>0$ for all $1\leq i\leq d$, i.e., $f_{i}$ is $L_{i}$-smooth:

$\|\nabla f_{i}(x)-\nabla f_{i}(y)\|\leq
L_{i}\|x-y\|\quad\forall~{}x,y\in\mathbb{R}^{d}.$ (4.1)

  * •

(F2) The total cost $f$ is $\beta$-strongly convex with a value $\beta>0$.

Under the above assumptions, there exists a unique minimizer $w_{*}$ of the
cost $f$. In order to analyze the convergence property of the algorithm (2.2),
we consider the following two quantities

$A_{t}:=\|\bar{w}(t)-w_{*}\|\quad\textrm{and}\quad
B_{t}:=\|w(t)-(W^{\infty}\otimes I_{d})w(t)\|_{\pi}.$

Here $A_{t}$ measures the distance between the average of states $\bar{w}(t)$
and the optimal point $w_{*}$. Also we note that

$(W^{\infty}\otimes I_{d})w(t)=(\pi 1_{n}^{T}\otimes
I_{d})w(t)=n\pi\otimes\bar{w}(t).$ (4.2)

Therefore $B_{t}$ measures how the static $w(t)$ to the weighted consensus
states $n\pi\otimes\bar{w}(t)$. Obtaining convergence properties of $A_{t}$
and $B_{t}$ will give a convergence estimate of the sequence $w(t)$ to
$n\pi\otimes w_{*}$ as seen in the following lemma.

######  Lemma 4.1.

We have

$\|w(t)-n\pi\otimes w_{*}\|_{\pi\otimes
1_{d}}\leq\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+n\|\bar{w}(t)-w_{*}\|.$

###### Proof.

We apply the triangle inequality to find

$\|w(t)-n\pi\otimes w_{*}\|_{\pi\otimes
1_{d}}\leq\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\|n\pi\otimes(\bar{w}(t)-w_{*})\|_{\pi\otimes 1_{d}}.$ (4.3)

By (2.4),

$\|n\pi\otimes(\bar{w}(t)-w_{*})\|_{\pi\otimes
1_{d}}^{2}=n^{2}\sum_{j=1}^{n}\pi_{j}\|\bar{w}(t)-w_{*}\|^{2}=n^{2}\|\bar{w}(t)-w_{*}\|^{2}.$

Combining this with (4.3) gives

$\|w(t)-n\pi\otimes w_{*}\|_{\pi\otimes
1_{d}}\leq\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+n\|\bar{w}(t)-w_{*}\|.$

The proof is done. ∎

In order to state the main convergence results, we set the following values:

$\delta=\max_{t\in\mathbb{N}_{0}}\max_{1\leq i\leq
n}\frac{1}{y_{i}(t)}\quad\textrm{and}\quad\rho=\sigma_{W}(1+\alpha L\delta).$
(4.4)

We also set $\gamma=\frac{\beta L}{\beta+L}$ and

$\begin{split}\mathbf{D}_{1}&=\delta{\|1_{n}-n\pi\|_{\pi}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}}\\\
\mathbf{D}_{2}&=L\delta{\|1_{n}-n\pi\|_{\pi}}\|w_{*}\|+\|\nabla F(1_{n}\otimes
w_{*})\|_{\pi\otimes 1_{d}}.\end{split}$

In the following result, we establish that the sequence
$\\{(A_{t},B_{t})\\}_{t\geq 0}$ is bounded under a condition on the stepsize
$\alpha>0$.

######  Theorem 4.2.

Let $b=\frac{n\gamma}{4L\delta}$. Assume that (F1) and (F2) hold, and that
$\alpha>0$ satisfies

$\alpha\leq\frac{2}{L+\beta}\quad\textrm{and}\quad\alpha<\frac{b(1-\sigma_{W})}{L\sigma_{W}(\delta
b+\delta{\|1_{n}-n\pi\|_{\pi}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}})}$ (4.5)

for all $t\geq 0$. Then the sequence
$\\{(A_{t},B_{t})\\}_{t\in\mathbb{N}_{0}}$ is uniformly bounded in time, i.e.,

$\sup_{t\geq 0}A_{t}<\infty,\quad\sup_{t\geq 0}B_{t}<\infty.$

More precisely, take a value $t_{0}\in\mathbb{N}$ such that
$(L\delta/n){\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t_{0}}}\leq\gamma/2$ and define
$R>0$ as

$R=\max\Big{\\{}A_{t_{0}},~{}\frac{B_{t_{0}}}{b},~{}2\|w_{*}\|,~{}\frac{\sigma_{W}\alpha\textbf{D}_{2}}{b(1-\sigma_{W})-\alpha
L\sigma_{W}(\delta
b+\delta{\|1_{n}-n\pi\|_{\pi}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}})}\Big{\\}}.$

Then we have

$A_{t}\leq R\quad\textrm{and}\quad B_{t}\leq bR$

for all $t\geq t_{0}$.

We mention that the above boundedness result may hold for a larger range of
$\alpha>0$ than that guaranteed by Theorem 4.2. We refer to [39, 9] for the
discussion of this issue for the decentralized gradient method on undirected
graph.

Now we state the main convergence result for the gradient-push algorithm.

######  Theorem 4.3.

Assume that (F1) and (F2) hold, and that $\alpha>0$ satisfies
$\alpha\leq\frac{2}{L+\beta}$ and the sequence $\\{A_{t}\\}$ is bounded, i.e.,
there exists $R>0$ such that $A_{t}\leq R$ for all $t\geq 0$. Set
$\bar{R}=L\textbf{D}_{1}R+\textbf{D}_{2}>0$. Then for all $t\geq 0$ we have

$\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}\leq\rho^{t}\|w(0)-n\pi\otimes\bar{w}(0)\|_{\pi\otimes
1_{d}}+\frac{\alpha\sigma_{W}\bar{R}}{1-\rho}$ (4.6)

and

$\begin{split}\|\bar{w}(t)-w_{*}\|&\leq(1-\gamma\alpha)^{t}\|\bar{w}(0)-w_{*}\|+\frac{\alpha
L\delta}{n}\|w(0)-n\pi\otimes\bar{w}(0)\|_{\pi\otimes
1_{d}}t\Big{[}\max\\{1-\gamma\alpha,\rho\\}\Big{]}^{t-1}\\\
&\quad+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}}(\|w_{*}\|+R)t\Big{[}\max\\{1-\gamma\alpha,e^{-c}\\}\Big{]}^{t-1}+\frac{\alpha
L\delta}{n\gamma}\frac{\sigma_{W}\bar{R}}{1-\rho}.\end{split}$

The above result establishes that $w(t)$ converges exponentially fast to an
$O\Big{(}\frac{\alpha}{1-\rho}\Big{)}$ neighborhood of
$n\pi\otimes\bar{w}_{*}$. In order to prove the above two results, we will
derive two sequential inequalities of $A_{t}$ and $B_{t}$ in the next two
sections. Based on those inequalities, we prove Theorem 4.2 in Section 7, and
then establish the proof of Theorem 4.3 in Section 8.

##  5\. Weighted Consensus

In this section, we give an estimate of $\|w(t+1)-(W^{\infty}\otimes
I_{d})w(t+1)\|_{\pi\otimes 1_{d}}$ in terms of $\|w(t)-(W^{\infty}\otimes
I_{d})w(t)\|_{\pi\otimes 1_{d}}$ and $\|\bar{w}(t)-w_{*}\|$. As a preliminary
step, we bound a measure of the consensus for the variable $z(t)$ in terms of
$w(t)$ in the following lemma.

######  Lemma 5.1.

We have the following estimate

$\|z(t)-1_{n}\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}\leq\delta\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\Big{(}\|\bar{w}(t)-w_{*}\|+\|w_{*}\|\Big{)}.$

for all $t\in\mathbb{N}\cup\\{0\\}$ and $1\leq i\leq n$.

###### Proof.

Using the definition of $z(t)$ in (2.2) and $\delta>0$ from (4.4), we find

$\begin{split}\|z(t)-1_{n}\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}&=\Big{[}\sum_{j=1}^{n}\frac{1}{\pi_{j}}\Big{(}\frac{w_{j}(t)}{y_{j}(t)}-\bar{w}(t)\Big{)}^{2}\Big{]}^{1/2}\\\
&\leq\delta\Big{[}\sum_{j=1}^{n}\frac{1}{\pi_{j}}(w_{j}(t)-y_{j}(t)\bar{w}(t))^{2}\Big{]}^{1/2}\\\
&=\delta\|w(t)-y(t)\otimes\bar{w}(t)\|_{\pi\otimes 1_{d}}.\end{split}$

By applying the triangle inequality here, we get

$\|z(t)-1_{n}\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}\leq\delta\Big{(}\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\|(n\pi-y(t))\otimes\bar{w}(t)\|_{\pi\otimes 1_{d}}\Big{)}.$ (5.1)

Here we use (2.6) to estimate

$\begin{split}\|(n\pi-y(t))\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}^{2}&=\sum_{j=1}^{n}\frac{1}{\pi_{j}}\Big{(}n\pi_{j}-y_{j}(t)\Big{)}^{2}\|\bar{w}(t)\|^{2}\\\
&=\|n\pi-y(t)\|_{\pi}^{2}\|\bar{w}(t)\|^{2}\\\
&\leq\|1_{n}-n\pi\|_{\pi}^{2}\sigma_{W}^{2t}\|\bar{w}(t)\|^{2}.\end{split}$
(5.2)

Putting this in (5.1) yields the following estimate

$\begin{split}\|z(t)-&1_{n}\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}\leq\delta\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|\bar{w}(t)\|\\\
&\leq\delta\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\Big{(}\|\bar{w}(t)-w_{*}\|+\|w_{*}\|\Big{)}.\end{split}$

The proof is done. ∎

We are ready to establish the main estimate of this seciton.

######  Proposition 5.2.

Assume that (F1) and (F2) hold, and that $\kappa(t)\geq 1$ for all $t\geq 0$.
Then we have

$\begin{split}&\|w(t+1)-n\pi\otimes\bar{w}(t+1)\|_{\pi\otimes 1_{d}}\\\
&\leq\sigma_{W}(1+\alpha L\delta)\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\alpha
L\sigma_{W}D_{1}[t]\|\bar{w}(t)-w_{*}\|+\alpha\sigma_{W}D_{2}[t],\end{split}$
(5.3)

where

$\begin{split}D_{1}[t]&=\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}}\\\
D_{2}[t]&=L\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|+\|\nabla
F(1_{n}\otimes w_{*})\|_{\pi\otimes 1_{d}}.\end{split}$

###### Proof.

First we prove (5.3). Using the definition (2.3) and the relation (4.2), we
proceed as follows.

$\begin{split}&\|w(t+1)-(W^{\infty}\otimes I_{d})w(t+1)\|_{\pi\otimes
1_{d}}\\\ &=\|((I_{n}-W^{\infty})\otimes I_{d})w(t+1)\|_{\pi\otimes 1_{d}}\\\
&=\|[((I_{n}-W^{\infty})W)\otimes I_{d}]x(t)\|_{\pi\otimes 1_{d}}\\\
&=\|[((I_{n}-W^{\infty})W)\otimes I_{d}](w(t)-\alpha\nabla
F(z(t)))\|_{\pi\otimes 1_{d}}\end{split}$ (5.4)

We further manipulate this identity to have

$\begin{split}&\|w(t+1)-(W^{\infty}\otimes I_{d})w(t+1)\|_{\pi\otimes
1_{d}}\\\ &=\|[(W-W^{\infty})\otimes I_{d}](w(t)-\alpha\nabla
F(z(t)))\|_{\pi\otimes 1_{d}}\\\ &=\|[(W-W^{\infty})\otimes
I_{d}][((I_{n}-W^{\infty})\otimes I_{d})w(t)-\alpha\nabla
F(z(t))]\|_{\pi\otimes 1_{d}},\end{split}$

where we have used $W^{\infty}W=WW^{\infty}=(W^{\infty})^{2}=W^{\infty}$ in
the first and the second equalities. By the triangle inequality and Lemma 2.3,
we estimate (5.4) as follows:

$\begin{split}&\|w(t+1)-(W^{\infty}\otimes I_{d})w(t+1)\|_{\pi\otimes
1_{d}}\\\
&\leq{\left|\kern-1.07639pt\left|\kern-1.07639pt\left|(W-W^{\infty})\otimes
I_{d}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi\otimes
1_{d}}\left[\|((I_{n}-W^{\infty})\otimes I_{d})w(t)\|_{\pi\otimes
1_{d}}+\alpha\|\nabla F(z(t))\|_{\pi\otimes 1_{d}}\right]\\\
&={\left|\kern-1.07639pt\left|\kern-1.07639pt\left|W-W^{\infty}\right|\kern-1.07639pt\right|\kern-1.07639pt\right|}_{\pi}\left[\|w(t)-(W^{\infty}\otimes
I_{d})w(t)\|_{\pi\otimes 1_{d}}+\alpha\|\nabla F(z(t))\|_{\pi\otimes
1_{d}}\right].\end{split}$ (5.5)

This together with Lemma 2.2 gives

$\begin{split}&\|w(t+1)-(W^{\infty}\otimes I_{d})w(t+1)\|_{\pi\otimes
1_{d}}\\\ &\leq\sigma_{W}\|w(t)-(W^{\infty}\otimes I_{d})w(t)\|_{\pi\otimes
1_{d}}+\alpha\sigma_{W}\|\nabla F(z(t))\|_{\pi\otimes 1_{d}}.\end{split}$
(5.6)

To estimate $\|\nabla F(z(t))\|_{\pi\otimes 1_{d}}$ further, we write

$\begin{split}\nabla F(z(t))&=(\nabla F(z(t))-\nabla
F(1_{n}\otimes\bar{w}(t)))\\\ &\qquad+(\nabla F(1_{n}\otimes\bar{w}(t))-\nabla
F(1_{n}\otimes w_{*}))+\nabla F(1_{n}\otimes w_{*}).\end{split}$ (5.7)

Using Lemma 5.1 we have

$\begin{split}&\|z(t)-1_{n}\otimes\bar{w}(t)\|_{\pi\otimes 1_{d}}\\\
&\leq\delta\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\Big{(}\|\bar{w}(t)-w_{*}\|+\|w_{*}\|\Big{)}.\end{split}$

Combining this with (5.7) yields

$\begin{split}&\|\nabla F(z(t))\|_{\pi\otimes 1_{d}}\\\ &\leq
L\|z(t)-1_{n}\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+L\|1_{n}\otimes\bar{w}(t)-1_{n}\otimes w_{*}\|_{\pi\otimes
1_{d}}+\|\nabla F(1_{n}\otimes w_{*})\|_{\pi\otimes 1_{d}}\\\ &\leq
L\delta\|w(t)-n\pi\otimes\bar{w}(t)\|_{\pi\otimes
1_{d}}+L\Big{(}\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}}\Big{)}\|\bar{w}(t)-w_{*}\|\\\
&\qquad+\|\nabla F(1_{n}\otimes w_{*})\|_{\pi\otimes
1_{d}}+L\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|.\end{split}$

Putting this estimate in (5.6) gives the following estimate

$\begin{split}&\|w(t+1)-(W^{\infty}\otimes I_{d})w(t+1)\|_{\pi\otimes
1_{d}}\\\ &\leq\sigma_{W}(1+\alpha L\delta)\|(W^{\infty}\otimes
I_{d})w(t)-w(t)\|_{\pi\otimes 1_{d}}\\\ &\quad+\alpha
L\sigma_{W}\Big{(}\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}}\Big{)}\|\bar{w}(t)-w_{*}\|\\\
&\quad+\alpha\sigma_{W}\Big{(}L\delta{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|+\|\nabla
F(1_{n}\otimes w_{*})\|_{\pi\otimes 1_{d}}\Big{)}.\end{split}$

The proof is done. ∎

##  6\. Estimates on the distance between the average and the optimizer

In this section, we find an estimate of $\|\bar{w}(t+1)-w_{*}\|$ in terms of
$\|\bar{w}(t)-w_{*}\|$ and $\|w(t)-(W^{\infty}\otimes I_{d})w(t)\|_{\pi\otimes
1_{d}}$. We begin with recalling a classical result in the following lemma
(see e.g. [17]).

######  Lemma 6.1.

Assume that $f$ is $\beta$-strongly convex and $L$-smooth. Then

$\langle\nabla f(x)-\nabla
f(y),~{}x-y\rangle\geq\frac{L\beta}{L+\beta}\|x-y\|^{2}+\frac{1}{L+\beta}\|\nabla
f(x)-\nabla f(y)\|^{2}$

holds for all $x,y\in\mathbb{R}^{d}$.

Now we state the main result of this section.

######  Proposition 6.2.

Assume that (F1) and (F2) hold, and $f$ is $\beta$-strongly convex, and that
$\kappa(t)\geq 1$ for all $t\geq 0$. Let $\gamma=\frac{\beta
L}{L+\beta}\in(0,1)$. Then, for $\alpha\in\Big{(}0,\frac{2}{L+\beta}\Big{]}$,
we have the following estimates

$\begin{split}\|\bar{w}(t+1)-w_{*}\|&\leq\Big{(}1-\gamma\alpha+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\Big{)}\|\bar{w}(t)-w_{*}\|\\\
&\quad+\frac{\alpha L\delta}{n}\|(W^{\infty}\otimes
I_{d})w(t)-w(t)\|_{\pi\otimes 1_{d}}+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|.\end{split}$ (6.1)

where $w_{*}$ is the minimizer of the problem (1.1).

###### Proof.

From (2.3) we find

$\begin{split}\bar{w}(t+1)&={\frac{1}{n}(1_{n}^{\top}\otimes
I_{d})w(t+1)=\frac{1}{n}(1_{n}^{\top}\otimes I_{d})(W\otimes
I_{d})x(t)=\frac{1}{n}(1_{n}^{\top}\otimes I_{d})x(t)}\\\
&=\frac{1}{n}(1_{n}^{\top}\otimes I_{d})(w(t)-\alpha\nabla F(z(t)))\\\
&=\bar{w}(t)-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla f_{i}(z_{i}(t))\\\
&=\bar{w}(t)-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}\left(\frac{w_{i}(t)}{y_{i}(t)}\right).\end{split}$

Let us write the above term as

$\begin{split}\bar{w}(t+1)-w_{*}&=\bar{w}(t)-w_{*}-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}(\bar{w}(t))+\frac{\alpha}{n}\sum_{i=1}^{n}\left(\nabla
f_{i}(\bar{w}(t))-\nabla
f_{i}\left(\frac{w_{i}(t)}{y_{i}(t)}\right)\right).\end{split}$ (6.2)

Using Lemma 6.1, we have

$\begin{split}&\|\bar{w}(t)-w_{*}-\alpha\nabla f(\bar{w}(t))\|^{2}\\\
&=\|\bar{w}(t)-w_{*}\|^{2}-2\alpha\langle\bar{w}(t)-w_{*},~{}\nabla
f(\bar{w}(t))\rangle+\alpha^{2}\|\nabla f(\bar{w}(t))\|^{2}\\\
&\leq\|\bar{w}(t)-w_{*}\|^{2}-\frac{2\alpha\beta
L}{L+\beta}\|\bar{w}(t)-w_{*}\|^{2}-\frac{2\alpha}{L+\beta}\|\nabla
f(\bar{w}(t))\|^{2}+\alpha^{2}\|\nabla f(\bar{w}(t))\|^{2}.\end{split}$

Since $\alpha\leq\frac{2}{L+\beta}$, the above inequality gives

$\begin{split}\|\bar{w}(t)-w_{*}-\alpha\nabla
f(\bar{w}(t))\|^{2}&\leq\Big{(}1-\frac{2\alpha\beta
L}{L+\beta}\Big{)}\|\bar{w}(t)-w_{*}\|^{2}\\\ &\leq\Big{(}1-\frac{\alpha\beta
L}{L+\beta}\Big{)}^{2}\|\bar{w}(t)-w_{*}\|^{2}.\end{split}$

Hence we have

$\left\|\bar{w}(t)-w_{*}-\frac{\alpha}{n}\sum_{i=1}^{n}\nabla
f_{i}(\bar{w}(t))\right\|\leq(1-\gamma\alpha)\|\bar{w}(t)-w_{*}\|,$ (6.3)

where $\gamma=\frac{\beta L}{L+\beta}\in(0,1)$. In order to esimate the right-
most term of (6.2), we use (4.1) to have

$\left\|\frac{\alpha}{n}\sum_{i=1}^{n}\left(\nabla f_{i}(\bar{w}(t))-\nabla
f_{i}\left(\frac{w_{i}(t)}{y_{i}(t)}\right)\right)\right\|\leq\frac{\alpha
L}{n}\sum_{i=1}^{n}\left\|\bar{w}(t)-\frac{w_{i}(t)}{y_{i}(t)}\right\|,$ (6.4)

whose right hand side is estimated as

$\begin{split}\sum_{i=1}^{n}\Big{\|}\bar{w}(t)-\frac{w_{i}(t)}{y_{i}(t)}\Big{\|}&\leq\Big{(}\sum_{i=1}^{n}\pi_{i}\Big{)}^{1/2}\Big{(}\sum_{i=1}^{n}\frac{1}{\pi_{i}}\Big{\|}\bar{w}(t)-\frac{w_{i}(t)}{y_{i}(t)}\Big{\|}^{2}\Big{)}^{1/2}\\\
&=\|1_{n}\otimes\bar{w}(t)-z(t)\|_{\pi\otimes 1_{d}}.\end{split}$

Gathering the estimates (6.3) and (6.4) in (6.2) we find

$\|\bar{w}(t+1)-w_{*}\|\leq(1-\gamma\alpha)\|\bar{w}(t)-w_{*}\|+\frac{\alpha
L}{n}\|1_{n}\otimes\bar{w}(t)-z(t)\|_{\pi\otimes 1_{d}}.$

Combining this with Lemma 5.1 gives the following estimate

$\begin{split}\|\bar{w}(t+1)-w_{*}\|&\leq\Big{(}1-\gamma\alpha+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\Big{)}\|\bar{w}(t)-w_{*}\|\\\
&\quad+\frac{\alpha L\delta}{n}\|(W^{\infty}\otimes
I_{d})w(t)-w(t)\|_{\pi\otimes 1_{d}}+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|.\end{split}$

The proof is done. ∎

##  7\. Uniform boundedness of the sequence

Now we shall use the recursive estimates of the previous sections to establish
the uniform boundedness property of the sequence $\\{w_{k}(t)\\}$. For the
proof, we recall the estimates of the sequences $A_{t}=\|\bar{w}(t)-w_{*}\|$
and $B_{t}=\|(W^{\infty}\otimes I_{d})w(t)-w(t)\|_{\pi\otimes 1_{d}}$ given by
Propositions 5.2 and 6.2:

$A_{t+1}\leq(1-\gamma\alpha+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}})A_{t}+\frac{\alpha
L\delta}{n}B_{t}+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|$ (7.1)

and

$\begin{split}B_{t+1}&\leq\sigma_{W}(1+\alpha L\delta)B_{t}+\sigma_{W}(\alpha
L)\textbf{D}_{1}A_{t}+\alpha\sigma_{W}\textbf{D}_{2},\end{split}$ (7.2)

where $\textbf{D}_{1}=D_{1}[0]$ and $\textbf{D}_{2}=D_{2}[0]$. Now we
establish the uniform boundedness result of the sequence
$\\{(A_{t},B_{t})\\}_{t\in\mathbb{N}_{0}}$.

###### Proof of Theorem 4.2.

Take a value $t_{0}\in\mathbb{N}$ such that for $t\geq t_{0}$ we have
$(L\delta/n){\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\leq\gamma/2$. Choose $R>0$ as

$R=\max\Big{\\{}A_{t_{0}},~{}\frac{B_{t_{0}}}{b},~{}2\|w_{*}\|,~{}\frac{\sigma_{W}\alpha\textbf{D}_{2}}{b(1-\sigma_{W})-\alpha
L\sigma_{W}(\delta
b+\delta{\|1_{n}-n\pi\|_{\pi}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}})}\Big{\\}}.$

By an inductive argument, we will show that

$A_{t}\leq R\quad\textrm{and}\quad B_{t}\leq bR$ (7.3)

for all $t\geq t_{0}$. Assume that $A_{t}\leq R$ and $B_{t}\leq bR$ for some
$t\geq t_{0}$. Then we use (7.1) to deduce

$\begin{split}A_{t+1}&\leq(1-\gamma\alpha/2)R+\frac{\alpha
L\delta}{n}bR+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}\|w_{*}\|\\\
&=\Big{(}1-\Big{(}\gamma/2-(L\delta/n)b\Big{)}\alpha\Big{)}R+\frac{\gamma\alpha}{2}\cdot\frac{R}{2}\\\
&=R.\end{split}$

Next we estimate $B_{t+1}$ using (7.2) as

$\begin{split}B_{t+1}&\leq\sigma_{W}(1+\alpha L\delta)bR+\sigma_{W}\alpha
L\textbf{D}_{1}R+\sigma_{W}\alpha\textbf{D}_{2}\\\ &\leq\sigma_{W}(1+\alpha
L\delta)bR+\sigma_{W}\alpha
L\Big{(}\delta{\|1_{n}-n\pi\|_{\pi}}+\sqrt{\sum_{j=1}^{n}\frac{1}{\pi_{j}}}\Big{)}R+\sigma_{W}\alpha\textbf{D}_{2}\\\
&\leq bR.\end{split}$

The proof is done. ∎

##  8\. Convergence estimates

In this section, we prove the main convergence result of the gradient-push
algorithm stated in Theorem 4.3. For this aim, we prepare the following two
basic lemmas to analyze further the sequential estimates (7.1) and (7.2) of
$A_{t}$ and $B_{t}$.

######  Lemma 8.1.

Assume that a sequence $\\{Y_{t}\\}_{t\geq 0}\subset\mathbb{R}$ satisfies

$Y_{t+1}\leq(1-\alpha)Y_{t}+C\quad\forall t\geq 0$ (8.1)

for some $C>0$ and $\alpha\in(0,1)$. Then we have

$Y_{t}\leq(1-\alpha)^{t}Y_{0}+\frac{C}{\alpha}.$

###### Proof.

Using (8.1) iteratively, we have

$\begin{split}Y_{t}&\leq(1-\alpha)^{t}Y_{0}+C\sum_{k=0}^{t-1}(1-\alpha)^{k}.\\\
&\leq(1-\alpha)^{t}Y_{0}+\frac{C}{\alpha},\end{split}$

which proves the lemma. ∎

######  Lemma 8.2.

Assume that a sequence $\\{Y_{t}\\}_{t\geq 0}\subset\mathbb{R}$ satisfies

$Y_{t+1}\leq(1-\alpha)Y_{t}+C\rho^{t}\quad\forall t\geq 0$ (8.2)

for some $C>0$, $\alpha\in(0,1)$ and $\rho\in(0,1)$. Then we have

$Y_{t}\leq(1-\alpha)^{t}Y_{0}+Ct\left(\max\\{1-\alpha,\rho\\}\right)^{t-1}.$

###### Proof.

Making use of (8.2) recursively, we find

$\displaystyle Y_{t}$
$\displaystyle\leq(1-\alpha)^{t}Y_{0}+C\sum_{k=0}^{t-1}(1-\alpha)^{k}\rho^{t-1-k}$
$\displaystyle\leq(1-\alpha)^{t}Y_{0}+C\sum_{k=0}^{t-1}\left(\max\\{1-\alpha,\rho\\}\right)^{t-1}$
$\displaystyle=(1-\alpha)^{t}Y_{0}+Ct\left(\max\\{1-\alpha,\rho\\}\right)^{t-1}.$

The proof is done. ∎

Now we are ready to establish the main convergence result.

###### Proof of Theorem 4.3.

Let $R:=\sup_{t\geq 0}A_{t}$. By (7.2), we get

$\begin{split}B_{t+1}&\leq\sigma_{W}(1+\alpha L)B_{t}+\sigma_{W}(\alpha
L)\textbf{D}_{1}R+\alpha\sigma_{W}\textbf{D}_{2}\\\ &\leq\rho
B_{t}+\alpha\sigma_{W}\bar{R}\quad\textrm{for all}~{}t\geq 0,\end{split}$

where we have let $\rho=\sigma_{W}(1+\alpha L)$ and
$\bar{R}=L\textbf{D}_{1}R+\textbf{D}_{2}$. Using this we obtain

$\begin{split}B_{t}&\leq\rho^{t}B_{0}+\Big{(}\rho^{t-1}+\rho^{t-2}+\cdots+1\Big{)}\alpha\sigma_{W}\bar{R}\\\
&\leq\rho^{t}B_{0}+\frac{\alpha\sigma_{W}\bar{R}}{1-\rho},\end{split}$

which proves (4.6). Using this inequality in (7.1) we have

$\begin{split}A_{t+1}&\leq(1-\gamma\alpha)A_{t}+\frac{\alpha
L\delta}{n}\rho^{t}B_{0}+\alpha^{2}\frac{L\delta}{n}\frac{\sigma_{W}\bar{R}}{1-\rho}+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}(\|w_{*}\|+R).\end{split}$

To analyze this inequality, we consider three sequences
$A_{t}^{1},A_{t}^{2},A_{t}^{3}$ such that for $t\geq 0$,

$\begin{split}A_{t+1}^{1}&=(1-\gamma\alpha)A_{t}^{1}+\alpha^{2}\frac{L\delta}{n}\frac{\sigma_{W}\bar{R}}{1-\rho}\\\
A_{t+1}^{2}&=(1-\gamma\alpha)A_{t}^{2}+\frac{\alpha
L\delta}{n}\rho^{t}B_{0}\\\
A_{t+1}^{3}&=(1-\gamma\alpha)A_{t}^{3}+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}\sigma_{W}^{t}}(\|w_{*}\|+R),\end{split}$

with initial values $A_{0}^{1}=A_{0}$, $A_{0}^{2}=0$, and $A_{0}^{3}=0$. We
use Lemma 8.1 and Lemma 8.2 to analyze these sequences to find

$\begin{split}A_{t}^{1}&\leq(1-\gamma\alpha)^{t}A_{0}+\frac{\alpha
L\delta}{n\gamma}\frac{\sigma_{W}\bar{R}}{1-\rho}\\\
A_{t}^{2}&\leq\frac{\alpha
L\delta}{n}B_{0}t\Big{[}\max\\{1-\gamma\alpha,\rho\\}\Big{]}^{t-1}\\\
A_{t}^{3}&\leq\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}}(\|w_{*}\|+R)t\Big{[}\max\\{1-\gamma\alpha,e^{-c}\\}\Big{]}^{t-1}.\end{split}$

Collecting the above estimates, we get

$\begin{split}A_{t}&\leq(1-\gamma\alpha)^{t}A_{0}+\frac{\alpha
L\delta}{n}B_{0}t\Big{[}\max\\{1-\gamma\alpha,\rho\\}\Big{]}^{t-1}\\\
&\quad+\frac{\alpha
L\delta}{n}{\|1_{n}-n\pi\|_{\pi}}(\|w_{*}\|+R)t\Big{[}\max\\{1-\gamma\alpha,e^{-c}\\}\Big{]}^{t-1}+\frac{\alpha
L\delta}{n\gamma}\frac{\sigma_{W}\bar{R}}{1-\rho}.\end{split}$

The proof is done. ∎

##  9\. Numerical experiments

Here we provide numerical results for the gradient-push algorithm (2.2) that
support our theoretical convergence result. For all experiments, we set
$x_{i}(0)=1_{d}$ $(i=1,\dots,n)$, $d=5,n=10$, and generated a random directed
graph $G$ with $n$ vertices by letting each possible arc to occur
independently with probability $p=0.7$, except for the self-loops, which must
exist with probability 1. Then the matrix $W$ would be naturally determined by
(2.1). In the first example, we consider the least square parameter estimation
problem where each cost is convex. In the second example, we consider local
cost of the form $f_{j}(x)=\frac{1}{2}x^{T}A_{j}x+B_{j}^{T}x$ where $A_{j}$
may not be a positive semidefinite matrix.

###  9.1. Convex local cost case

We consider the least square parameter estimation problem

$f(x)=\frac{1}{2n}\sum_{j=1}^{n}\|A_{j}x-b_{j}\|^{2}.$

Here $A_{j}$ and $b_{j}$ are $3\times d$, $3\times 1$ matrices respectively,
with i.i.d. entries drawn from the standard normal distribution. It is well
known that the minimizer of $f$ is given by
$x^{*}=\left(\sum\limits_{j=1}^{n}A_{j}^{\top}A_{j}\right)^{-1}\sum\limits_{j=1}^{n}A_{j}^{\top}b_{j}$.
Figure 1 shows the graph of $\sum\limits_{i=1}^{n}\|z_{i}(t)-x^{*}\|^{2}$ with
respect to the iteration $t$, for $\alpha=10^{-1},10^{-2},10^{-3},10^{-4}$. As
expected, the limiting error seems to be proportional to the value of
$\alpha$.

Figure 1. Performance of NEAR-DGD for the convex local cost case.

###  9.2. Nonconvex local cost case

Here we consider the following problem

$f(x)=\frac{1}{n}\sum_{j=1}^{n}f_{j}(x),$

where $f_{j}(x)=\frac{1}{2}x^{T}(I+C_{j})x+d_{j}^{T}x$. Here $C_{j}$ is a
symmetric $d\times d$ matrix and $d_{j}\in\mathbb{R}^{d}$ for each $1\leq
j\leq n$, with i.i.d. entries(excluding the pairs that must be equal because
of the symmetry condition) drawn from the standard normal distribution. If the
resulting $f$ is not convex, then all random entries are sampled again. The
minimizer of $f$ is given by
$x^{*}=-\left(\sum_{j=1}^{N}(I+C_{j})\right)^{-1}\sum_{j=1}^{N}d_{j}$. Figure
2 shows the graph of $\sum\limits_{i=1}^{n}\|z_{i}(t)-x^{*}\|^{2}$ with
respect to the iteration $t$, for $\alpha=10^{-1},10^{-2},10^{-3},10^{-4}$.
Although our analysis does not treat the case where some $f_{j}$ may not be
convex, the limiting error seems to be proportional to the value of $\alpha$.

Figure 2. Performance of NEAR-DGD for the nonconvex local cost case.

## Acknowledgments

The work of Woocheol Choi was supported by the National Research Foundation of
Korea NRF- 2016R1A5A1008055 and Grant NRF-2021R1F1A1059671. The work of Doheon
Kim was supported by the National Research Foundation of Korea(NRF) grant
funded by the Korea government(MSIT) (No. RS-2022-00166699). Doheon Kim is
grateful for support by the Open KIAS Center at Korea Institute for Advanced
Study. The work of Seok-Bae Yun was supported by Samsung Science and
Technology Foundation under Project Number SSTF-BA1801-02.

## References

  * [1] P. A. Forero, A. Cano, and G. B. Giannakis, “”Consensus-based distributed support vector machines,”” Journal of Machine Learning Research, vol. 11, pp. 1663–-1707, 2010.
  * [2] H. Raja and W. U. Bajwa, “”Cloud K-SVD: A collaborative dictionary learning algorithm for big, distributed data,”” IEEE Transactions on Signal Processing, vol. 64, no. 1, pp. 173–-188, Jan. 2016.
  * [3] T. Yang, X. Yi, J. Wu, Y. Yuan, D. Wu, Z. Meng, Y. Hong, H. Wang, Z. Lin, and K. H. Johansson, “”A survey of distributed optimization,”” Annual Reviews in Control, vol. 47, pp. 278 –- 305, 2019.
  * [4] L. Bottou, F. E. Curtis, and J. Nocedal, “”Optimization methods for large-scale machine learning,”” SIAM Review, vol. 60, no. 2, pp. 223–-311, 2018.
  * [5] Bullo, F., Cortes, J., Martinez, S.: Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms, vol. 27. Princeton University Press, Princeton (2009)
  * [6] W. Ren, Consensus Based Formation Control Strategies for Multi-Vehicle Systems, in Proceedings of the Amer-ican Control Conference, 2006, pp. 4237–-4242.
  * [7] Y. Cao, W. Yu, W. Ren, and G. Chen, An overview of recent progress in the study of distributed multi-agent coordination, IEEE Trans Ind. Informat., 9 (2013), pp. 427–438
  * [8] W. Choi, D. Kim, S. Yun, Convergence results of a nested decentralized gradient method for non-strongly convex problems. J. Optim. Theory Appl. 195 (2022), no. 1, 172–204.
  * [9] W. Choi, J. Kim, On the convergence of decentralized gradient descent with diminishing stepsize, revisited, arXiv:2203.09079.
  * [10] G. B. Giannakis, V. Kekatos, N. Gatsis, S.-J. Kim, H. Zhu, and B. Wollenberg, Mon-itoring and optimization for power grids: A signal processing perspective, IEEE Signal Processing Mag., 30 (2013), pp. 107–128,
  * [11] V. Kekatos and G. B. Giannakis, Distributed robust power system state estimation, IEEE Trans. Power Syst., 28 (2013), pp. 1617–1626,
  * [12] K. I. Tsianos, S. Lawlor, and M. G. Rabbat, Consensus-based distributed optimization: Practical issues and applications in large-scale machine learning, in Proceedings of the IEEE Allerton Conference on Communication, Control, and Computing, IEEE, New York, 2012, pp. 1543–1550,
  * [13] M. Akbari, B. Gharesifard, and T. Linder, “Distributed online convex optimization on time-varying directed graphs,” IEEE Trans. Control Netw. Syst., vol. 4, no. 3, pp. 417–428, Sep. 2017.
  * [14] M. Assran, N. Loizou, N. Ballas, and M. Rabbat, “Stochastic gradient push for distributed deep learning,” in 36th International Conference on Machine Learning. Jun. 2019, vol. 97, pp. 344–353, PMLR.
  * [15] Bazerque, J.A., Giannakis, G.B.: Distributed spectrum sensing for cognitive radio networks by exploiting sparsity. IEEE Trans. Signal Process. 58(3), 1847–1862 (2010)
  * [16] Berahas, A.S., Bollapragada, R., Keskar, N.S., Wei, E.: Balancing communication and computation in distributed optimization. IEEE Trans. Autom. Control 64(8), 3141–3155 (2018)
  * [17] S. Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3–4):231–357, 2015.
  * [18] A. I. Chen and A. Ozdaglar, “A fast distributed proximal-gradient method,” in Communication, Control, and Computing (Allerton), 2012 50th Annual Allerton Conference on. IEEE, 2012, pp. 601–608.
  * [19] D. Jakovetic, J. Xavier, and J. M. F. Moura, “Fast Distributed Gradient Methods,” IEEE Transactions on Automatic Control, vol. 59, no. 5, pp. 1131–1146, 2014.
  * [20] D. Kempe, A. Dobra, and J. Gehrke, “”Gossip-based computation
  * [21] J. Kim, W. Choi, Gradient-push algorithm for distributed optimization with event-triggered communications, IEEE Access, vol. 11, pp. 517-534, 2023
  * [22] J. Li, C. Gu, Z. Wu Online distributed stochastic learning algorithm for convex optimization in time-varying directed networks , Neurocomputing 416 (2020) 85–94
  * [23] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48, 2009.
  * [24] A. Nedić and A. Olshevsky, “Stochastic gradient-push for strongly convex functions on time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 61, no. 12, pp. 3936–3947, 2016.
  * [25] A. Nedić and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014.
  * [26] 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.
  * [27] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2018.
  * [28] A. H. Sayed, Diffusion adaptation over networks. Academic Press Library in Signal Processing, 2013, vol. 3.
  * [29] Schizas, I.D., Giannakis, G.B., Roumeliotis, S.I., Ribeiro, A.: Consensus in ad hoc WSNs with noisy links—part II: distributed estimation and smoothing of random signals. IEEE Trans. Signal Process. 56(4), 1650–1666 (2008)
  * [30] E. Seneta. Non-negative matrices and Markov chains, 2nd Ed. Springer-Verlag New York (1981).
  * [31] W. Shi, Q. Ling, G. Wu, W. Yin, Extra: an exact first-order algorithm for decentralized consensus optimization. SIAM J. Optim. 25(2), 944–966 (2015)
  * [32] W. Shi, Q. Ling, K. Yuan, G. Wu, W. Yin, On the linear convergence of theADMMin decentralized consensus optimization. IEEE Trans. Signal Process. 62(7), 1750–1761 (2014)
  * [33] T. Tatarenko, B. Touri, Non-convex distributed optimization. IEEE Trans. Automat. Control 62 (2017), no. 8, 3744–3757.
  * [34] K. Tsianos, S. Lawlor, and M. G. Rabbat, ”Communication/computation tradeoffs in consensus-based distributed optimization,” in Proc. Adv. Neural Inf. Process. Syst., 2012, pp. 1943–1951
  * [35] K. I. Tsianos, S. Lawlor, and M. G. Rabbat, “”Push-sum distributed dual averaging for convex optimization,”” in Proc. IEEE Conf. Dec. Control, Maui, HI, USA, 2012, pp. 5453–-5458.
  * [36] C. Xi and U. A. Khan, “DEXTRA: A fast algorithm for optimization over directed graphs,” IEEE Transactions on Automatic Control, vol. 62, no. 10, pp. 4980–4993, Oct. 2017.
  * [37] R. Xin, A. K. Sahu, U. A. Khan, and S. Kar, “Distributed stochastic optimization with gradient tracking over strongly-connected networks,” in 58th IEEE Conference on Decision and Control, Dec. 2019, pp. 8353–8358.
  * [38] R. Xin and U. A. Khan, “A linear algorithm for optimization over directed graphs with geometric convergence,” IEEE Control Systems Letters, vol. 2, no. 3, pp. 315–320, 2018.
  * [39] 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, Sep. 2016.
  * [40] D. Yuan, S. Xu, J. Lu, Gradient-free method for distributed multi-agent optimization via push-sum algorithms, Internat. J. Robust Nonlinear Control 25 (2015), no. 10, 1569–1580.
  * [41] H. Taheri, A. Mokhtari, H. Hassani, and R. Pedarsani, Quantized decentralized stochastic learning over directed graphs. In International Conference on Machine Learning, 2020.
  * [42] J. Li, C. Gu, Z. Wu, Online distributed stochastic learning algorithm for convex optimization in time-varying directed networks, Neurocomputing (2019).
  * [43] T. Yang et al., ”A Distributed Algorithm for Economic Dispatch Over Time-Varying Directed Networks With Delays,” in IEEE Transactions on Industrial Electronics, vol. 64, no. 6, pp. 5095-5106, June 2017.
  * [44] M. S. Assran and M. G. Rabbat, ”Asynchronous Gradient Push,” in IEEE Transactions on Automatic Control, vol. 66, no. 1, pp. 168-183, Jan. 2021.
  * [45] W. Yu, H. Liu, W. Zheng, Y. Zhu, Distributed discrete-time convex optimization with nonidentical local constraints over time-varying unbalanced directed graphs. Automatica J. IFAC 134 (2021).
  * [46] M. Akbari, B. Gharesifard and T. Linder, ”Distributed Online Convex Optimization on Time-Varying Directed Graphs,” in IEEE Transactions on Control of Network Systems, vol. 4, no. 3, pp. 417-428, Sept. 2017.
  * [47] C. Wang, S. Xu, D. Yuan, B. Zhang and Z. Zhang, ”Push-Sum Distributed Online Optimization With Bandit Feedback,” in IEEE Transactions on Cybernetics, vol. 52, no. 4, pp. 2263-2273, April 2022.