# Accelerated Gradient Tracking over Time-varying Graphs for Decentralized
Optimization

Huan Li  Zhouchen Lin

###### Abstract

Decentralized optimization over time-varying graphs has been increasingly
common in modern machine learning with massive data stored on millions of
mobile devices, such as in federated learning. This paper revisits and extends
the widely used accelerated gradient tracking. We prove the ${\cal
O}(\frac{\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\sqrt{\frac{L}{\epsilon}})$ and
${\cal
O}((\frac{\gamma}{1-\sigma_{\gamma}})^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
complexities for the practical single loop accelerated gradient tracking over
time-varying graphs when the problems are nonstrongly convex and strongly
convex, respectively, where $\gamma$ and $\sigma_{\gamma}$ are two common
constants charactering the network connectivity, $\epsilon$ is the desired
precision, and $L$ and $\mu$ are the smoothness and strong convexity
constants, respectively. Our complexities improve significantly on the ones of
${\cal O}(\frac{1}{\epsilon^{5/7}})$ and ${\cal
O}((\frac{L}{\mu})^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon})$
proved in the original literature only for static graph. When combining with a
multiple consensus subroutine, the dependence on the network connectivity
constants can be further improved. When the network is time-invariant, our
complexities exactly match the lower bounds without hiding any poly-
logarithmic factor for both nonstrongly convex and strongly convex problems.

##  1 Introduction

Distributed optimization has emerged as a promising framework in machine
learning motivated by large-scale data being produced or stored in a network
of nodes. Due to the popularity of smartphones and their growing computational
power, time-varying graphs are increasingly common in modern distributed
optimization. A typical example is the federated learning (Li et al., 2020c;
Kairouz et al., 2019), which involves training a global statistical model from
data stored on millions of mobile devices. The physical constraints on each
device typically result in only a small fraction of the devices being active
at once, and it is possible for an active device to drop out at a given time
(Bonawitz et al., 2019). Challengingly, the communication links in the network
may vary with time, and at each time the network may be even unconnected.
Although centralized network is the predominant topology in most machine
learning systems, such as TensorFlow, decentralized network has been a
potential alternative because it reduces the high communication cost on the
central server (Lian et al., 2017). This motivates us to study decentralized
optimization over time-varying graphs. In this paper, we consider the
following convex optimization problem:

$\displaystyle\min_{x\in\mathbb{R}^{n}}F(x)=\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(x).$
(1)

where the local objective functions $f_{(i)}$ are distributed separately over
a network of nodes. The network is mathematically represented as a sequence of
time-varying graphs $\\{\mathcal{G}^{0},\mathcal{G}^{1},...\\}$, and each
graph instance $\mathcal{G}^{k}$ consists of a fixed set of agents
$\mathcal{V}=\\{1,...,m\\}$ and a set of time-varying edges $\mathcal{E}^{k}$.
Agents $i$ and $j$ can exchange information at time $k$ if and only if
$(i,j)\in\mathcal{E}^{k}$. Each agent $i$ privately holds a local objective
$f_{(i)}$, and makes its decision only based on the local computations on
$f_{(i)}$ and the local information received from its neighbors. The local
objective functions are assumed to be smooth. We consider both strongly convex
and nonstrongly convex objectives in this paper.

Although decentralized optimization over static graph has been well studied,
for example, lower bounds on communication rounds and gradient or stochastic
gradient computations for strongly convex and smooth problems are well-known
(Scaman et al., 2017, 2019; Hendrikx et al., 2020), and optimal accelerated
algorithms with upper bounds exactly matching the lower bounds are developed
(Koralev et al., 2020; Li et al., 2020b), for the time-varying graphs, the
literature is much scarcer. It remains an open problem on how to design
practical accelerated methods with the optimal dependence on the precision
$\epsilon$ and the condition number of the objectives, which exactly matches
that of the centralized counterparts. In this paper, we aim to address this
question.

###  1.1 Literature Review

In this section, we briefly review the decentralized algorithms over static
graph and time-varying graphs, and our focus is on the accelerated methods.
Tables 1 and 2 sum up the complexity comparisons of the state-of-the-art ones,
as well as the gradient tracking based methods.

####  1.1.1 Decentralized Optimization over Static Graph

Decentralized optimization has been studied for a long time (Bertsekas, 1983;
Tsitsiklis et al., 1986). The representative decentralized algorithms include
distributed gradient/subgradient descent (Nedić & Ozdaglar, 2009; Nedić, 2011;
Ram et al., 2010; Yuan et al., 2016), EXTRA (Shi et al., 2015b, a; Li & Lin,
2020b), gradient tracking (Nedić et al., 2017; Qu & Li, 2018; Xu et al., 2015;
Xin et al., 2018), NIDS (Li et al., 2019), as well as the dual based methods,
such as dual ascent (Terelius et al., 2011), dual averaging (Duchi et al.,
2012), ADMM (Iutzeler et al., 2016; Makhdoumi & Ozdaglar, 2017; Aybat et al.,
2018), and the primal-dual method (Lan et al., 2020; Scaman et al., 2018; Hong
et al., 2017; Jakovetić, 2019). Recently, accelerated decentralized methods
have gained significant attention due to their provable faster convergence
rates.

_Accelerated Methods for Strongly Convex and Smooth Decentralized
Optimization._ The accelerated methods which can be applied to strongly convex
and smooth decentralized optimization include the accelerated distributed
Nesterov gradient descent (Acc-DNGD) (Qu & Li, 2020), the robust distributed
accelerated stochastic gradient method (Fallah et al., 2019), the multi-step
dual accelerated method (Scaman et al., 2017, 2019), accelerated penalty
method (APM) (Li et al., 2020a; Dvinskikh & Gasnikov, 2019), the multi-
consensus decentralized accelerated gradient descent (Mudag) (Ye et al.,
2020a, b), accelerated EXTRA (Li & Lin, 2020b; Li et al., 2020b), and the
accelerated proximal alternating predictor-corrector method (APAPC) (Koralev
et al., 2020). Scaman et al. (2017, 2019) proved the
$\varOmega(\sqrt{\frac{L}{\mu(1-\sigma)}}\log\frac{1}{\epsilon})$ (see the
notations in Section 1.3) communication complexity lower bound and the
$\varOmega(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$ gradient computation
complexity lower bound. To the best of our knowledge, only APAPC combined with
Chebyshev acceleration (CA) (Arioli & Scott, 2014) exactly achieves these
lower bounds without hiding any poly-logarithmic factor. Although gradient
tracking has been widely used in practice, its accelerated variant, Acc-DNGD,
only has the ${\cal
O}((\frac{L}{\mu})^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon})$
complexity originally proved in (Qu & Li, 2020).

_Accelerated Methods for Nonstrongly Convex and Smooth Decentralized
Optimization._ The accelerated methods for nonstrongly convex and smooth
problems are much scarcer. Examples include the distributed Nesterov gradient
with consensus (Jakovetić et al., 2014), Acc-DNGD (Qu & Li, 2020), APM (Li et
al., 2020a; Dvinskikh & Gasnikov, 2019), accelerated EXTRA (Li & Lin, 2020b),
and the accelerated dual ascent (Uribe et al., 2021), where the last one adds
a small regularizer to translate the problem to a strongly convex and smooth
one. Scaman et al. (2019) proved the
$\varOmega(\sqrt{\frac{L}{\epsilon(1-\sigma)}})$ communication complexity
lower bound and the $\varOmega(\sqrt{\frac{L}{\epsilon}})$ gradient
computation complexity lower bound. To the best of our knowledge, there is no
method matching these lower bounds exactly without hiding any poly-logarithmic
factor. APM comes close to this target, but with an additional ${\cal
O}(\log\frac{1}{\epsilon})$ factor in the communication complexity. Acc-DNGD
only has the ${\cal O}(\frac{1}{\epsilon^{5/7}})$ complexity originally proved
in (Qu & Li, 2020)111The dependence on $1-\sigma$, a small constant
charactering the network connectivity, was not explicitly given in (Qu & Li,
2020).. Xu et al. (2020) proposed an accelerated primal dual method, however,
their complexity remains ${\cal O}(\frac{1}{\epsilon})$.

Table 1: Comparisons among the state-of-the-art complexities of decentralized methods over static graph, as well as those of gradient tracking and its accelerated variant Acc-DNGD. Methods |  | gradient computation
---
complexity
| communication
---
complexity
| single or
---
double loop
Nonstrongly convex and smooth functions
| Gradient tracking
---
(Qu & Li, 2018)
${\cal O}\left(\frac{L}{\epsilon(1-\sigma)^{2}}\right)$ | ${\cal O}\left(\frac{L}{\epsilon(1-\sigma)^{2}}\right)$ | single loop
| Acc-DNGD
---
(Qu & Li, 2020)
${\cal O}\left(\frac{1}{\epsilon^{5/7}}\right)$ | ${\cal O}\left(\frac{1}{\epsilon^{5/7}}\right)$ | single loop
| APM
---
(Li et al., 2020a)
(Dvinskikh & Gasnikov, 2019)
${\cal O}\left(\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\epsilon(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | double loop
| Acc-EXTRA
---
(Li & Lin, 2020b)
${\cal O}\left(\sqrt{\frac{L}{\epsilon(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\epsilon(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | double loop
| Our results for Acc-GT
---
${\cal O}\left(\frac{1}{(1-\sigma)^{2}}\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\frac{1}{(1-\sigma)^{2}}\sqrt{\frac{L}{\epsilon}}\right)$ | single loop
| Our results for Acc-GT+CA
---
${\cal O}\left(\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\epsilon(1-\sigma)}}\right)$ | double loop
| Lower bounds
---
Scaman et al. (2019)
${\cal O}\left(\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\epsilon(1-\sigma)}}\right)$ | $\backslash$
Strongly convex and smooth functions
| Gradient tracking
---
(Alghunaim et al., 2020)
${\cal O}\left(\left(\frac{L}{\mu}+\frac{1}{(1-\sigma)^{2}}\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\frac{L}{\mu}+\frac{1}{(1-\sigma)^{2}}\right)\log\frac{1}{\epsilon}\right)$ | single loop
| Acc-DNGD
---
(Qu & Li, 2020)
${\cal O}\left(\left(\frac{L}{\mu}\right)^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\frac{L}{\mu}\right)^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon}\right)$ | single loop
| APAPC+CA
---
(Koralev et al., 2020)
${\cal O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\mu(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | double loop
| Our results for Acc-GT
---
${\cal O}\left(\sqrt{\frac{L}{\mu(1-\sigma)^{3}}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\mu(1-\sigma)^{3}}}\log\frac{1}{\epsilon}\right)$ | single loop
| Our results for Acc-GT+CA
---
${\cal O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\mu(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | double loop
| Lower bounds
---
Scaman et al. (2019)
${\cal O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\frac{L}{\mu(1-\sigma)}}\log\frac{1}{\epsilon}\right)$ | $\backslash$

####  1.1.2 Decentralized Optimization over Time-varying Graphs

Table 2: Comparisons among the state-of-the-art complexities of decentralized methods over time-varying graphs. We only compare with the methods working over $\gamma$-connected graphs. Methods |  | gradient computation
---
complexity
| communication
---
complexity
| single or
---
double loop
Nonstrongly convex and smooth functions
| APM
---
(Li et al., 2020a)
${\cal O}\left(\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\epsilon}}\log\frac{1}{\epsilon}\right)$ | double loop
| Our results for Acc-GT
---
${\cal O}\left(\frac{\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\frac{\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\sqrt{\frac{L}{\epsilon}}\right)$ | single loop
| Our results for Acc-GT+
---
multiple consensus
${\cal O}\left(\sqrt{\frac{L}{\epsilon}}\right)$ | ${\cal O}\left(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\epsilon}}\right)$ | double loop
Strongly convex and smooth functions
| DIGing
---
(Nedić et al., 2017)
${\cal O}\left(\sqrt{m}\left(\frac{L}{\mu}\right)^{1.5}\left(\frac{\gamma}{1-\sigma_{\gamma}}\right)^{2}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{m}\left(\frac{L}{\mu}\right)^{1.5}\left(\frac{\gamma}{1-\sigma_{\gamma}}\right)^{2}\log\frac{1}{\epsilon}\right)$ | single loop
| DAGD-C
---
(Rogozin et al., 2020)
${\cal O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\mu}}\left(\log\frac{1}{\epsilon}\right)^{2}\right)$ | double loop
| Our results for Acc-GT
---
${\cal O}\left(\left(\frac{\gamma}{1-\sigma_{\gamma}}\right)^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\frac{\gamma}{1-\sigma_{\gamma}}\right)^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | single loop
| Our results for Acc-GT+
---
multiple consensus
${\cal O}\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | double loop

We review the decentralized algorithms over time-varying graphs in two
sceneries. In the first scenery, the network may not be connected at every
time, but it is assumed to be $\gamma$-connected, which means that the joint
graph $\\{\mathcal{V},\cup_{r=k}^{k+\gamma-1}\mathcal{E}^{r}\\}$ is connected
for all $k=0,1,...$. In the second scenery, the network is assumed to be
connected at every time.

_Not Connected at Every Time but $\gamma$-connected._ In this scenery, DIGing
(that is, the gradient tracking method) (Nedić et al., 2017), PANDA (Maros &
Jalden, 2018, 2019), the time-varying $\mathcal{A}\mathcal{B}$/push-pull
method (Saadatniaki et al., 2020), the decentralized stochastic gradient
descent (SGD) (Koloskova et al., 2020), and the push-sum based method (Nedić &
Olshevsky, 2016, 2015; Nedić et al., 2017) are the representative non-
accelerated methods over time-varying graphs for strongly convex and smooth
objectives, as well as NEXT (Lorenzo & Scutari, 2016) and SONATA (Scutari &
Sun, 2019) for nonconvex problems. When combing with Nesterov’s acceleration,
to the best of our knowledge, the decentralized accelerated gradient descent
with consensus subroutine (DAGD-C) (Rogozin et al., 2020, 2021) is the only
accelerated method with explicit complexities in this general time-varying
setting. However, the communication complexity of DAGD-C has an additional
${\cal O}(\log\frac{1}{\epsilon})$ factor compared with the classical
centralized accelerated gradient method. For nonstrongly convex and smooth
problems, no literature studies the accelerated methods over time-varying
graphs. While APM (Li et al., 2020a) was originally designed for static graph,
it can be easily extended to the time-varying case. However, as introduced in
the previous section, APM also has an additional ${\cal
O}(\log\frac{1}{\epsilon})$ factor in the communication complexity.

_Connected at Every Time._ In this scenery, the literatures are rich and many
distributed methods originally designed over static graph, such as Acc-DNGD,
APM, and Mudag, can be directly used. Kovalev et al. (2021) proposed a dual
based method named ADOM with the state-of-the-art communication complexity of
${\cal O}(\frac{1}{1-\sigma}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$ for
strongly convex problems. However, ADOM needs to compute the gradient of
Fenchel conjugate of the local objectives, which is expensive, and ADOM can
not be used for nonstrongly convex problems.

###  1.2 Contributions

In this paper, we revisit the accelerated gradient tracking originally
proposed in (Qu & Li, 2020) and extend it to the time-varying graphs with
sharper complexities. We give our analysis over both static graph and time-
varying graphs in a unified framework. The former scenery provides the basis
and insights for the latter one. Our contributions are twofold:

  1. 1.

For the static graph, our contributions include:

    1. (a)

When the local objective functions are nonstrongly convex and smooth, we prove
the ${\cal O}(\frac{1}{(1-\sigma)^{2}}\sqrt{\frac{L}{\epsilon}})$ complexity
for the practical single loop accelerated gradient tracking (Acc-GT), which
significantly improves the existing ${\cal O}(\frac{1}{\epsilon^{5/7}})$ one
originally proved in (Qu & Li, 2020). When combing with Chebyshev
acceleration, we can improve the complexities to ${\cal
O}(\sqrt{\frac{L}{\epsilon(1-\sigma)}})$ for communications and ${\cal
O}(\sqrt{\frac{L}{\epsilon}})$ for gradient computations, which exactly match
the communication and gradient computation complexity lower bounds,
respectively. To the best of our knowledge, this is the first time that the
optimal upper bounds for nonstrongly convex problems are proved, which exactly
match the corresponding lower bounds without hiding any poly-logarithmic
factor.

    2. (b)

When the local objective functions are strongly convex and smooth, we prove
the ${\cal O}(\sqrt{\frac{L}{\mu(1-\sigma)^{3}}}\log\frac{1}{\epsilon})$
complexity for the practical single loop accelerated gradient tracking, which
improves the existing ${\cal
O}((\frac{L}{\mu})^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon})$ one
originally given in (Qu & Li, 2020). When combing with Chebyshev acceleration,
the complexities can be further improved to match the corresponding lower
bounds and existing optimal upper bounds.

  2. 2.

For the time-varying graphs, our contributions include:

    1. (a)

When the local objective functions are nonstrongly convex and smooth, we prove
the ${\cal
O}(\frac{\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\sqrt{\frac{L}{\epsilon}})$
complexity for the practical single loop accelerated gradient tracking. When
combing with a multiple consensus subroutine, our complexities can be improved
to ${\cal O}(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\epsilon}})$ for
communications and ${\cal O}(\sqrt{\frac{L}{\epsilon}})$ for gradient
computations. Our communication cost is lower than the state-of-the-art APM
(Li et al., 2020a) by a ${\cal O}(\log\frac{1}{\epsilon})$ factor, while our
gradient computation cost is the same as that of APM.

    2. (b)

When the local objective functions are strongly convex and smooth, we prove
the ${\cal
O}((\frac{\gamma}{1-\sigma_{\gamma}})^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
complexity for the practical single loop accelerated gradient tracking. When
combing with the multiple consensus subroutine, we can improve the
complexities to ${\cal
O}(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
for communications and ${\cal O}(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
for gradient computations. Our communication cost is lower than the state-of-
the-art DAGD-C (Rogozin et al., 2020) by a ${\cal O}(\log\frac{1}{\epsilon})$
factor, while our gradient computation cost remains the same as that of
DAGD-C.

###  1.3 Notations and Assumptions

Throughout this article, we denote $x_{(i)}$ to be the local variable for
agent $i$. We use the subscript $(i)$ to distinguish the $i$th element of $x$.
To write the algorithm in a compact form, we introduce the aggregate objective
function $f(\mathbf{x})$ with its aggregate variable
$\mathbf{x}\in\mathbb{R}^{m\times n}$ and aggregate gradient $\nabla
f(\mathbf{x})\in\mathbb{R}^{m\times n}$ as

$\displaystyle\qquad\begin{aligned}
f(\mathbf{x})=\sum_{i=1}^{m}f_{(i)}(x_{(i)}),\quad\mathbf{x}=\left(\begin{array}[]{c}x_{(1)}^{T}\\\
\vdots\\\ x_{(m)}^{T}\end{array}\right),\quad\nabla
f(\mathbf{x})=\left(\begin{array}[]{c}\nabla f_{(1)}(x_{(1)})^{T}\\\ \vdots\\\
\nabla f_{(m)}(x_{(m)})^{T}\end{array}\right).\end{aligned}$ (2)

Denote $\mathbf{x}^{k}$ to be the value at iteration $k$. For scalers, for
example, $\theta$, we use $\theta_{k}$ instead of $\theta^{k}$ to be the value
at iteration $k$, while the latter one is denoted to be its $k$th power. We
denote $\|\cdot\|$ to be the Frobenius norm for matrices and the $\ell_{2}$
Euclidean norm for vectors uniformly, and $\|\cdot\|_{2}$ as the spectral norm
of matrices. Denote $I$ as the identity matrix and $\mathbf{1}$ as the column
vector of $m$ ones. Denote $x^{*}$ as the optimal solution of problem (1).
Define the average variable across all the local variables at iteration $k$ as

$\displaystyle\overline{x}^{k}=\frac{1}{m}\sum_{i=1}^{m}x_{(i)}^{k},\quad\overline{y}^{k}=\frac{1}{m}\sum_{i=1}^{m}y_{(i)}^{k},\quad\overline{z}^{k}=\frac{1}{m}\sum_{i=1}^{m}z_{(i)}^{k},\quad\overline{s}^{k}=\frac{1}{m}\sum_{i=1}^{m}s_{(i)}^{k},$
(3)

where $x$, $y$, $z$, and $s$ will be used in the development of the algorithm.
Define operator $\Pi=I-\frac{\mathbf{1}\mathbf{1}^{T}}{m}$ to measure the
consensus violation such that

$\Pi\mathbf{x}=\left(\begin{array}[]{c}x_{(1)}^{T}-\overline{x}^{T}\\\
\cdots\\\ x_{(m)}^{T}-\overline{x}^{T}\\\ \end{array}\right).$ (4)

We make the following assumptions for each local objective function in problem
(1).

###### Assumption 1

  1. 1.

Each $f_{(i)}(x)$ is $\mu$-strongly convex: $f_{(i)}(y)\geq
f_{(i)}(x)+\left\langle\nabla
f_{(i)}(x),y-x\right\rangle+\frac{\mu}{2}\|y-x\|^{2}$. Especially, we allow
$\mu$ to be zero through this paper, and in this case we say $f_{(i)}(x)$ is
convex.

  2. 2.

Each $f_{(i)}(x)$ is $L$-smooth, that is, $f_{(i)}(x)$ is differentiable and
its gradient is $L$-Lipschitz continuous: $\|\nabla f_{(i)}(y)-\nabla
f_{(i)}(x)\|\leq L\|y-x\|$.

A direct consequence of the smoothness and convexity assumptions is the
following property (Nesterov, 2004):

$\displaystyle\frac{1}{2L}\|\nabla f_{(i)}(y)-\nabla f_{(i)}(x)\|^{2}\leq
f_{(i)}(y)-f_{(i)}(x)-\left\langle\nabla
f_{(i)}(x),y-x\right\rangle\leq\frac{L}{2}\|y-x\|^{2}.$

When the network is static, we make the following standard assumptions for the
weight matrix $W\in\mathbb{R}^{m\times m}$ associated to the network:

###### Assumption 2

  1. 1.

(Decentralized property) $W_{i,j}>0$ if and only if $(i,j)\in\mathcal{E}$ or
$i=j$. Otherwise, $W_{i,j}=0$.

  2. 2.

(Double stochasticity) $W\mathbf{1}=\mathbf{1}$ and
$\mathbf{1}^{T}W=\mathbf{1}^{T}$.

If the network is connected, Assumption 2 implies that the second largest
singular value $\sigma$ of $W$ is less than 1 (its largest one equals 1), that
is, $\sigma=\|W-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\|_{2}<1$. Moreover, we
have the following classical consensus contraction:

$\displaystyle\qquad\|\Pi
W\mathbf{x}\|=\left\|\left(W-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\right)\mathbf{x}\right\|=\left\|\left(W-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\right)\left(I-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\right)\mathbf{x}\right\|\leq\sigma\|\Pi\mathbf{x}\|.$
(5)

When the network is time-varying, each graph instance $\mathcal{G}^{k}$
associates with a weight matrix $W^{k}$. We follow (Nedić et al., 2017) to
denote

$W^{k,\gamma}=W^{k}W^{k-1}\cdots W^{k-\gamma+1}\mbox{ for any
}k\geq\gamma-1\quad\mbox{and}\quad W^{k,0}=I,$ (6)

and make the following standard assumptions for the sequence of weight
matrices $\\{W^{k}\\}_{k=0}^{\infty}$.

###### Assumption 3

  1. 1.

(Decentralized property) $W^{k}_{i,j}>0$ if and only if
$(i,j)\in\mathcal{E}^{k}$ or $i=j$. Otherwise, $W_{i,j}^{k}=0$.

  2. 2.

(Double stochasticity) $W^{k}\mathbf{1}=\mathbf{1}$ and
$\mathbf{1}^{T}W^{k}=\mathbf{1}^{T}$.

  3. 3.

(Joint spectrum property) There exists a constant integer $\gamma$ such that

$\sigma_{\gamma}<1,\quad\mbox{where}\quad\sigma_{\gamma}=\sup_{k\geq\gamma-1}\left\|W^{k,\gamma}-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\right\|_{2}.$

Assumption 3 is weaker than the assumption that every graph $\mathcal{G}^{k}$
is connected. A typical example of the weight matrix satisfying Assumption 3
is the Metropolis weight with the $\gamma$-connected graph sequence. The
former is defined as

$W_{ij}^{k}=\left\\{\begin{array}[]{ll}1/(1+\max\\{d_{i}^{k},d_{j}^{k}\\}),&\mbox{if
}(i,j)\in\mathcal{E}^{k},\\\ 0,&\mbox{if }(i,j)\neq\mathcal{E}^{k}\mbox{ and
}i\neq j,\\\ 1-\sum_{l\in\mathcal{N}_{(i)}^{k}}W_{il}^{k},&\mbox{if
}i=j,\end{array}\right.$

where $\mathcal{N}_{(i)}^{k}$ is the set of neighbors of agent $i$ at time
$k$, and $d_{i}^{k}=|\mathcal{N}_{(i)}^{k}|$ is the degree. The
$\gamma$-connected graph sequence is defined as follows (Nedić et al., 2017).

###### Definition 1

The time-varying undirected graph sequence
$\\{\mathcal{G}^{k}\\}_{k=0}^{\infty}$ is $\gamma$-connected if there exists
some positive integer $\gamma$ such that the undirected graph
$\\{\mathcal{V},\cup_{r=k}^{k+\gamma-1}\mathcal{E}^{r}\\}$ is connected for
all $k=0,1,...$.

When Assumption 3 holds, we have the following $\gamma$-step consensus
contraction:

$\|\Pi
W^{k,\gamma}\mathbf{x}\|\leq\sigma_{\gamma}\|\Pi\mathbf{x}\|,\qquad\mbox{for
any }k\geq\gamma-1.$ (7)

When the algorithm proceeds less than $\gamma$ steps, we only have

$\|\Pi W^{k,t}\mathbf{x}\|\leq\|\Pi\mathbf{x}\|,\qquad\mbox{for any }0\leq
t<\gamma\mbox{ and }k\geq t-1.$ (8)

##  2 Accelerated gradient tracking over Static Graph

We first review the gradient tracking and its accelerated variant, and then
give our new results.

###  2.1 Review of Gradient Tracking and its Acceleration

Gradient tracking (Nedić et al., 2017; Qu & Li, 2018; Xu et al., 2015; Xin et
al., 2018) keeps an auxiliary variable $s_{(i)}^{k}$ at each iteration for
each agent $i$ to track the average of the gradients $\nabla
f_{(j)}(x_{(j)}^{k})$ for all $j=1,...,m$, such that if $x_{(i)}^{k}$
converges to some point $x^{\infty}$, $s_{(i)}^{k}$ converges to
$\frac{1}{m}\sum_{i=1}^{m}\nabla f_{(i)}(x^{\infty})$. The auxiliary variable
is updated recursively as follows:

$\displaystyle
s_{(i)}^{k}=\sum_{j\in\mathcal{N}_{(i)}}W_{ij}s_{(j)}^{k-1}+\nabla
f_{(i)}(x_{(i)}^{k})-\nabla f_{(i)}(x_{(i)}^{k-1}),$

and each agent uses this auxiliary variable as the descent direction in the
general distributed gradient descent framework:

$\displaystyle
x_{(i)}^{k+1}=\sum_{j\in\mathcal{N}_{(i)}}W_{ij}x_{(j)}^{k}-\alpha
s_{(i)}^{k},$

where $\alpha$ is the step size. Writing gradient tracking in the compact
form, it reads as follows:

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

To further accelerate gradient tracking, Qu & Li (2020) employed Nesterov’s
acceleration technique (Nesterov, 2004) and proposed the following accelerated
distributed Nesterov gradient descent for nonstrongly convex problems:

$\displaystyle\mathbf{y}^{k}=\theta_{k}\mathbf{z}^{k}+(1-\theta_{k})\mathbf{x}^{k},$
(10a) $\displaystyle\mathbf{s}^{k}=W\mathbf{s}^{k-1}+\nabla
f(\mathbf{y}^{k})-\nabla f(\mathbf{y}^{k-1}),$ (10b)
$\displaystyle\mathbf{x}^{k+1}=W\mathbf{y}^{k}-\alpha\mathbf{s}^{k},$ (10c)
$\displaystyle\mathbf{z}^{k+1}=W\mathbf{z}^{k}-\frac{\alpha}{\theta_{k}}\mathbf{s}^{k}.$
(10d)

It can be checked that step (10c) is equivalent to the following one:

$\mathbf{x}^{k+1}=\theta_{k}\mathbf{z}^{k+1}+(1-\theta_{k})W\mathbf{x}^{k}.$

When strong convexity is assumed, Qu & Li (2020) replaced steps (10a) and
(10d) by the following two steps:

$\displaystyle\mathbf{y}^{k}=\frac{\mathbf{x}^{k}+\theta\mathbf{z}^{k}}{1+\theta},\qquad\mathbf{z}^{k+1}=(1-\theta)W\mathbf{z}^{k}+\theta
W\mathbf{y}^{k}-\frac{\alpha}{\theta}\mathbf{s}^{k}.$

The main idea behind the development of the above distributed algorithms is to
relate it to the inexact accelerated gradient descent (Devolder et al., 2014)
by taking average of the local variables over all $i=1,...,m$. See Section 4.1
for the details. Table 1 lists the state-of-the-art complexities of gradient
tracking and its accelerated variant.

###  2.2 Sharper Complexity Upper Bounds

In this paper, we study the following accelerated gradient tracking:

$\displaystyle\mathbf{y}^{k}=\theta_{k}\mathbf{z}^{k}+(1-\theta_{k})\mathbf{x}^{k},$
(11a) $\displaystyle\mathbf{s}^{k}=W\mathbf{s}^{k-1}+\nabla
f(\mathbf{y}^{k})-\nabla f(\mathbf{y}^{k-1}),$ (11b)
$\displaystyle\mathbf{z}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{k}}}\left(W\left(\frac{\mu\alpha}{\theta_{k}}\mathbf{y}^{k}+\mathbf{z}^{k}\right)-\frac{\alpha}{\theta_{k}}\mathbf{s}^{k}\right),$
(11c)
$\displaystyle\mathbf{x}^{k+1}=\theta_{k}\mathbf{z}^{k+1}+(1-\theta_{k})W\mathbf{x}^{k},$
(11d)

where we initialize $\mathbf{x}^{0}=\mathbf{y}^{0}=\mathbf{z}^{0}$ with
$\Pi\mathbf{x}^{0}=0$, $\mathbf{s}^{0}=\nabla f(\mathbf{y}^{0})$,
$\mathbf{z}^{1}=W\mathbf{z}^{0}-\frac{\alpha}{\theta_{0}+\mu\alpha}\mathbf{s}^{0}$,
and $\mathbf{x}^{1}=\theta_{0}\mathbf{z}^{1}+(1-\theta_{0})W\mathbf{x}^{0}$.
We see that algorithm (11a)-(11d) is equivalent to (10a)-(10d) when $\mu=0$.
However, when $\mu>0$, it is not equivalent to the method proposed in (Qu &
Li, 2020). In fact, Nesterov’s accelerated gradient method has several
variants, and we choose the one in the form of (11a)-(11d) due to its simple
convergence proof.

We follow the proof idea in (Jakovetić et al., 2014; Qu & Li, 2020) to rewrite
the distributed algorithm in the form of inexact accelerated gradient descent.
However, we bound the consensus error in a different way from (Qu & Li, 2020),
which is crucial to get faster convergence rates. See Section 4.2 for the
details. Our main technical results concerning the convergence rates of the
accelerated gradient tracking are summarized in the following two theorems for
nonstrongly convex and strongly convex problems, respectively.

###### Theorem 1

Suppose that Assumptions 1 and 2 hold with $\mu=0$. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{K}$ satisfy
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ with
$\theta_{0}=1$, let $\alpha\leq\frac{(1-\sigma)^{4}}{537L}$. Then for
algorithm (11a)-(11d), we have

$\displaystyle
F(\overline{x}^{K+1})-F(x^{*})\leq\frac{1}{(K+1)^{2}}\left(\frac{2}{\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{2L}\frac{1}{m}\sum_{i=1}^{m}\|s_{(i)}^{0}-\overline{s}^{0}\|^{2}\right),$

and

$\displaystyle\frac{1}{m}\|\Pi\mathbf{x}^{K}\|^{2}\leq\frac{1}{(K+1)^{2}}\left(\frac{5}{L\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{9(1-\sigma)}{4L^{2}}\frac{1}{m}\sum_{i=1}^{m}\|s_{(i)}^{0}-\overline{s}^{0}\|^{2}\right).$

###### Theorem 2

Suppose that Assumptions 1 and 2 hold with $\mu>0$. Let
$\alpha\leq\frac{(1-\sigma)^{3}}{119L}$ and
$\theta_{k}\equiv\theta=\frac{\sqrt{\mu\alpha}}{2}$. Then for algorithm
(11a)-(11d), we have

$\displaystyle
F(\overline{x}^{K+1})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{K+1}-x^{*}\|^{2}\leq(1-\theta)^{K+1}C,$

and

$\displaystyle\frac{1}{m}\|\Pi\mathbf{x}^{K}\|^{2}\leq(1-\theta)^{K+1}\frac{4C}{L},$

where
$C=F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{59L(1-\theta)}\frac{1}{m}\sum_{i=1}^{m}\|s_{(i)}^{0}-\overline{s}^{0}\|^{2}$.

When the local objectives are nonstrongly convex, we see from Theorem 1 that
algorithm (11a)-(11d) needs both ${\cal
O}(\frac{1}{(1-\sigma)^{2}}\sqrt{\frac{LR}{\epsilon}})$ communication rounds
and gradient computations to find an averaged solution $\overline{x}$ such
that $F(\overline{x})-F(x^{*})\leq\epsilon$, where $R={\cal
O}(\|\overline{z}^{0}-x^{*}\|^{2}+\frac{(1-\sigma)^{5}}{mL^{2}}\sum_{i=1}^{m}\|s_{(i)}^{0}-\overline{s}^{0}\|^{2})$.
When strong convexity is assumed, we see from Theorem 2 that both the
communication and gradient computation complexities are ${\cal
O}(\sqrt{\frac{L}{\mu(1-\sigma)^{3}}}\log\frac{1}{\epsilon})$. As compared in
Table 1, our complexities significantly improve the ones of ${\cal
O}(\frac{1}{\epsilon^{5/7}})$ and ${\cal
O}((\frac{L}{\mu})^{5/7}\frac{1}{(1-\sigma)^{1.5}}\log\frac{1}{\epsilon})$
originally proved in (Qu & Li, 2020).

###### Remark 1

We measure the convergence rates at the averaged solution, which can be
obtained by an additional consensus average routine
$\mathbf{u}^{t+1}=W\mathbf{u}^{t}$ initialized at
$\mathbf{u}^{0}=\mathbf{x}^{K+1}$, and ${\cal
O}(\frac{1}{1-\sigma}\log\frac{1}{\epsilon})$ rounds of communications are
enough. So the total complexities are ${\cal
O}(\frac{1}{(1-\sigma)^{2}}\sqrt{\frac{LR}{\epsilon}})+{\cal
O}(\frac{1}{1-\sigma}\log\frac{1}{\epsilon})$ and ${\cal
O}(\sqrt{\frac{L}{\mu(1-\sigma)^{3}}}\log\frac{1}{\epsilon})+{\cal
O}(\frac{1}{1-\sigma}\log\frac{1}{\epsilon})$ for nonstrongly convex and
strongly convex problems, respectively, and they are dominated by the first
part.

###### Remark 2

For the nonstrongly convex problems, we can also prove the convergence rate
measured at the point $x_{(i)}^{K}$ for any $i$:

$\displaystyle\begin{aligned}
F(x_{(i)}^{K})-F(x^{*})\leq\frac{1}{K^{2}}\max\left\\{\frac{\sqrt{m}(1-\sigma)}{L\alpha},8m\right\\}\left(\frac{2}{\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{2mL}\|\Pi\mathbf{s}^{0}\|^{2}\right).\end{aligned}$

However, the complexity increases to ${\cal
O}(\max\\{\frac{\sqrt{m}}{(1-\sigma)^{2}},\frac{\sqrt[4]{m}}{(1-\sigma)^{3.5}}\\}\sqrt{\frac{L}{\epsilon}})$
in this case. For strongly convex problems, the complexity keeps the same no
matter measured at $\overline{x}^{K+1}$ or $x_{(i)}^{K}$.

###### Remark 3

Theorems 1 and 2 require the step size to be of the order ${\cal
O}(\frac{(1-\sigma)^{4}}{L})$ and ${\cal O}(\frac{(1-\sigma)^{3}}{L})$,
respectively, which may be small when the network is not well connected. We
conjecture that it is because of the limitation of the proof technique, rather
than the weakness of the algorithm. In fact, Alghunaim et al. (2020) analyzed
the original gradient tracking from the primal dual perspective, and they only
required the step size to satisfy $\alpha\leq\frac{\omega^{2}}{L}$ when the
stronger assumption $\omega I\preceq W\preceq I$ is made on the weight matrix,
where $\omega$ is a small positive constant. We can design $W$ such that
$\omega={\cal O}(1)$, for example, $\omega=\frac{1}{2}$, so to have
$\alpha={\cal O}(\frac{1}{L})$. It is unclear whether we can set the step size
of the order ${\cal O}(\frac{1}{L})$ for algorithm (11a)-(11d) under the
stronger assumption on $W$.

###  2.3 Further Improved Complexities via Chebyshev Acceleration

The dependence on $1-\sigma$ in our complexities is not optimal, and it can be
further improved by Chebyshev acceleration (Arioli & Scott, 2014). Chebyshev
acceleration was first used to accelerate distributed algorithms by Scaman et
al. (2017), and it becomes a standard technique now. Define the Chebyshev
polynomials as $T_{0}(x)=1$, $T_{1}(x)=x$, and
$T_{k+1}(x)=2xT_{k}(x)-T_{k-1}(x)$ for all $k\geq 1$. Define $L=I-W$ with
$\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{m-1}>\lambda_{m}=0$ being its
eigenvalues (assume that $W$ is symmetric). We know $\lambda_{m-1}=1-\sigma$.
Define $\nu=\frac{1-\sigma}{\lambda_{1}}$,
$c_{1}=\frac{1-\sqrt{\nu}}{1+\sqrt{\nu}}$, $c_{2}=\frac{1+\nu}{1-\nu}$,
$c_{3}=\frac{2}{\lambda_{1}+1-\sigma}$, and
$P_{t}(x)=1-\frac{T_{t}(c_{2}(1-x))}{T_{t}(c_{2})}$. Then, $P_{t}(c_{3}L)$ is
a gossip matrix satisfying $P_{t}(c_{3}L)\mathbf{1}=0$ with its spectrum in
$[1-\frac{2c_{1}^{t}}{1+c_{1}^{2t}},1+\frac{2c_{1}^{t}}{1+c_{1}^{2t}}]$
(Auzinger & Melenk, 2017). Let $t=\frac{1}{\sqrt{\nu}}$ so to have
$c_{1}^{t}\leq\frac{1}{e}$ and
$[1-\frac{2c_{1}^{t}}{1+c_{1}^{2t}},1+\frac{2c_{1}^{t}}{1+c_{1}^{2t}}]\subseteq[0.35,1.65]$.
Thus, we can replace the weight matrix $W$ in algorithm (11a)-(11d) by
$I-P_{t}(c_{3}L)$ because its second largest singular value $\sigma^{\prime}$
satisfies $\sigma^{\prime}\leq 0.65$, which is independent on $1-\sigma$. From
Theorems 1 and 2 with $\sigma$ replaced by $\sigma^{\prime}$, we see that the
algorithm needs ${\cal O}(\sqrt{\frac{L}{\epsilon}})$ iterations for
nonstrongly convex problems and ${\cal
O}(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$ iterations for strongly convex
problems to find an $\epsilon$-optimal solution, which corresponds to the
gradient computation complexity. On the other hand, we can compute the
operation $(I-P_{t}(c_{3}L))\mathbf{x}$ by the following procedure (Scaman et
al., 2017):

Input: $\mathbf{x}$,

Initialize: $a_{0}=1$, $a_{1}=c_{2}$, $\mathbf{z}^{0}=\mathbf{x}$,
$\mathbf{z}^{1}=c_{2}(I-c_{3}L)\mathbf{x}$,

for $s=1,2,...,t-1$ do

$a_{s+1}=2c_{2}a_{s}-a_{s-1}$,

$\mathbf{z}^{s+1}=2c_{2}(I-c_{3}L)\mathbf{z}^{s}-\mathbf{z}^{s-1}$.

end for

Output: $(I-P_{t}(c_{3}L))\mathbf{x}=\frac{\mathbf{z}^{t}}{a_{t}}$.

Thus, the communication complexities for nonstrongly convex and strongly
convex problems are ${\cal O}(\sqrt{\frac{L}{\epsilon(1-\sigma)}})$ and ${\cal
O}(\sqrt{\frac{L}{\mu(1-\sigma)}}\log\frac{1}{\epsilon})$, respectively.

##  3 Accelerated gradient tracking over Time-varying Graphs

We can extend algorithm (11a)-(11d) to the time-varying graphs with no change
except that the weight matrix may vary with time. The resultant algorithm
reads as follows, where we allow $W_{1}^{k}$, $W_{2}^{k}$, and $W_{3}^{k}$ to
be different at iteration $k$,

$\displaystyle\mathbf{y}^{k}=\theta_{k}\mathbf{z}^{k}+(1-\theta_{k})\mathbf{x}^{k},$
(12a) $\displaystyle\mathbf{s}^{k}=W_{1}^{k}\mathbf{s}^{k-1}+\nabla
f(\mathbf{y}^{k})-\nabla f(\mathbf{y}^{k-1}),$ (12b)
$\displaystyle\mathbf{z}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{k}}}\left(W_{2}^{k}\left(\frac{\mu\alpha}{\theta_{k}}\mathbf{y}^{k}+\mathbf{z}^{k}\right)-\frac{\alpha}{\theta_{k}}\mathbf{s}^{k}\right),$
(12c)
$\displaystyle\mathbf{x}^{k+1}=\theta_{k}\mathbf{z}^{k+1}+(1-\theta_{k})W_{3}^{k}\mathbf{x}^{k}.$
(12d)

Unlike the classical analysis relying on the small gain theorem (Nedić et al.,
2017), we construct a novel way to bound the consensus error such that the
proof framework over static graph can be extended to time-varying graphs. See
the details in Section 4.3. Our proof technique may shed new light to time-
varying decentralized optimization, and it gives an alternative to the small
gain theorem. There are two advantages of our proof technique: it can be
embedded into many algorithm frameworks from the perspective of error
analysis, and it can be applied to both strongly convex and nonstrongly convex
problems, while the small gain theorem only applies to strongly convex ones.
Our main technical results are summarized in the following two theorems for
nonstrongly convex and strongly convex problems, respectively.

###### Theorem 3

Suppose that Assumptions 1 and 3 hold with $\mu=0$. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{T\gamma}$ satisfy
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ with
$\theta_{0}=1$, let
$\alpha\leq\frac{(1-\sigma_{\gamma})^{4}}{21675L\gamma^{4}}$. Then for
algorithm (12a)-(12d), we have

$\displaystyle
F(\overline{x}^{T\gamma+1})-F(x^{*})\leq\frac{1}{(T\gamma+1)^{2}}\left(\frac{2}{\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{5mL\gamma}\max_{r=0,...,\gamma}\|\Pi\mathbf{s}^{r}\|^{2}\right),$

and

$\displaystyle\frac{1}{m}\|\Pi\mathbf{x}^{T\gamma}\|^{2}\leq\frac{9}{2L(T\gamma+1)^{2}}\left(\frac{2}{\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{5mL\gamma}\max_{r=0,...,\gamma}\|\Pi\mathbf{s}^{r}\|^{2}\right).$

###### Theorem 4

Suppose that Assumptions 1 and 3 hold with $\mu>0$. Let
$\alpha\leq\frac{(1-\sigma_{\gamma})^{3}}{4244L\gamma^{3}}$ and
$\theta_{k}\equiv\theta=\frac{\sqrt{\mu\alpha}}{2}$. Then for algorithm
(12a)-(12d), we have

$\displaystyle
F(\overline{x}^{T\gamma+1})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{T\gamma+1}-x^{*}\|^{2}\leq(1-\theta)^{T\gamma+1}C,$

and

$\displaystyle\frac{1}{m}\|\Pi\mathbf{x}^{T\gamma}\|^{2}\leq(1-\theta)^{T\gamma+1}\frac{4C}{L},$

where
$C=F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{49mL\gamma(1-\theta)}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\frac{1459L\gamma^{3}}{m(1-\theta)(1-\sigma_{\gamma})^{3}}\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}+\frac{6.6L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}$,
$\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}=\max_{r=1,...,\gamma}\|\Pi\mathbf{s}^{r}\|^{2}$,
and similarly for $\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}$ and
$\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}$.

We see from Theorem 3 that algorithm (12a)-(12d) needs ${\cal
O}(\frac{\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\sqrt{\frac{LR}{\epsilon}})$
rounds of communications and gradient computations to find an
$\epsilon$-optimal averaged solution for nonstrongly convex problems, where
$R={\cal
O}(\|\overline{z}^{0}-x^{*}\|^{2}+\frac{(1-\sigma_{\gamma})^{5}}{mL^{2}\gamma^{5}}\max_{r=0,...,\gamma}\sum_{i=1}^{m}\|s_{(i)}^{r}-\overline{s}^{r}\|^{2})$.
When the problems are strongly convex, the complexity becomes ${\cal
O}((\frac{\gamma}{1-\sigma_{\gamma}})^{1.5}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$.
Our complexities have the optimal dependence on the precision $\epsilon$ and
the condition number $L/\mu$, matching that of the classical centralized
accelerated gradient method. As compared in Table 2, the state-of-the-art APM
(Li et al., 2020a) and DAGD-C (Rogozin et al., 2020) have an additional ${\cal
O}(\log\frac{1}{\epsilon})$ factor in their communication complexities.
However, our dependence on $\frac{\gamma}{1-\sigma_{\gamma}}$ is not state-of-
the-art. We will improve it in the next section.

###### Remark 4

Similar to Remark 2, for the nonstrongly convex problems, we can also prove
the convergence rate measured at the point $x_{(i)}^{T\gamma-\gamma+1}$ for
any $i$:

$\displaystyle\begin{aligned}
F(x_{(i)}^{T\gamma-\gamma+1})-F(x^{*})\leq\frac{1}{(T\gamma-\gamma+1)^{2}}\max\left\\{\frac{\sqrt{m}(1-\sigma_{\gamma})}{L\alpha\gamma},8m\right\\}\left(\frac{2}{\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{5mL\gamma}\max_{r=0,...,\gamma}\|\Pi\mathbf{s}^{r}\|^{2}\right).\end{aligned}$

However, the complexity increases to ${\cal
O}(\max\\{\frac{\sqrt{m}\gamma^{2}}{(1-\sigma_{\gamma})^{2}},\sqrt[4]{m}(\frac{\gamma}{1-\sigma_{\gamma}})^{3.5}\\}\sqrt{\frac{L}{\epsilon}})$.
On the other hand, the averaged solution can also be obtained by an additional
multiple consensus routine, and ${\cal
O}(\frac{\gamma}{1-\sigma_{\gamma}}\log\frac{1}{\epsilon})$ rounds of
communications are enough.

###### Remark 5

In Theorems 3 and 4, we measure the convergence rates at the $(T\gamma+1)$th
iteration for simplicity. For any $K=T\gamma+r$, a straightforward
modification is to regard the $(r-1)$th iteration as the virtual
initialization. However, we should modify the proof of Theorem 3 accordingly
with $\theta_{0}<1$. We omit the details since it complicates the proofs and
notations.

###### Remark 6

The local computation based distributed optimization, such as the local SGD
(Stich, 2019) which is widely used in federated learning, can be modeled by
optimization over time-varying graphs (Koloskova et al., 2020). Consider the
case when $W^{k}_{ii}=1$ and $W^{k}_{ij}=0$ for all $j\neq i$ and $t\leq k\leq
t^{\prime}$, which means that agent $i$ does not communicate with the other
agents during the time $[t,t^{\prime}]$, algorithm (12a)-(12d) reduces to the
following steps for agent $i$ and iteration $t\leq k\leq t^{\prime}$:

$\displaystyle\begin{aligned}
&\mathbf{y}_{(i)}^{k}=\theta_{k}\mathbf{z}_{(i)}^{k}+(1-\theta_{k})\mathbf{x}_{(i)}^{k},\\\
&\mathbf{s}_{(i)}^{k}=\mathbf{s}_{(i)}^{k-1}+\nabla
f_{(i)}(\mathbf{y}_{(i)}^{k})-\nabla f_{(i)}(\mathbf{y}_{(i)}^{k-1}),\\\
&\mathbf{z}_{(i)}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{k}}}\left(\left(\frac{\mu\alpha}{\theta_{k}}\mathbf{y}_{(i)}^{k}+\mathbf{z}_{(i)}^{k}\right)-\frac{\alpha}{\theta_{k}}\mathbf{s}_{(i)}^{k}\right),\\\
&\mathbf{x}_{(i)}^{k+1}=\theta_{k}\mathbf{z}_{(i)}^{k+1}+(1-\theta_{k})\mathbf{x}_{(i)}^{k},\end{aligned}$

which is a local inexact accelerated gradient descent. Motivated by the local
SGD, we can perform the local inexact accelerated gradient descent for each
agent for some period of time, and then communicate with each other over a
decentralized network. Although the convergence can be guaranteed by Theorems
3 and 4, currently we cannot prove the superiority of this local strategy over
the traditional distributed algorithms, such as (11a)-(11d), because of the
sub-optimal dependence on $\gamma$ in the complexities of algorithm
(12a)-(12d), where $\gamma$ can be regarded as the communication frequency in
this local strategy.

###  3.1 Further Improved Complexities via Multiple Consensus

Motivated by Chebyshev acceleration, we can employ a multiple consensus
subroutine to further reduce the dependence on
$\frac{\gamma}{1-\sigma_{\gamma}}$. The general idea is to replace
$W_{1}^{k}$, $W_{2}^{k}$, and $W_{3}^{k}$ in (12a)-(12d) by three virtual
weight matrices $W_{1}^{k,\zeta}$, $W_{2}^{k,\zeta}$, and $W_{3}^{k,\zeta}$
with carefully designed $\zeta$ such that

$\displaystyle\|\Pi
W_{r}^{k,\zeta}\mathbf{x}\|\leq\frac{1}{e}\|\Pi\mathbf{x}\|,\quad r=1,2,3.$

Here, $\frac{1}{e}$ can be replaced by any constant not close to 1. Then, it
can be regarded as running the resultant algorithm over time-varying graphs
with each graph instance being connected at every time, and moreover,
$\sigma=\frac{1}{e}$. From Theorems 3 and 4 with $\gamma=1$ and
$\sigma_{\gamma}=\frac{1}{e}$, we see that ${\cal
O}(\sqrt{\frac{L}{\epsilon}})$ iterations for nonstrongly convex problems and
${\cal O}(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$ for strongly convex
problems suffice to find an $\epsilon$-optimal solution, which correspond to
the gradient computation complexity. Next, we consider the communication
complexity. Letting $\zeta=\lceil\frac{\gamma}{1-\sigma_{\gamma}}\rceil$, it
follows from (7) that

$\displaystyle\|\Pi
W_{r}^{k,\zeta}\mathbf{x}\|\leq\sigma_{\gamma}^{\frac{1}{1-\sigma_{\gamma}}}\|\Pi\mathbf{x}\|=\left(1-\left(1-\sigma_{\gamma}\right)\right)^{\frac{1}{1-\sigma_{\gamma}}}\|\Pi\mathbf{x}\|\leq\frac{1}{e}\|\Pi\mathbf{x}\|,$

where we use the fact that $(1-x)^{1/x}\leq 1/e$ for any $x\in(0,1)$. Since
$\Pi W_{r}^{k,\zeta}\mathbf{x}$ can be implemented by the multiple consensus
subroutine $\mathbf{u}^{t+1}=W_{r}^{t}\mathbf{u}^{t}$ with $\zeta$ rounds of
communications initialized at $\mathbf{u}^{0}=\mathbf{x}$, the communication
complexity is ${\cal
O}(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\epsilon}})$ for nonstrongly
convex problems and ${\cal
O}(\frac{\gamma}{1-\sigma_{\gamma}}\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$
for strongly convex problems, respectively.

###### Remark 7

The multiple consensus subroutine is only for the theoretical purpose. It may
be unpractical in a realistic time-varying network. The multiple consensus may
place a larger communication burden in practice, although it gives
theoretically lower communication complexities. Communication has been
recognized as the major bottleneck in distributed optimization because the CPU
speed is much faster than the communication speed over TCP/IP (Lan et al.,
2020). The similar issue also happened in APM (Li et al., 2020a) and DAGD-C
(Rogozin et al., 2020), which also need a consensus subroutine. In fact, in
federated learning, local SGD is employed to reduce the communication
frequency, rather than increasing the communication frequency by the multiple
consensus.

##  4 Proofs of Theorems

In this section, we prove the theorems in Sections 2 and 3 in a unified
framework. We first reformulate algorithms (11a)-(11d) and (12a)-(12d) as the
inexact accelerated gradient descent and give its convergence rates in Section
4.1, then we bound the consensus error in Sections 4.2 and 4.3 for static
graph and time-varying graphs, respectively.

###  4.1 Convergence Rates of the Inexact Accelerated Gradient Descent

Following the proof framework in (Jakovetić et al., 2014; Qu & Li, 2020), we
multiply both sides of (11a)-(11d) by $\frac{1}{m}\mathbf{1}^{T}$ and use the
definitions in (3) and (2) to yield

$\displaystyle\overline{y}^{k}=\theta_{k}\overline{z}^{k}+(1-\theta_{k})\overline{x}^{k},$
(13a)
$\displaystyle\overline{s}^{k}-\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(y_{(i)}^{k})=\overline{s}^{k-1}-\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(y_{(i)}^{k-1}),$
(13b)
$\displaystyle\overline{z}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{k}}}\left(\frac{\mu\alpha}{\theta_{k}}\overline{y}^{k}+\overline{z}^{k}-\frac{\alpha}{\theta_{k}}\overline{s}^{k}\right),$
(13c)
$\displaystyle\overline{x}^{k+1}=\theta_{k}\overline{z}^{k+1}+(1-\theta_{k})\overline{x}^{k}.$
(13d)

From the initialization $\mathbf{s}^{0}=\nabla f(\mathbf{y}^{0})$ and (13b),
we have the following standard but important property in gradient tracking:

$\overline{s}^{k}=\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(y_{(i)}^{k}).$ (14)

Iterations (13a)-(13d) can be regarded as the inexact accelerated gradient
descent (Devolder et al., 2014) in the sense that we use
$\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(y_{(i)}^{k})$ as the descent direction,
rather than the true gradient
$\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(\overline{y}^{k})$. In fact, when we replace
$\overline{s}^{k}$ in step (13c) by the true gradient, steps (13a), (13c), and
(13d) reduce to the updates of the standard accelerated gradient descent, see
(Nesterov, 2004; Lin et al., 2020) for example. Note that (13a)-(13d) also
hold for algorithm (12a)-(12d) over time-varying graphs, as long as the column
stochasticity property of $\mathbf{1}^{T}W^{k}=\mathbf{1}^{T}$ in Assumption 3
holds.

The next lemma demonstrates the analogy properties of convexity and smoothness
with the inexact gradient. The proof can be found in (Jakovetić et al., 2014;
Qu & Li, 2020). For the completeness and the readers’ convenience, we give the
proof in the appendix.

###### Lemma 1

Define

$\displaystyle
f(\overline{y}^{k},\mathbf{y}^{k})=\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),\overline{y}^{k}-y_{(i)}^{k}\right\rangle\right).$ (15)

Suppose that Assumption 1 holds. Then, we have for any $w$,

$\displaystyle F(w)\geq
f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},w-\overline{y}^{k}\right\rangle+\frac{\mu}{2}\|w-\overline{y}^{k}\|^{2},$
(16) $\displaystyle F(w)\leq
f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},w-\overline{y}^{k}\right\rangle+\frac{L}{2}\|w-\overline{y}^{k}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2}.$
(17)

Especially, we allow $\mu$ to be zero.

Define the Bregman distance as follows:

$D_{f}(x,\mathbf{y}^{k})=\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(x)-f_{(i)}(y_{(i)}^{k})-\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),x-y_{(i)}^{k}\right\rangle\right).$ (18)

The next lemma gives the convergence rates of the inexact accelerated gradient
descent. The techniques in this proof are standard, see (Lin et al., 2020) for
example. The crucial difference is that we keep the Bregman distance term
$D_{f}(\overline{x}^{k},\mathbf{y}^{k})$ in (LABEL:cont3) and (LABEL:cont4),
which is motivated by (Tseng, 2008; Li & Lin, 2020a).

Compared with the standard accelerated gradient descent, for example, see
(Nesterov, 2004; Lin et al., 2020), there are two additional error terms $(a)$
and $(c)$ in our lemma due to the inexact gradient. In the next two sections,
we bound the two terms carefully by $(b)$ and $(d)$, respectively, such that
the convergence rates of the accelerated gradient tracking match those of the
classical centralized accelerated gradient descent, which is the main
technical contribution of this paper compared with the existing work on
accelerated gradient tracking in (Qu & Li, 2020).

###### Lemma 2

Suppose that Assumption 1 with $\mu=0$ and part 2 of Assumption 2 for static
graph or Assumption 3 for time-varying graphs hold. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{K}$ satisfy
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ with
$\theta_{0}=1$. Then for both algorithms (11a)-(11d) and (12a)-(12d), we have

$\displaystyle\begin{aligned}
&\frac{F(\overline{x}^{K+1})-F(x^{*})}{\theta_{K}^{2}}+\frac{1}{2\alpha}\|\overline{z}^{K+1}-x^{*}\|^{2}\\\
&~{}~{}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\underbrace{\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2}}_{\text{\rm
term
(a)}}-\underbrace{\sum_{k=0}^{K}\left(\left(\frac{1}{2\alpha}-\frac{L}{2}\right)\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}+\frac{1}{\theta_{k-1}^{2}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)}_{\text{\rm
term (b)}}.\end{aligned}$ (19)

Suppose that Assumption 1 with $\mu>0$ and part 2 of Assumption 2 for static
graph or Assumption 3 for time-varying graphs hold. Let
$\theta_{k}=\theta=\frac{\sqrt{\alpha\mu}}{2}$ for all $k$ and assume that
$\alpha\mu\leq 1$. Then for both algorithms (11a)-(11d) and (12a)-(12d), we
have

$\displaystyle\begin{aligned}
&\frac{1}{(1-\theta)^{K+1}}\left(F(\overline{x}^{K+1})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{K+1}-x^{*}\|^{2}\right)\\\
&~{}~{}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\underbrace{\sum_{k=0}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2}}_{\text{\rm
term (c)}}\\\
&~{}~{}\quad-\underbrace{\sum_{k=0}^{K}\left(\frac{1}{(1-\theta)^{k+1}}\left(\frac{\theta^{2}}{2\alpha}-\frac{L\theta^{2}}{2}\right)\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}+\frac{1}{(1-\theta)^{k}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)}_{\text{\rm
term (d)}}.\end{aligned}$ (20)

###### Proof 1

From the inexact smoothness (17), we have

$\displaystyle\begin{aligned}
F(\overline{x}^{k+1})\leq&f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},\overline{x}^{k+1}-\overline{y}^{k}\right\rangle+\frac{L}{2}\|\overline{x}^{k+1}-\overline{y}^{k}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2}\\\
\overset{a}{=}&f(\overline{y}^{k},\mathbf{y}^{k})+\theta_{k}\left\langle\overline{s}^{k},\overline{z}^{k+1}-\overline{z}^{k}\right\rangle+\frac{L\theta_{k}^{2}}{2}\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2}\\\
=&f(\overline{y}^{k},\mathbf{y}^{k})+\theta_{k}\left\langle\overline{s}^{k},x^{*}-\overline{z}^{k}\right\rangle+\theta_{k}\left\langle\overline{s}^{k},\overline{z}^{k+1}-x^{*}\right\rangle+\frac{L\theta_{k}^{2}}{2}\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2},\end{aligned}$
(21)

where we use (13a) and (13d) in $\overset{a}{=}$. Next, we bound the two inner
product terms. For the first inner product, we have

$\displaystyle\begin{aligned}
&f(\overline{y}^{k},\mathbf{y}^{k})+\theta_{k}\left\langle\overline{s}^{k},x^{*}-\overline{z}^{k}\right\rangle\\\
&~{}~{}\overset{b}{=}f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},\theta_{k}x^{*}+(1-\theta_{k})\overline{x}^{k}-\overline{y}^{k}\right\rangle\\\
&~{}~{}=\theta_{k}\left(f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},x^{*}-\overline{y}^{k}\right\rangle\right)+(1-\theta_{k})\left(f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},\overline{x}^{k}-\overline{y}^{k}\right\rangle\right)\\\
&~{}~{}\overset{c}{\leq}\theta_{k}F(x^{*})-\frac{\mu\theta_{k}}{2}\|\overline{y}^{k}-x^{*}\|^{2}+\frac{1-\theta_{k}}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),\overline{x}^{k}-y_{(i)}^{k}\right\rangle\right)\\\
&~{}~{}=\theta_{k}F(x^{*})-\frac{\mu\theta_{k}}{2}\|\overline{y}^{k}-x^{*}\|^{2}+(1-\theta_{k})F(\overline{x}^{k})\\\
&~{}~{}\quad-\frac{1-\theta_{k}}{m}\sum_{i=1}^{m}\left(f_{(i)}(\overline{x}^{k})-f_{(i)}(y_{(i)}^{k})-\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),\overline{x}^{k}-y_{(i)}^{k}\right\rangle\right)\\\
&~{}~{}=\theta_{k}F(x^{*})-\frac{\mu\theta_{k}}{2}\|\overline{y}^{k}-x^{*}\|^{2}+(1-\theta_{k})F(\overline{x}^{k})-(1-\theta_{k})D_{f}(\overline{x}^{k},\mathbf{y}^{k}),\end{aligned}$

where we use (13a) in $\overset{b}{=}$, (16), (15), and (14) in
$\overset{c}{\leq}$. For the second inner product, we have

$\displaystyle\begin{aligned}
\theta_{k}\left\langle\overline{s}^{k},\overline{z}^{k+1}-x^{*}\right\rangle\overset{d}{=}&-\frac{\theta_{k}^{2}}{\alpha}\left\langle\overline{z}^{k+1}-\overline{z}^{k}+\frac{\mu\alpha}{\theta_{k}}(\overline{z}^{k+1}-\overline{y}^{k}),\overline{z}^{k+1}-x^{*}\right\rangle\\\
=&\frac{\theta_{k}^{2}}{2\alpha}\left(\|\overline{z}^{k}-x^{*}\|^{2}-\|\overline{z}^{k+1}-x^{*}\|^{2}-\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}\right)\\\
&+\frac{\mu\theta_{k}}{2}\left(\|\overline{y}^{k}-x^{*}\|^{2}-\|\overline{z}^{k+1}-x^{*}\|^{2}-\|\overline{z}^{k+1}-\overline{y}^{k}\|^{2}\right),\end{aligned}$

where we use (13c) in $\overset{d}{=}$. Plugging into (21) and rearranging the
terms, it gives

$\displaystyle\begin{aligned}
&F(\overline{x}^{k+1})-F(x^{*})+\left(\frac{\theta_{k}^{2}}{2\alpha}+\frac{\mu\theta_{k}}{2}\right)\|\overline{z}^{k+1}-x^{*}\|^{2}\\\
&~{}~{}\leq(1-\theta_{k})(F(\overline{x}^{k})-F(x^{*}))+\frac{\theta_{k}^{2}}{2\alpha}\|\overline{z}^{k}-x^{*}\|^{2}\\\
&~{}~{}\quad-\left(\frac{\theta_{k}^{2}}{2\alpha}-\frac{L\theta_{k}^{2}}{2}\right)\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}-(1-\theta_{k})D_{f}(\overline{x}^{k},\mathbf{y}^{k})+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2}.\end{aligned}$
(22)

Case 1: Each $f_{(i)}$ is nonstrongly convex. In this case, (LABEL:cont2)
holds with $\mu=0$. Dividing both sides of (LABEL:cont2) by $\theta_{k}^{2}$,
summing over $k=0,1,...,K$, using
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ and
$\theta_{0}=1$, we have (LABEL:cont3).

Case 2: Each $f_{(i)}$ is $\mu$-strongly convex. Letting
$\theta_{k}=\theta=\frac{\sqrt{\alpha\mu}}{2}$ for all $k$, we know
$\frac{\theta^{2}}{2\alpha}\leq\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)(1-\theta)$
holds if $\alpha\mu\leq 1$. Dividing both sides of (LABEL:cont2) by
$(1-\theta)^{k+1}$ and summing over $k=0,1,...,K$, it gives (LABEL:cont4).

###  4.2 Bounding the Consensus Error over Static Graph

In this section, we bound the term $(a)$ by $(b)$ appeared in (LABEL:cont3),
and the term $(c)$ by $(d)$ in (LABEL:cont4). We first bound
$\|\Pi\mathbf{y}^{k}\|^{2}$ in the next lemma. The crucial trick is to
construct a linear combination of the consensus errors with carefully designed
weights such that it shrinks geometrically with an additional error term.
Moreover, the step size $\alpha$ remains to be a constant of the order ${\cal
O}(\frac{1}{L})$ as large as possible. As a comparison, Qu & Li (2020)
constructed a linear system inequality with smaller step sizes, for example,
the vanishing ones of $\alpha_{k}={\cal O}(\frac{1}{k^{0.6+\epsilon}})$ for
nonstrongly convex problems, which yield a slower convergence rate than ours.
Another trick is that we use constant $\tau$ to balance
$D_{f}(\overline{x}^{r+1},\mathbf{y}^{r+1})$ and
$\|\overline{z}^{r+1}-\overline{z}^{r}\|^{2}$ in $\Phi^{r}$, which is
generated by Young’s inequality and will be specified later.

###### Lemma 3

Suppose that Assumptions 1 and 2 hold with $\mu\geq 0$. Let
$\alpha\leq\frac{(1-\sigma)^{3}}{80L\sqrt{1+\frac{1}{\tau}}}$ and the sequence
$\\{\theta_{k}\\}_{k=0}^{K}$ satisfy $\theta_{k+1}\leq\theta_{k}\leq 1$. Then
for algorithm (11a)-(11d), we have

$\displaystyle\qquad\begin{aligned}
\max\left\\{\|\Pi\mathbf{y}^{k+1}\|^{2},\|\Pi\mathbf{x}^{k+1}\|^{2}\right\\}\leq
C_{1}\rho^{k+1}+C_{2}\sum_{r=0}^{k}\rho^{k-r}\theta_{r}^{2}\Phi^{r},\end{aligned}$
(23)

where $\rho=1-\frac{1-\sigma}{4}$,
$C_{1}=\frac{(1-\sigma)^{2}}{18(1+\frac{1}{\tau})L^{2}}\|\Pi\mathbf{s}^{0}\|^{2}$,
$C_{2}=\frac{1-\sigma}{9(1+\frac{1}{\tau})L^{2}}$,

$\Phi^{r}=\frac{2mL(1+\tau)}{\theta_{r}^{2}}D_{f}(\overline{x}^{r+1},\mathbf{y}^{r+1})+2mL^{2}\left(1+\frac{1}{\tau}\right)\|\overline{z}^{r+1}-\overline{z}^{r}\|^{2},$
(24)

and $\tau$ can be any positive constant.

###### Proof 2

Multiplying both sides of (11a)-(11d) by $\Pi$, using (5) and
$\|\Pi\mathbf{x}\|\leq\|\mathbf{x}\|$, we have

$\displaystyle\|\Pi\mathbf{y}^{k}\|\leq\theta_{k}\|\Pi\mathbf{z}^{k}\|+(1-\theta_{k})\|\Pi\mathbf{x}^{k}\|\leq\theta_{k}\|\Pi\mathbf{z}^{k}\|+\|\Pi\mathbf{x}^{k}\|,$
(25)
$\displaystyle\|\Pi\mathbf{s}^{k+1}\|\leq\sigma\|\Pi\mathbf{s}^{k}\|+\|\nabla
f(\mathbf{y}^{k+1})-\nabla f(\mathbf{y}^{k})\|,$ (26)
$\displaystyle\begin{aligned}
\|\Pi\mathbf{z}^{k+1}\|\leq&\sigma\left(\frac{\mu\alpha}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{y}^{k}\|+\frac{\theta_{k}}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{z}^{k}\|\right)+\frac{\alpha}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{s}^{k}\|\\\
\overset{a}{\leq}&\frac{\sigma(\mu\alpha+1)\theta_{k}}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{z}^{k}\|+\frac{\sigma\mu\alpha}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{x}^{k}\|+\frac{\alpha}{\theta_{k}+\mu\alpha}\|\Pi\mathbf{s}^{k}\|\\\
\overset{b}{\leq}&\sigma\|\Pi\mathbf{z}^{k}\|+\frac{\mu\alpha}{\theta_{k}}\|\Pi\mathbf{x}^{k}\|+\frac{\alpha}{\theta_{k}}\|\Pi\mathbf{s}^{k}\|,\end{aligned}$
(27)
$\displaystyle\|\Pi\mathbf{x}^{k+1}\|\leq\theta_{k}\|\Pi\mathbf{z}^{k+1}\|+\sigma\|\Pi\mathbf{x}^{k}\|,$
(28)

where $\overset{a}{\leq}$ uses (25), $\overset{b}{\leq}$ uses $\sigma<1$ and
$\frac{(\mu\alpha+1)\theta_{k}}{\theta_{k}+\mu\alpha}\leq 1$ with
$\theta_{k}\leq 1$. Next, we bound $\|\nabla f(\mathbf{y}^{k+1})-\nabla
f(\mathbf{y}^{k})\|$.

$\displaystyle\quad\begin{aligned} &\|\nabla f(\mathbf{y}^{k+1})-\nabla
f(\mathbf{y}^{k})\|^{2}=\sum_{i=1}^{m}\|\nabla f_{(i)}(y_{(i)}^{k+1})-\nabla
f_{(i)}(y_{(i)}^{k})\|^{2}\\\ &~{}~{}\leq\sum_{i=1}^{m}(1+\tau)\|\nabla
f_{(i)}(y_{(i)}^{k+1})-\nabla f_{(i)}(\overline{x}^{k+1})\|^{2}\\\
&~{}~{}\quad+\sum_{i=1}^{m}\left(1+\frac{1}{\tau}\right)2\left(\|\nabla
f_{(i)}(\overline{x}^{k+1})-\nabla f_{(i)}(\overline{y}^{k})\|^{2}+\|\nabla
f_{(i)}(\overline{y}^{k})-\nabla f_{(i)}(y_{(i)}^{k})\|^{2}\right)\\\
&~{}~{}\overset{c}{\leq}2mL(1+\tau)D_{f}(\overline{x}^{k+1},\mathbf{y}^{k+1})+2L^{2}\left(1+\frac{1}{\tau}\right)\sum_{i=1}^{m}\left(\|\overline{x}^{k+1}-\overline{y}^{k}\|^{2}+\|\overline{y}^{k}-y_{(i)}^{k}\|^{2}\right)\\\
&~{}~{}\overset{d}{=}2mL(1+\tau)D_{f}(\overline{x}^{k+1},\mathbf{y}^{k+1})+2L^{2}\left(1+\frac{1}{\tau}\right)\left(m\theta_{k}^{2}\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}+\|\Pi\mathbf{y}^{k}\|^{2}\right)\\\
&~{}~{}=\theta_{k}^{2}\Phi^{k}+2L^{2}\left(1+\frac{1}{\tau}\right)\|\Pi\mathbf{y}^{k}\|^{2}\\\
&~{}~{}\overset{e}{\leq}\theta_{k}^{2}\Phi^{k}+4L^{2}\left(1+\frac{1}{\tau}\right)\left(\theta_{k}^{2}\|\Pi\mathbf{z}^{k}\|^{2}+\|\Pi\mathbf{x}^{k}\|^{2}\right),\end{aligned}$
(29)

where $\overset{c}{\leq}$ uses the convexity and smoothness of $f_{(i)}$ and
the definition of $D_{f}$ in (18), $\overset{d}{=}$ uses (13a), (13d), and the
definition of $\Pi\mathbf{y}$ in (4), $\overset{e}{\leq}$ uses (25). Denote
$c_{0}=4L^{2}\left(1+\frac{1}{\tau}\right)$ for simplicity in the remaining
proof of this lemma.

Squaring both sides of (26), it follows that

$\displaystyle\begin{aligned}
\|\Pi\mathbf{s}^{k+1}\|^{2}\leq&\left(1+\frac{1-\sigma}{2\sigma}\right)\sigma^{2}\|\Pi\mathbf{s}^{k}\|^{2}+\left(1+\frac{2\sigma}{1-\sigma}\right)\|\nabla
f(\mathbf{y}^{k+1})-\nabla f(\mathbf{y}^{k})\|^{2}\\\
=&\frac{\sigma+\sigma^{2}}{2}\|\Pi\mathbf{s}^{k}\|^{2}+\frac{1+\sigma}{1-\sigma}\|\nabla
f(\mathbf{y}^{k+1})-\nabla f(\mathbf{y}^{k})\|^{2}\\\
\overset{f}{\leq}&\frac{1+\sigma}{2}\|\Pi\mathbf{s}^{k}\|^{2}+\frac{2}{1-\sigma}\left(\theta_{k}^{2}\Phi^{k}+c_{0}\theta_{k}^{2}\|\Pi\mathbf{z}^{k}\|^{2}+c_{0}\|\Pi\mathbf{x}^{k}\|^{2}\right),\end{aligned}$
(30)

where we use $\sigma<1$ and (LABEL:cont15) in $\overset{f}{\leq}$. Similarly,
for (27) and (28), we also have

$\displaystyle\|\Pi\mathbf{z}^{k+1}\|^{2}\leq\frac{1+\sigma}{2}\|\Pi\mathbf{z}^{k}\|^{2}+\frac{4}{1-\sigma}\left(\frac{\mu^{2}\alpha^{2}}{\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}+\frac{\alpha^{2}}{\theta_{k}^{2}}\|\Pi\mathbf{s}^{k}\|^{2}\right),$
(31)
$\displaystyle\|\Pi\mathbf{x}^{k+1}\|^{2}\leq\frac{1+\sigma}{2}\|\Pi\mathbf{x}^{k}\|^{2}+\frac{2\theta_{k}^{2}}{1-\sigma}\|\Pi\mathbf{z}^{k+1}\|^{2}.$
(32)

Adding (30), (31), and (32) together with the weights $c_{1}$,
$c_{2}\theta_{k+1}^{2}$, and $c_{3}$, respectively, we have

$\displaystyle\begin{aligned}
&c_{1}\|\Pi\mathbf{s}^{k+1}\|^{2}+c_{2}\theta_{k+1}^{2}\|\Pi\mathbf{z}^{k+1}\|^{2}+c_{3}\|\Pi\mathbf{x}^{k+1}\|^{2}\\\
&~{}~{}\overset{g}{\leq}c_{1}\|\Pi\mathbf{s}^{k+1}\|^{2}+\left(c_{2}\theta_{k}^{2}+\frac{2c_{3}\theta_{k}^{2}}{1-\sigma}\right)\|\Pi\mathbf{z}^{k+1}\|^{2}+\frac{c_{3}(1+\sigma)}{2}\|\Pi\mathbf{x}^{k}\|^{2}\\\
&~{}~{}\leq\left(\frac{c_{1}(1+\sigma)}{2}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{4\alpha^{2}}{1-\sigma}\right)\|\Pi\mathbf{s}^{k}\|^{2}\\\
&~{}~{}\quad+\left(\frac{2c_{0}c_{1}}{1-\sigma}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{1+\sigma}{2}\right)\theta_{k}^{2}\|\Pi\mathbf{z}^{k}\|^{2}\\\
&~{}~{}\quad+\left(\frac{2c_{0}c_{1}}{1-\sigma}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{4\mu^{2}\alpha^{2}}{1-\sigma}+\frac{c_{3}(1+\sigma)}{2}\right)\|\Pi\mathbf{x}^{k}\|^{2}+\frac{2c_{1}}{1-\sigma}\theta_{k}^{2}\Phi^{k},\end{aligned}$

where we use $\theta_{k+1}\leq\theta_{k}$ and (32) in $\overset{g}{\leq}$.
Letting $c_{3}=\frac{9c_{0}c_{1}}{(1-\sigma)^{2}}$,
$c_{2}=\frac{80c_{0}c_{1}}{(1-\sigma)^{4}}\geq\frac{8c_{0}c_{1}}{(1-\sigma)^{2}}+\frac{8c_{3}}{(1-\sigma)^{2}}$,
and
$\alpha^{2}\leq\min\left\\{\frac{(1-\sigma)^{6}}{1600c_{0}},\frac{(1-\sigma)^{4}}{1600\mu^{2}}\right\\}$
such that

$\displaystyle\frac{c_{1}(1+\sigma)}{2}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{4\alpha^{2}}{1-\sigma}\leq\frac{c_{1}(1+\sigma)}{2}+\frac{400c_{0}c_{1}\alpha^{2}}{(1-\sigma)^{5}}\leq\frac{c_{1}(3+\sigma)}{4},$
$\displaystyle\frac{2c_{0}c_{1}}{1-\sigma}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{1+\sigma}{2}\leq\frac{2c_{0}c_{1}}{1-\sigma}+\frac{c_{2}(1+\sigma)}{2}+\frac{2c_{3}}{1-\sigma}\leq\frac{c_{2}(3+\sigma)}{4},$
$\displaystyle\frac{2c_{0}c_{1}}{1-\sigma}+\left(c_{2}+\frac{2c_{3}}{1-\sigma}\right)\frac{4\mu^{2}\alpha^{2}}{1-\sigma}+\frac{c_{3}(1+\sigma)}{2}\leq\frac{2c_{0}c_{1}}{1-\sigma}+\frac{400c_{0}c_{1}\mu^{2}\alpha^{2}}{(1-\sigma)^{5}}+\frac{c_{3}(1+\sigma)}{2}\leq\frac{c_{3}(3+\sigma)}{4},$

we have

$\displaystyle\begin{aligned}
&c_{1}\|\Pi\mathbf{s}^{k+1}\|^{2}+c_{2}\theta_{k+1}^{2}\|\Pi\mathbf{z}^{k+1}\|^{2}+c_{3}\|\Pi\mathbf{x}^{k+1}\|^{2}\\\
&~{}~{}\leq\frac{3+\sigma}{4}\left(c_{1}\|\Pi\mathbf{s}^{k}\|^{2}+c_{2}\theta_{k}^{2}\|\Pi\mathbf{z}^{k}\|^{2}+c_{3}\|\Pi\mathbf{x}^{k}\|^{2}\right)+\frac{2c_{1}}{1-\sigma}\theta_{k}^{2}\Phi^{k}\\\
&~{}~{}\leq\left(\frac{3+\sigma}{4}\right)^{k+1}\left(c_{1}\|\Pi\mathbf{s}^{0}\|^{2}+c_{2}\theta_{0}^{2}\|\Pi\mathbf{z}^{0}\|^{2}+c_{3}\|\Pi\mathbf{x}^{0}\|^{2}\right)+\frac{2c_{1}}{1-\sigma}\sum_{r=0}^{k}\left(\frac{3+\sigma}{4}\right)^{k-r}\theta_{r}^{2}\Phi^{r}.\end{aligned}$

From (25), $c_{2}>c_{3}$, and the initialization such that
$\Pi\mathbf{x}^{0}=\Pi\mathbf{y}^{0}=\Pi\mathbf{z}^{0}=0$, we have

$\displaystyle\begin{aligned}
\|\Pi\mathbf{y}^{k+1}\|^{2}\leq&\frac{2}{c_{3}}\left(c_{1}\|\Pi\mathbf{s}^{k+1}\|^{2}+c_{2}\theta_{k+1}^{2}\|\Pi\mathbf{z}^{k+1}\|^{2}+c_{3}\|\Pi\mathbf{x}^{k+1}\|^{2}\right)\\\
\leq&\left(\frac{3+\sigma}{4}\right)^{k+1}\frac{2c_{1}}{c_{3}}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{4c_{1}}{c_{3}(1-\sigma)}\sum_{r=0}^{k}\left(\frac{3+\sigma}{4}\right)^{k-r}\theta_{r}^{2}\Phi^{r}\\\
=&\left(\frac{3+\sigma}{4}\right)^{k+1}\frac{(1-\sigma)^{2}}{18(1+\frac{1}{\tau})L^{2}}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{1-\sigma}{9(1+\frac{1}{\tau})L^{2}}\sum_{r=0}^{k}\left(\frac{3+\sigma}{4}\right)^{k-r}\theta_{r}^{2}\Phi^{r},\end{aligned}$

which is exactly (23).

Having (23) at hand, we are ready to bound the term $(a)$ by $(b)$ appeared in
(LABEL:cont3). The remaining challenge is to upper bound the weighted
summation of $\|\Pi\mathbf{y}^{k}\|^{2}$.

###### Lemma 4

Suppose that Assumptions 1 and 2 hold with $\mu=0$. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{K}$ satisfy
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ with
$\theta_{0}=1$, let
$\alpha\leq\frac{(1-\sigma)^{3}}{80L\sqrt{1+\frac{1}{\tau}}}$. Then for
algorithm (11a)-(11d), we have

$\displaystyle\begin{aligned}
&\max\left\\{\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2},\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}\right\\}\\\
&~{}~{}\leq\frac{16}{3mL(1+\frac{1}{\tau})(1-\sigma)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{11}{mL(1+\frac{1}{\tau})(1-\sigma)^{2}}\sum_{r=0}^{K-1}\Phi^{r},\end{aligned}$
(33)

where $\tau$ and $\Phi^{r}$ are defined in Lemma 3.

###### Proof 3

We first give some properties of the sequence $\\{\theta_{k}\\}_{k=0}^{K}$.
From $\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ and
$\theta_{0}=1$, we have $\theta_{k}\leq\theta_{k-1}$,
$\frac{1}{\theta_{k}}-1\leq\frac{1}{\theta_{k-1}}$, and
$\frac{1}{\theta_{k}}-\frac{1}{2}\geq\frac{1}{\theta_{k-1}}$, which further
give

$\displaystyle\frac{1}{\theta_{k}}-\frac{1}{\theta_{k-1}}\leq
1,\qquad\frac{1}{k+1}\leq\theta_{k}\leq\frac{2}{k+1}.$ (34)

From (23), we get

$\displaystyle\begin{aligned}
\sum_{k=1}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2}\leq&\sum_{k=1}^{K}\frac{C_{1}L\rho^{k}}{2m\theta_{k}^{2}}+\sum_{k=1}^{K}\frac{C_{2}L}{2m\theta_{k}^{2}}\sum_{r=0}^{k-1}\rho^{k-1-r}\theta_{r}^{2}\Phi^{r}\\\
=&\frac{C_{1}L}{2m}\sum_{k=1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}+\frac{C_{2}L}{2m\rho}\sum_{k=1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{r=0}^{k-1}\frac{\theta_{r}^{2}}{\rho^{r}}\Phi^{r}\\\
=&\frac{C_{1}L}{2m}\sum_{k=1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}+\frac{C_{2}L}{2m\rho}\sum_{r=0}^{K-1}\frac{\theta_{r}^{2}}{\rho^{r}}\Phi^{r}\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}.\end{aligned}$
(35)

Recall that for scalers, $\theta_{k}$ means the value at iteration $k$, while
$\rho^{k}$ is its $k$th power. Next, we compute
$\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}$ for any $r\geq 0$. Denote
$S=\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}$ for simplicity. We have

$\rho
S=\sum_{k=r+1}^{K}\frac{\rho^{k+1}}{\theta_{k}^{2}}=\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k-1}^{2}}-\frac{\rho^{r+1}}{\theta_{r}^{2}}+\frac{\rho^{K+1}}{\theta_{K}^{2}},$

and

$S-\rho
S=\sum_{k=r+1}^{K}\rho^{k}\left(\frac{1}{\theta_{k}^{2}}-\frac{1}{\theta_{k-1}^{2}}\right)+\frac{\rho^{r+1}}{\theta_{r}^{2}}-\frac{\rho^{K+1}}{\theta_{K}^{2}}\overset{a}{=}\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k}}+\frac{\rho^{r+1}}{\theta_{r}^{2}}-\frac{\rho^{K+1}}{\theta_{K}^{2}},$

where we use $\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$
in $\overset{a}{=}$. It further gives

$\rho(1-\rho)S=\sum_{k=r+1}^{K}\frac{\rho^{k+1}}{\theta_{k}}+\frac{\rho^{r+2}}{\theta_{r}^{2}}-\frac{\rho^{K+2}}{\theta_{K}^{2}}=\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k-1}}-\frac{\rho^{r+1}}{\theta_{r}}+\frac{\rho^{K+1}}{\theta_{K}}+\frac{\rho^{r+2}}{\theta_{r}^{2}}-\frac{\rho^{K+2}}{\theta_{K}^{2}},$

and

$\displaystyle\begin{aligned} (1-\rho)^{2}S=&(1-\rho)S-\rho(1-\rho)S\\\
=&\sum_{k=r+1}^{K}\rho^{k}\left(\frac{1}{\theta_{k}}-\frac{1}{\theta_{k-1}}\right)+\frac{\rho^{r+1}}{\theta_{r}^{2}}-\frac{\rho^{K+1}}{\theta_{K}^{2}}+\frac{\rho^{r+1}}{\theta_{r}}-\frac{\rho^{K+1}}{\theta_{K}}-\frac{\rho^{r+2}}{\theta_{r}^{2}}+\frac{\rho^{K+2}}{\theta_{K}^{2}}\\\
=&\sum_{k=r+1}^{K}\rho^{k}\left(\frac{1}{\theta_{k}}-\frac{1}{\theta_{k-1}}\right)+\frac{(1-\rho)\rho^{r+1}}{\theta_{r}^{2}}-\frac{(1-\rho)\rho^{K+1}}{\theta_{K}^{2}}+\frac{\rho^{r+1}}{\theta_{r}}-\frac{\rho^{K+1}}{\theta_{K}}\\\
\overset{b}{\leq}&\sum_{k=r+1}^{K}\rho^{k}+\frac{(1-\rho)\rho^{r+1}}{\theta_{r}^{2}}+\frac{\rho^{r+1}}{\theta_{r}}\leq\frac{\rho^{r+1}}{1-\rho}+\frac{2\rho^{r+1}}{\theta_{r}^{2}},\end{aligned}$

where we use (34) in $\overset{b}{\leq}$. Thus, we get

$\displaystyle\sum_{k=r+1}^{K}\frac{\rho^{k}}{\theta_{k}^{2}}\leq\frac{1}{(1-\rho)^{2}}\left(\frac{\rho^{r+1}}{1-\rho}+\frac{2\rho^{r+1}}{\theta_{r}^{2}}\right)\leq\frac{3\rho^{r+1}}{(1-\rho)^{3}\theta_{r}^{2}}.$
(36)

Plugging into (35), it follows from $\Pi\mathbf{y}^{0}=0$ that

$\displaystyle\begin{aligned}
\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2}\leq&\frac{3C_{1}L\rho}{2m(1-\rho)^{3}}+\frac{3C_{2}L}{2m(1-\rho)^{3}}\sum_{r=0}^{K-1}\Phi^{r}\\\
\leq&\frac{16}{3mL(1+\frac{1}{\tau})(1-\sigma)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{11}{mL(1+\frac{1}{\tau})(1-\sigma)^{2}}\sum_{r=0}^{K-1}\Phi^{r},\end{aligned}$

where the last inequality uses the definitions of $C_{1}$, $C_{2}$, and $\rho$
given in Lemma 3. Replacing $\|\Pi\mathbf{y}^{k}\|$ by $\|\Pi\mathbf{x}^{k}\|$
in the above analysis, we have the same bound for
$\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}$.

In the next lemma, we bound the term $(c)$ by $(d)$ appeared in (LABEL:cont4)
in a similar way to the proof of Lemma 4.

###### Lemma 5

Suppose that Assumptions 1 and 2 hold with $\mu>0$. Let
$\alpha\leq\frac{(1-\sigma)^{3}}{80L\sqrt{1+\frac{1}{\tau}}}$ and
$\theta_{k}\equiv\theta=\frac{\sqrt{\mu\alpha}}{2}$. Then for algorithm
(11a)-(11d), we have

$\displaystyle\begin{aligned}
&\max\left\\{\sum_{k=0}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2},\sum_{k=0}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{x}^{k}\|^{2}\right\\}\\\
&~{}~{}\leq\frac{4(1-\sigma)}{27mL(1+\frac{1}{\tau})(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{8\theta^{2}}{27mL(1+\frac{1}{\tau})}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}},\end{aligned}$
(37)

where $\tau$ and $\Phi^{r}$ are defined in Lemma 3.

###### Proof 4

From (23), we get

$\displaystyle\begin{aligned}
&\sum_{k=1}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2}\\\
&~{}~{}\leq\sum_{k=1}^{K}\frac{C_{1}L\rho^{k}}{2m(1-\theta)^{k+1}}+\sum_{k=1}^{K}\frac{C_{2}L}{2m(1-\theta)^{k+1}}\sum_{r=0}^{k-1}\rho^{k-1-r}\theta^{2}\Phi^{r}\\\
&~{}~{}=\frac{C_{1}L}{2m(1-\theta)}\sum_{k=1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}+\frac{\theta^{2}C_{2}L}{2m\rho(1-\theta)}\sum_{k=1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}\sum_{r=0}^{k-1}\frac{\Phi^{r}}{\rho^{r}}\\\
&~{}~{}=\frac{C_{1}L}{2m(1-\theta)}\sum_{k=1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}+\frac{\theta^{2}C_{2}L}{2m\rho(1-\theta)}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{\rho^{r}}\sum_{k=r+1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}.\end{aligned}$

From the settings of $\theta$ and $\alpha$, we know
$\theta\leq\frac{1-\sigma}{16}$. Thus we have $\frac{\rho}{1-\theta}<1$,
$1-\theta-\rho\geq\frac{3(1-\sigma)}{16}$, and
$\sum_{k=r+1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}\leq\left(\frac{\rho}{1-\theta}\right)^{r}\frac{\rho}{1-\theta-\rho}$.
It follows from $\Pi\mathbf{y}^{0}=0$ that

$\displaystyle\begin{aligned}
\sum_{k=0}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2}\leq&\frac{C_{1}L}{2m(1-\theta)}\frac{\rho}{1-\theta-\rho}+\frac{\theta^{2}C_{2}L}{2m(1-\theta-\rho)}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}}\\\
\leq&\frac{4(1-\sigma)}{27mL(1+\frac{1}{\tau})(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{8\theta^{2}}{27mL(1+\frac{1}{\tau})}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}},\end{aligned}$

where the last inequality uses the definitions of $C_{1}$ and $C_{2}$ given in
Lemma 3 and $1-\theta-\rho\geq\frac{3(1-\sigma)}{16}$. Replacing
$\|\Pi\mathbf{y}^{k}\|$ by $\|\Pi\mathbf{x}^{k}\|$ in the above analysis, we
have the same bound for $\Pi\mathbf{x}^{k}$.

Now, we are ready to prove Theorems 1 and 2. We first prove Theorem 1.

###### Proof 5

Plugging (33) into (LABEL:cont3) and using the definition of $\Phi^{r}$ in
(24), we obtain

$\displaystyle\begin{aligned}
&\frac{F(\overline{x}^{K+1})-F(x^{*})}{\theta_{K}^{2}}+\frac{1}{2\alpha}\|\overline{z}^{K+1}-x^{*}\|^{2}\\\
&~{}~{}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{16}{3mL(1+\frac{1}{\tau})(1-\sigma)}\|\Pi\mathbf{s}^{0}\|^{2}\\\
&~{}~{}\quad-\sum_{k=0}^{K}\left(\left(\frac{1}{2\alpha}-\frac{L}{2}-\frac{22L}{(1-\sigma)^{2}}\right)\|\overline{z}^{t+1}-\overline{z}^{t}\|^{2}+\frac{1}{\theta_{k-1}^{2}}\left(1-\frac{22(1+\tau)}{(1+\frac{1}{\tau})(1-\sigma)^{2}}\right)D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)\\\
&~{}~{}\overset{a}{\leq}\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{16}{3mL(1+\frac{1}{\tau})(1-\sigma)}\|\Pi\mathbf{s}^{0}\|^{2}-\sum_{k=0}^{K}\left(\frac{1}{4\alpha}\|\overline{z}^{t+1}-\overline{z}^{t}\|^{2}+\frac{1}{2\theta_{k-1}^{2}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)\\\
&~{}~{}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}-\frac{1}{5mL}\sum_{r=0}^{K-1}\Phi^{r},\end{aligned}$

where in $\overset{a}{\leq}$ we let $\tau=\frac{(1-\sigma)^{2}}{44}$ so to
have $\frac{22(1+\tau)}{(1+\frac{1}{\tau})(1-\sigma)^{2}}=\frac{1}{2}$,
$\alpha\leq\frac{(1-\sigma)^{4}}{537L}\leq\frac{(1-\sigma)^{3}}{80L\sqrt{1+\frac{1}{\tau}}}$,
and $\frac{1}{4\alpha}\geq\frac{L}{2}+\frac{22L}{(1-\sigma)^{2}}$. So we have

$\displaystyle
F(\overline{x}^{K+1})-F(x^{*})\leq\theta_{K}^{2}\left(\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}\right),$
(38)
$\displaystyle\frac{1}{5mL}\sum_{r=0}^{K-1}\Phi^{r}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}.$
(39)

It follows from (33) that

$\displaystyle\begin{aligned}
&\max\left\\{\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2},\sum_{k=0}^{K}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}\right\\}\\\
&~{}~{}\leq\frac{16}{3mL(1+\frac{1}{\tau})(1-\sigma)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{11}{mL(1+\frac{1}{\tau})(1-\sigma)^{2}}\sum_{r=0}^{K-1}\Phi^{r}\\\
&~{}~{}\leq\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{1}{4mL}\sum_{r=0}^{K-1}\Phi^{r}\\\
&~{}~{}\leq\frac{5}{8\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{9(1-\sigma)}{32mL}\|\Pi\mathbf{s}^{0}\|^{2}.\end{aligned}$
(40)

From (34), we have the conclusions.

In the next lemma, we measure the convergence rate at $x_{(i)}^{K}$ for any
$i=1,...,m$.

###### Lemma 6

Under the settings of Theorem 1, we have for any $k\leq K$,

$\displaystyle\begin{aligned}
F(x_{(i)}^{k})-F(x^{*})\leq\frac{4}{k^{2}}\max\left\\{\frac{\sqrt{m}(1-\sigma)}{L\alpha},8m\right\\}\left(\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}\right).\end{aligned}$

###### Proof 6

We first bound $F(x_{(i)}^{k})-F(\overline{x}^{k})$ for any $i$. From Lemma 1,
we have

$\displaystyle\begin{aligned}
F(x_{(i)}^{k})\leq&f(\overline{y}^{k-1},\mathbf{y}^{k-1})+\left\langle\overline{s}^{k-1},x_{(i)}^{k}-\overline{y}^{k-1}\right\rangle+\frac{L}{2}\|x_{(i)}^{k}-\overline{y}^{k-1}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k-1}\|^{2}\\\
\leq&F(\overline{x}^{k})+\left\langle\overline{s}^{k-1},x_{(i)}^{k}-\overline{x}^{k}\right\rangle+L\|x_{(i)}^{k}-\overline{x}^{k}\|^{2}+L\|\overline{x}^{k}-\overline{y}^{k-1}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k-1}\|^{2}\\\
\overset{a}{\leq}&F(\overline{x}^{k})+\frac{\theta_{k-1}}{\alpha}\|\overline{z}^{k}-\overline{z}^{k-1}\|\|\Pi\mathbf{x}^{k}\|+L\|\Pi\mathbf{x}^{k}\|^{2}+L\theta_{k-1}^{2}\|\overline{z}^{k}-\overline{z}^{k-1}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k-1}\|^{2},\end{aligned}$

where we use (13c) with $\mu=0$, (13a), and (13d) in $\overset{a}{\leq}$. From
the definition of $\Phi^{r}$ in (24), it follows from (39) that for any $k\leq
K$,

$\|\overline{z}^{k}-\overline{z}^{k-1}\|^{2}\leq\frac{\Phi^{k-1}}{2mL^{2}(1+\frac{1}{\tau})}\overset{b}{\leq}\frac{5(1-\sigma)^{2}}{88L}\left(\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma}{8mL}\|\Pi\mathbf{s}^{0}\|^{2}\right),$

where $\overset{b}{\leq}$ uses the setting of $\tau=\frac{(1-\sigma)^{2}}{44}$
given in the proof of Theorem 1. From (38), (LABEL:cont34), and (34), we have
the conclusion.

Next, we prove Theorem 2.

###### Proof 7

Plugging (LABEL:cont29) into (LABEL:cont4) and using the definition of
$\Phi^{r}$ in (24), we have

$\displaystyle\begin{aligned}
&\frac{1}{(1-\theta)^{K+1}}\left(F(\overline{x}^{K+1})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{K+1}-x^{*}\|^{2}\right)\\\
&~{}~{}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{27mL(1+\frac{1}{\tau})(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}\\\
&~{}~{}\quad-\sum_{k=0}^{K}\left(\frac{1}{(1-\theta)^{k}}\left(1-\frac{16(1+\tau)}{27(1+\frac{1}{\tau})}\right)D_{f}(\overline{x}^{k},\mathbf{y}^{k})+\frac{1}{(1-\theta)^{k+1}}\left(\frac{\theta^{2}}{2\alpha}-\frac{L\theta^{2}}{2}-\frac{16L\theta^{2}}{27}\right)\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}\right)\\\
&~{}~{}\overset{a}{\leq}F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{27m(1+\frac{1}{\tau})L(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}\\\
&~{}~{}\quad-\sum_{k=0}^{K}\left(\frac{1}{2(1-\theta)^{k}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})+\frac{\theta^{2}}{4\alpha(1-\theta)^{k+1}}\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}\right)\\\
&~{}~{}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{59mL(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}-\frac{8\theta^{2}}{59mL}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}},\end{aligned}$

where in $\overset{a}{\leq}$ we let $\tau=\frac{27}{32}$ so to have
$\frac{16(1+\tau)}{27(1+\frac{1}{\tau})}=\frac{1}{2}$,
$\alpha\leq\frac{(1-\sigma)^{3}}{119L}\leq\frac{(1-\sigma)^{3}}{80L\sqrt{1+\frac{1}{\tau}}}$,
and $\frac{1}{4\alpha}\geq\frac{L}{2}+\frac{16L}{27}$. Thus, we have the first
conclusion and

$\displaystyle\frac{8\theta^{2}}{59mL}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{59mL(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}.$

It follows from (LABEL:cont29) that

$\displaystyle\begin{aligned}
&\sum_{k=0}^{K}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{x}^{k}\|^{2}\\\
&~{}~{}\leq\frac{4(1-\sigma)}{27mL(1+\frac{1}{\tau})(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{8\theta^{2}}{27mL(1+\frac{1}{\tau})}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}}\\\
&~{}~{}=\frac{4(1-\sigma)}{59mL(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}+\frac{8\theta^{2}}{59mL}\sum_{r=0}^{K-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}}\\\
&~{}~{}\leq
2\left(F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{4(1-\sigma)}{59mL(1-\theta)}\|\Pi\mathbf{s}^{0}\|^{2}\right).\end{aligned}$

Thus, we have the second conclusion.

###  4.3 Bounding the Consensus Error over Time-varying Graphs

In this section, we consider algorithm (12a)-(12d) over time-varying graphs.
Recall that Lemma 2 still holds for the time-varying weight matrices. Thus, we
only need to bound the consensus error. Our analysis follows the same proof
framework in the previous section for static graph, but with more complex
details.

In the the next lemma, we first give the analogy counterparts of (30)-(32).

###### Lemma 7

Suppose that Assumptions 1 and 3 hold with $\mu\geq 0$. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{K}$ satisfy
$\frac{\theta_{k}}{1.62}\leq\theta_{k+1}\leq\theta_{k}\leq 1$. Then, we have
for any $k\geq\gamma-1$,

$\displaystyle\|\Pi\mathbf{s}^{k+1}\|^{2}\leq\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{k-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k}\left(\theta_{r}^{2}\Phi^{r}+c_{0}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}+c_{0}\|\Pi\mathbf{x}^{r}\|^{2}\right),$
(41)
$\displaystyle\|\Pi\mathbf{x}^{k+1}\|^{2}\leq\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{x}^{k-\gamma+1}\|^{2}+\frac{5.5\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+2}^{k+1}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2},$
(42)
$\displaystyle\theta_{k+1}^{2}\|\Pi\mathbf{z}^{k+1}\|^{2}\leq\frac{1+\sigma_{\gamma}}{2}\theta_{k-\gamma+1}^{2}\|\Pi\mathbf{z}^{k-\gamma+1}\|^{2}+\frac{4\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k}\left(\mu^{2}\alpha^{2}\|\Pi\mathbf{x}^{r}\|^{2}+\alpha^{2}\|\Pi\mathbf{s}^{r}\|^{2}\right),$
(43)

where we denote $c_{0}=4L^{2}\left(1+\frac{1}{\tau}\right)$, and $\tau$ and
$\Phi^{r}$ are defined in Lemma 3.

###### Proof 8

From (12b) and the definition of $W^{k,\gamma}$ in (6), we have for any
$k\geq\gamma-1$,

$\displaystyle\begin{aligned}
\mathbf{s}^{k+1}=&W_{1}^{k+1}\mathbf{s}^{k}+\nabla f(\mathbf{y}^{k+1})-\nabla
f(\mathbf{y}^{k})\\\
=&\left(\prod_{t=k-\gamma+2}^{k+1}W_{1}^{t}\right)\mathbf{s}^{k-\gamma+1}+\sum_{r=k-\gamma+1}^{k}\left(\prod_{t=r+1}^{k}W_{1}^{t+1}\right)(\nabla
f(\mathbf{y}^{r+1})-\nabla f(\mathbf{y}^{r}))\\\
=&W_{1}^{k+1,\gamma}\mathbf{s}^{k-\gamma+1}+\sum_{r=k-\gamma+1}^{k}W_{1}^{k+1,k-r}(\nabla
f(\mathbf{y}^{r+1})-\nabla f(\mathbf{y}^{r})),\end{aligned}$

where we denote $\prod_{t=k+1}^{k}W_{1}^{t+1}=I$. Multiplying both sides by
$\Pi$, using (7) and (8), it gives

$\displaystyle\|\Pi\mathbf{s}^{k+1}\|\leq\sigma_{\gamma}\|\Pi\mathbf{s}^{k-\gamma+1}\|+\sum_{r=k-\gamma+1}^{k}\|\nabla
f(\mathbf{y}^{r+1})-\nabla f(\mathbf{y}^{r})\|.$ (44)

Similar to (30), squaring both sides of (44) yields

$\displaystyle\qquad\begin{aligned}
\|\Pi\mathbf{s}^{k+1}\|^{2}\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{k-\gamma+1}\|^{2}+\frac{2}{1-\sigma_{\gamma}}\left(\sum_{r=k-\gamma+1}^{k}\|\nabla
f(\mathbf{y}^{r+1})-\nabla f(\mathbf{y}^{r})\|\right)^{2}\\\
\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{k-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k}\|\nabla
f(\mathbf{y}^{r+1})-\nabla f(\mathbf{y}^{r})\|^{2}.\end{aligned}$ (45)

From (LABEL:cont15), we have (41). It follows from (12d) that

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=&(1-\theta_{k})W_{3}^{k}\mathbf{x}^{k}+\theta_{k}\mathbf{z}^{k+1}\\\
=&\left(\prod_{t=k-\gamma+1}^{k}(1-\theta_{t})W_{3}^{t}\right)\mathbf{x}^{k-\gamma+1}+\sum_{r=k-\gamma+1}^{k}\left(\prod_{t=r+1}^{k}(1-\theta_{t})W_{3}^{t}\right)\theta_{r}\mathbf{z}^{r+1}\\\
=&W_{3}^{k,\gamma}\mathbf{x}^{k-\gamma+1}\prod_{t=k-\gamma+1}^{k}(1-\theta_{t})+\sum_{r=k-\gamma+1}^{k}W_{3}^{k,k-r}\theta_{r}\mathbf{z}^{r+1}\prod_{t=r+1}^{k}(1-\theta_{t}).\end{aligned}$

Similar to (44) and (45), we also have

$\displaystyle\|\Pi\mathbf{x}^{k+1}\|\leq\sigma_{\gamma}\|\Pi\mathbf{x}^{k-\gamma+1}\|+\sum_{r=k-\gamma+1}^{k}\theta_{r}\|\Pi\mathbf{z}^{r+1}\|=\sigma_{\gamma}\|\Pi\mathbf{x}^{k-\gamma+1}\|+\sum_{r=k-\gamma+2}^{k+1}\theta_{r-1}\|\Pi\mathbf{z}^{r}\|,$

and

$\displaystyle\begin{aligned}
\|\Pi\mathbf{x}^{k+1}\|^{2}\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{x}^{k-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+2}^{k+1}\theta_{r-1}^{2}\|\Pi\mathbf{z}^{r}\|^{2}.\end{aligned}$

Using $\theta_{r-1}\leq 1.62\theta_{r}$, we obtain (42). Similarly, for (12c),
we have

$\displaystyle\begin{aligned}
\mathbf{z}^{k+1}=&\frac{\theta_{k}}{\theta_{k}+\mu\alpha}W_{2}^{k}\mathbf{z}^{k}+\frac{\mu\alpha}{\theta_{k}+\mu\alpha}W_{2}^{k}\mathbf{y}^{k}-\frac{\alpha}{\theta_{k}+\mu\alpha}\mathbf{s}^{k}\\\
\overset{a}{=}&\frac{\theta_{k}(1+\mu\alpha)}{\theta_{k}+\mu\alpha}W_{2}^{k}\mathbf{z}^{k}+\frac{\mu\alpha(1-\theta_{k})}{\theta_{k}+\mu\alpha}W_{2}^{k}\mathbf{x}^{k}-\frac{\alpha}{\theta_{k}+\mu\alpha}\mathbf{s}^{k}\\\
=&\left(\prod_{t=k-\gamma+1}^{k}\frac{\theta_{t}(1+\mu\alpha)}{\theta_{t}+\mu\alpha}W_{2}^{t}\right)\mathbf{z}^{k-\gamma+1}\\\
&+\sum_{r=k-\gamma+1}^{k}\left(\prod_{t=r+1}^{k}\frac{\theta_{t}(1+\mu\alpha)}{\theta_{t}+\mu\alpha}W_{2}^{t}\right)\left(\frac{\mu\alpha(1-\theta_{r})}{\theta_{r}+\mu\alpha}W_{2}^{r}\mathbf{x}^{r}-\frac{\alpha}{\theta_{r}+\mu\alpha}\mathbf{s}^{r}\right)\\\
=&W_{2}^{k,\gamma}\mathbf{z}^{k-\gamma+1}\prod_{t=k-\gamma+1}^{k}\frac{\theta_{t}(1+\mu\alpha)}{\theta_{t}+\mu\alpha}\\\
&+\sum_{r=k-\gamma+1}^{k}W_{2}^{k,k-r}\left(\frac{\mu\alpha(1-\theta_{r})}{\theta_{r}+\mu\alpha}W_{2}^{r}\mathbf{x}^{r}-\frac{\alpha}{\theta_{r}+\mu\alpha}\mathbf{s}^{r}\right)\prod_{t=r+1}^{k}\frac{\theta_{t}(1+\mu\alpha)}{\theta_{t}+\mu\alpha},\end{aligned}$

and

$\displaystyle\begin{aligned}
\|\Pi\mathbf{z}^{k+1}\|\overset{b}{\leq}&\sigma_{\gamma}\|\Pi\mathbf{z}^{k-\gamma+1}\|+\sum_{r=k-\gamma+1}^{k}\left(\frac{\mu\alpha(1-\theta_{r})}{\theta_{r}+\mu\alpha}\|\Pi\mathbf{x}^{r}\|+\frac{\alpha}{\theta_{r}+\mu\alpha}\|\Pi\mathbf{s}^{r}\|\right)\\\
\leq&\sigma_{\gamma}\|\Pi\mathbf{z}^{k-\gamma+1}\|+\sum_{r=k-\gamma+1}^{k}\left(\frac{\mu\alpha}{\theta_{r}}\|\Pi\mathbf{x}^{r}\|+\frac{\alpha}{\theta_{r}}\|\Pi\mathbf{s}^{r}\|\right),\end{aligned}$

where we use (12a) in $\overset{a}{=}$,
$\frac{\theta_{t}(1+\mu\alpha)}{\theta_{t}+\mu\alpha}\leq 1$ with
$\theta_{t}\leq 1$ in $\overset{b}{\leq}$. Similar to (45), squaring both
sides yields

$\displaystyle\|\Pi\mathbf{z}^{k+1}\|^{2}\leq\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{z}^{k-\gamma+1}\|^{2}+\frac{4\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k}\left(\frac{\mu^{2}\alpha^{2}}{\theta_{r}^{2}}\|\Pi\mathbf{x}^{r}\|^{2}+\frac{\alpha^{2}}{\theta_{r}^{2}}\|\Pi\mathbf{s}^{r}\|^{2}\right).$

Multiplying both sides by $\theta_{k+1}^{2}$ and using the non-increasing of
$\\{\theta_{k}\\}$, it further gives (43)

Motivated by the proof of Lemma 3, we want to construct a linear combination
of the consensus errors. However, due to the time-varying graphs and the
$\gamma$-step joint spectrum property in Assumption 3, we see from (41)-(43)
that they shrink every $\gamma$ iterations, rather than every iteration. By
exploiting the special structures in (41)-(43), we define the following
quantities:

$\displaystyle\begin{aligned}
&\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}=\max_{r=k+1,...,k+\gamma}\|\Pi\mathbf{s}^{r}\|^{2},\quad\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}=\max_{r=k+1,...,k+\gamma}\|\Pi\mathbf{x}^{r}\|^{2},\\\
&\mathcal{M}_{\mathbf{y}}^{k+\gamma,\gamma}=\max_{r=k+1,...,k+\gamma}\|\Pi\mathbf{y}^{r}\|^{2},\quad\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}=\max_{r=k+1,...,k+\gamma}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}.\end{aligned}$

Motivated by (23), we define the following quantity in the form of summation,
instead of the maximum:

$\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}=\sum_{r=k}^{k+\gamma-1}\theta_{r}^{2}\Phi^{r}.$

The next lemma is an analogy counterpart of Lemma 3. Unlike the classical
analysis relying on the small gain theorem (Nedić et al., 2017), which is
unclear how to be used in the accelerated methods and especially for
nonstrongly convex problems, our main idea is to construct a linear
combination of $\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}$,
$\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}$, and
$\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}$ with carefully designed weights
such that it shrinks geometrically with the additional error term
$\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}$, which is crucial to extend our
analysis over static graph to time-varying graphs in a unified framework, both
for nonstrongly convex and strongly convex problems.

###### Lemma 8

Under the settings of Lemma 7, letting
$\alpha\leq\frac{(1-\sigma_{\gamma})^{3}}{3385L\gamma^{3}\sqrt{1+\frac{1}{\tau}}}$,
we have for any $t\geq 0$,

$\displaystyle\begin{aligned}
\max\left\\{\mathcal{M}_{\mathbf{y}}^{(t+1)\gamma,\gamma},\mathcal{M}_{\mathbf{x}}^{(t+1)\gamma,\gamma}\right\\}\leq
C_{3}\rho^{t\gamma}+C_{4}\sum_{s=0}^{(t+1)\gamma-1}\rho^{(t-1)\gamma-s}\theta_{s}^{2}\Phi^{s}.\end{aligned}$
(46)

where $\rho=\sqrt[\gamma]{1-\frac{1-\sigma_{\gamma}}{5}}$,
$C_{3}=\left(\frac{(1-\sigma_{\gamma})^{2}}{162L^{2}\gamma^{2}(1+\frac{1}{\tau})}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\frac{442\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}+2\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}\right)$,
and $C_{4}=\frac{1-\sigma_{\gamma}}{38L^{2}\gamma(1+\frac{1}{\tau})}$.

###### Proof 9

For any $t$ satisfying $k\leq t\leq k+\gamma-1$ with $k\geq\gamma$, we can
relax (41) to

$\displaystyle\begin{aligned}
\|\Pi\mathbf{s}^{t+1}\|^{2}\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{t-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=t-\gamma+1}^{t}\left(\theta_{r}^{2}\Phi^{r}+c_{0}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}+c_{0}\|\Pi\mathbf{x}^{r}\|^{2}\right)\\\
\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{t-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma}^{k+\gamma-1}\theta_{r}^{2}\Phi^{r}+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k+\gamma}\left(c_{0}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}+c_{0}\|\Pi\mathbf{x}^{r}\|^{2}\right)\\\
\leq&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{t-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right)\\\
&+\frac{2\gamma}{1-\sigma_{\gamma}}\sum_{r=k-\gamma+1}^{k+\gamma}\left(c_{0}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\right)\\\
=&\frac{1+\sigma_{\gamma}}{2}\|\Pi\mathbf{s}^{t-\gamma+1}\|^{2}+\frac{2\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right)\\\
&+\frac{4\gamma^{2}}{1-\sigma_{\gamma}}\left(c_{0}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\right).\end{aligned}$

Taking the maximum over $t=k,k+1,...,k+\gamma-1$ on both side, we have

$\displaystyle\begin{aligned}
\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}\leq&\frac{1+\sigma_{\gamma}}{2}\mathcal{M}_{\mathbf{s}}^{k,\gamma}+\frac{2\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right)\\\
&+\frac{4\gamma^{2}}{1-\sigma_{\gamma}}\left(c_{0}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k,\gamma}+c_{0}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\right).\end{aligned}$

Similarly, for (43) and (42), we also have

$\displaystyle\begin{aligned}
\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}\leq&\frac{1+\sigma_{\gamma}}{2}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+\frac{8\gamma^{2}}{1-\sigma_{\gamma}}\left(\mu^{2}\alpha^{2}\mathcal{M}_{\mathbf{x}}^{k,\gamma}+\mu^{2}\alpha^{2}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}+\alpha^{2}\mathcal{M}_{\mathbf{s}}^{k,\gamma}+\alpha^{2}\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}\right),\\\
\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\leq&\frac{1+\sigma_{\gamma}}{2}\mathcal{M}_{\mathbf{x}}^{k,\gamma}+\frac{11\gamma^{2}}{1-\sigma_{\gamma}}\left(\mathcal{M}_{\mathbf{z}}^{k,\gamma}+\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}\right),\end{aligned}$

where for the second one, the relaxation of
$\sum_{r=t-\gamma+2}^{t+1}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}\leq\sum_{r=k-\gamma+1}^{k+\gamma}\theta_{r}^{2}\|\Pi\mathbf{z}^{r}\|^{2}$
also holds for any $t$ satisfying $k\leq t\leq k+\gamma-1$.

Adding the above three inequalities together with weights $c_{1}$, $c_{2}$,
and $c_{3}$, respectively, we have

$\displaystyle\begin{aligned}
&c_{1}\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\\\
&~{}~{}\leq\frac{8c_{2}\gamma^{2}\alpha^{2}}{1-\sigma_{\gamma}}\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}+\left(\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{11c_{3}\gamma^{2}}{1-\sigma_{\gamma}}\right)\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+\left(\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{8c_{2}\gamma^{2}\mu^{2}\alpha^{2}}{1-\sigma_{\gamma}}\right)\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\\\
&~{}~{}\quad+\left(\frac{c_{1}(1+\sigma_{\gamma})}{2}+\frac{8c_{2}\gamma^{2}\alpha^{2}}{1-\sigma_{\gamma}}\right)\mathcal{M}_{\mathbf{s}}^{k,\gamma}+\left(\frac{c_{2}(1+\sigma_{\gamma})}{2}+\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{11c_{3}\gamma^{2}}{1-\sigma_{\gamma}}\right)\mathcal{M}_{\mathbf{z}}^{k,\gamma}\\\
&~{}~{}\quad+\left(\frac{c_{3}(1+\sigma_{\gamma})}{2}+\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{8c_{2}\gamma^{2}\mu^{2}\alpha^{2}}{1-\sigma_{\gamma}}\right)\mathcal{M}_{\mathbf{x}}^{k,\gamma}+\frac{2c_{1}\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right).\end{aligned}$

We want to choose $c_{1}$, $c_{2}$, $c_{3}$, and $\alpha$ such that the
following inequalities hold,

$\displaystyle\begin{aligned}
&\frac{8c_{2}\gamma^{2}\alpha^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{1}(1-\sigma_{\gamma})}{20},\hskip
79.6678pt\frac{c_{1}(1+\sigma_{\gamma})}{2}+\frac{8c_{2}\gamma^{2}\alpha^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{1}(3+\sigma_{\gamma})}{4},\\\
\\\
&\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{11c_{3}\gamma^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{2}(1-\sigma_{\gamma})}{20},\hskip
36.98866pt\frac{c_{2}(1+\sigma_{\gamma})}{2}+\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{11c_{3}\gamma^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{2}(3+\sigma_{\gamma})}{4},\\\
\\\
&\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{8c_{2}\gamma^{2}\mu^{2}\alpha^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{3}(1-\sigma_{\gamma})}{20},\qquad\frac{c_{3}(1+\sigma_{\gamma})}{2}+\frac{4c_{1}c_{0}\gamma^{2}}{1-\sigma_{\gamma}}+\frac{8c_{2}\gamma^{2}\mu^{2}\alpha^{2}}{1-\sigma_{\gamma}}\leq\frac{c_{3}(3+\sigma_{\gamma})}{4},\end{aligned}$

which are satisfied if the three inequalities in the left column hold.
Accordingly, we can choose
$c_{3}=\frac{81c_{1}c_{0}\gamma^{2}}{(1-\sigma_{\gamma})^{2}}$,
$c_{2}=\frac{17900c_{1}c_{0}\gamma^{4}}{(1-\sigma_{\gamma})^{4}}\geq\frac{80c_{1}c_{0}\gamma^{2}}{(1-\sigma_{\gamma})^{2}}+\frac{220c_{3}\gamma^{2}}{(1-\sigma_{\gamma})^{2}}$,
and
$\alpha^{2}\leq\min\left\\{\frac{(1-\sigma_{\gamma})^{6}}{2864000c_{0}\gamma^{6}},\frac{(1-\sigma_{\gamma})^{4}}{2864000\mu^{2}\gamma^{4}}\right\\}$.
Thus, we have for any $k\geq\gamma$,

$\displaystyle\begin{aligned}
&\frac{19+\sigma_{\gamma}}{20}\left(c_{1}\mathcal{M}_{\mathbf{s}}^{k+\gamma,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{k+\gamma,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{k+\gamma,\gamma}\right)\\\
&~{}~{}\leq\frac{3+\sigma_{\gamma}}{4}\left(c_{1}\mathcal{M}_{\mathbf{s}}^{k,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{k,\gamma}\right)+\frac{2c_{1}\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right)\\\
&~{}~{}\leq\frac{19+\sigma_{\gamma}}{20}\left(1-\frac{1-\sigma_{\gamma}}{5}\right)\left(c_{1}\mathcal{M}_{\mathbf{s}}^{k,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{k,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{k,\gamma}\right)+\frac{2c_{1}\gamma}{1-\sigma_{\gamma}}\left(\mathcal{S}_{\phi}^{k-1,\gamma}+\mathcal{S}_{\phi}^{k+\gamma-1,\gamma}\right),\end{aligned}$

and

$\displaystyle\begin{aligned}
&c_{1}\mathcal{M}_{\mathbf{s}}^{(t+1)\gamma,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{(t+1)\gamma,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{(t+1)\gamma,\gamma}\\\
&~{}~{}\leq\left(1-\frac{1-\sigma_{\gamma}}{5}\right)^{t}\left(c_{1}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}\right)\\\
&~{}~{}\quad+\frac{40c_{1}\gamma}{19(1-\sigma_{\gamma})}\sum_{r=1}^{t}\left(1-\frac{1-\sigma_{\gamma}}{5}\right)^{t-r}\left(\mathcal{S}_{\phi}^{r\gamma-1,\gamma}+\mathcal{S}_{\phi}^{(r+1)\gamma-1,\gamma}\right).\end{aligned}$
(47)

It follows from (25) and $c_{2}>c_{3}$ that

$\displaystyle\frac{c_{3}}{2}\max\left\\{\mathcal{M}_{\mathbf{y}}^{(t+1)\gamma,\gamma},\mathcal{M}_{\mathbf{x}}^{(t+1)\gamma,\gamma}\right\\}\leq
c_{1}\mathcal{M}_{\mathbf{s}}^{(t+1)\gamma,\gamma}+c_{2}\mathcal{M}_{\mathbf{z}}^{(t+1)\gamma,\gamma}+c_{3}\mathcal{M}_{\mathbf{x}}^{(t+1)\gamma,\gamma}.$

On the other hand, denoting
$\rho=\sqrt[\gamma]{1-\frac{1-\sigma_{\gamma}}{5}}$, we have

$\displaystyle\begin{aligned}
&\sum_{r=1}^{t}\rho^{\gamma(t-r)}\left(\mathcal{S}_{\phi}^{r\gamma-1,\gamma}+\mathcal{S}_{\phi}^{(r+1)\gamma-1,\gamma}\right)=\rho^{\gamma
t}\sum_{r=1}^{t}\left(\frac{1}{\rho^{\gamma}}\right)^{r}\left(\sum_{s=(r-1)\gamma}^{r\gamma-1}\theta_{s}^{2}\Phi^{s}+\sum_{s=r\gamma}^{(r+1)\gamma-1}\theta_{s}^{2}\Phi^{s}\right)\\\
&~{}~{}=\rho^{\gamma
t}\sum_{s=0}^{t\gamma-1}\left(\frac{1}{\rho^{\gamma}}\right)^{\lfloor\frac{s}{\gamma}\rfloor+1}\theta_{s}^{2}\Phi^{s}+\rho^{\gamma
t}\sum_{s=\gamma}^{(t+1)\gamma-1}\left(\frac{1}{\rho^{\gamma}}\right)^{\lfloor\frac{s}{\gamma}\rfloor}\theta_{s}^{2}\Phi^{s}\\\
&~{}~{}\leq 2\rho^{\gamma
t}\sum_{s=0}^{(t+1)\gamma-1}\left(\frac{1}{\rho^{\gamma}}\right)^{\frac{s}{\gamma}+1}\theta_{s}^{2}\Phi^{s}=2\sum_{s=0}^{(t+1)\gamma-1}\rho^{(t-1)\gamma-s}\theta_{s}^{2}\Phi^{s}.\end{aligned}$

Plugging the above two inequalities and the settings of $c_{3}$ and $c_{0}$
into (LABEL:cont22), we have the conclusion.

Following the same proof framework over the static graph, our next step is to
bound the weighted summation of $\|\Pi\mathbf{y}^{k}\|^{2}$. However, the
details are more complex. The proof of Lemma 4 provides some insights.

###### Lemma 9

Suppose that Assumptions 1 and 3 hold with $\mu=0$. Let the sequence
$\\{\theta_{k}\\}_{k=0}^{T\gamma}$ satisfy
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ with
$\theta_{0}=1$, let
$\alpha\leq\frac{(1-\sigma_{\gamma})^{3}}{3385L\gamma^{3}\sqrt{1+\frac{1}{\tau}}}$.
Then for algorithm (12a)-(12d), we have

$\displaystyle\begin{aligned}
&\max\left\\{\sum_{k=0}^{T\gamma}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2},\sum_{k=0}^{T\gamma}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}\right\\}\\\
&~{}~{}\leq\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}+\frac{10\gamma^{2}}{mL(1+\frac{1}{\tau})(1-\sigma_{\gamma})^{2}}\sum_{s=0}^{T\gamma-1}\Phi^{s},\end{aligned}$
(48)

where $\tau$ and $\Phi^{r}$ are defined in Lemma 3, and $C_{3}$ is defined in
Lemma 8.

###### Proof 10

We first verify $\theta_{k}\leq 1.62\theta_{k+1}$ for all $k\geq 0$, which is
required in Lemmas 7 and 8. In fact, from
$\frac{1-\theta_{k+1}}{\theta_{k+1}^{2}}=\frac{1}{\theta_{k}^{2}}$ and
$\theta_{0}=1$, we have
$\frac{\theta_{k}}{\theta_{k+1}}=\frac{1}{\sqrt{1-\theta_{k+1}}}\in(1,\frac{1}{\sqrt{1-\theta_{1}}}]\in(1,1.62]$
for any $k\geq 0$. Next, we upper and lower bound $\rho$. From the definition
of $\rho=\sqrt[\gamma]{1-\frac{1-\sigma_{\tau}}{5}}$ and the fact that
$(1-\frac{x}{\gamma})^{\gamma}\geq 1-x$ for any $x\in(0,1)$ and $\gamma\geq
1$, we know

$\rho\leq
1-\frac{1-\sigma_{\gamma}}{5\gamma},\qquad\rho^{\gamma}\geq\frac{4}{5}.$ (49)

The remaining proof is similar to that of Lemma 4. From the definition of
$\mathcal{M}_{\mathbf{y}}^{t\gamma,\gamma}$ and (46), we have

$\displaystyle\begin{aligned}
&\sum_{k=1}^{T\gamma}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2}=\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{L}{2m\theta_{t\gamma+r}^{2}}\|\Pi\mathbf{y}^{t\gamma+r}\|^{2}\leq\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{L}{2m\theta_{t\gamma+r}^{2}}\mathcal{M}_{\mathbf{y}}^{(t+1)\gamma,\gamma}\\\
&~{}~{}\leq\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{C_{3}L\rho^{t\gamma}}{2m\theta_{t\gamma+r}^{2}}+\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{C_{4}L}{2m\theta_{t\gamma+r}^{2}}\sum_{s=0}^{(t+1)\gamma-1}\rho^{(t-1)\gamma-s}\theta_{s}^{2}\Phi^{s}\\\
&~{}~{}\leq\frac{C_{3}L}{2m}\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{\rho^{t\gamma+r}}{\rho^{\gamma}\theta_{t\gamma+r}^{2}}+\frac{C_{4}L}{2m}\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{\rho^{t\gamma+r}}{\rho^{2\gamma}\theta_{t\gamma+r}^{2}}\sum_{s=0}^{(t+1)\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\\\
&~{}~{}\overset{a}{=}\frac{C_{3}L}{2m\rho^{\gamma}}\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\frac{C_{4}L}{2m\rho^{2\gamma}}\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=0}^{\lceil\frac{k}{\gamma}\rceil\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s},\end{aligned}$
(50)

where $(t+1)\gamma-1=\lceil\frac{k}{\gamma}\rceil\gamma-1$ in $\overset{a}{=}$
comes from the variable substitution $k=t\gamma+r$ with $r=1,2,...,\gamma$.
Next, we compute the second part in $\overset{a}{=}$. It gives

$\displaystyle\begin{aligned}
&\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=0}^{\lceil\frac{k}{\gamma}\rceil\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\\\
&~{}~{}\leq\sum_{k=1}^{T\gamma-\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=0}^{k+\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}+\sum_{k=T\gamma-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=0}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\\\
&~{}~{}=\left(\sum_{k=1}^{T\gamma-\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}+\sum_{k=1}^{T\gamma-\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\sum_{s=\gamma}^{k+\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\right)+\sum_{s=0}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=T\gamma-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\\\
&~{}~{}=\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=1}^{T\gamma-\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\sum_{s=\gamma}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=s-\gamma+1}^{T\gamma-\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\left(\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=T\gamma-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\sum_{s=\gamma}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=T\gamma-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\right)\\\
&~{}~{}=\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\sum_{s=\gamma}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=s-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}.\end{aligned}$
(51)

Plugging (LABEL:cont36) into (LABEL:cont35), it follows from (36) and
$\Pi\mathbf{y}^{0}=0$ that

$\displaystyle\begin{aligned}
&\sum_{k=0}^{T\gamma}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{y}^{k}\|^{2}\\\
&~{}~{}\leq\frac{C_{3}L}{2m\rho^{\gamma}}\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\frac{C_{4}L}{2m\rho^{2\gamma}}\left(\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}+\sum_{s=\gamma}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\sum_{k=s-\gamma+1}^{T\gamma}\frac{\rho^{k}}{\theta_{k}^{2}}\right)\\\
&~{}~{}\leq\frac{C_{3}L}{2m\rho^{\gamma}}\frac{3\rho}{(1-\rho)^{3}}+\frac{C_{4}L}{2m\rho^{2\gamma}}\left(\frac{3\rho}{(1-\rho)^{3}}\sum_{s=0}^{\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}+\sum_{s=\gamma}^{T\gamma-1}\frac{\theta_{s}^{2}}{\rho^{s}}\Phi^{s}\frac{3\rho^{s-\gamma+1}}{(1-\rho)^{3}\theta_{s-\gamma}^{2}}\right)\\\
&~{}~{}\overset{b}{\leq}\frac{3C_{3}L}{2m\rho^{\gamma-1}(1-\rho)^{3}}+\frac{C_{4}L}{2m\rho^{2\gamma}}\left(\frac{3\rho}{(1-\rho)^{3}\rho^{\gamma-1}}\sum_{s=0}^{\gamma-1}\Phi^{s}+\frac{3\rho^{-\gamma+1}}{(1-\rho)^{3}}\sum_{s=\gamma}^{T\gamma-1}\Phi^{s}\right)\\\
&~{}~{}\leq\frac{3C_{3}L}{2m\rho^{\gamma-1}(1-\rho)^{3}}+\frac{3C_{4}L}{2m\rho^{3\gamma-1}(1-\rho)^{3}}\sum_{s=0}^{T\gamma-1}\Phi^{s}\\\
&~{}~{}\overset{c}{\leq}\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}+\frac{10\gamma^{2}}{mL(1+\frac{1}{\tau})(1-\sigma_{\gamma})^{2}}\sum_{s=0}^{T\gamma-1}\Phi^{s},\end{aligned}$

where $\overset{b}{\leq}$ uses $\theta_{s}\leq 1$ for $s\leq\gamma-1$ and
$\theta_{s}\leq\theta_{s-\gamma}$ for $s\geq\gamma$, $\overset{c}{\leq}$ uses
(49) and the definition of $C_{4}$ given in Lemma 8. Replacing
$\|\Pi\mathbf{y}^{k}\|$ by $\|\Pi\mathbf{x}^{k}\|$ in the above analysis, we
have the same bound for $\|\Pi\mathbf{x}^{k}\|^{2}$.

The next lemma is an analogy counterpart of Lemma 5 and the proof is similar
to that of the above Lemma 9.

###### Theorem 5

Suppose that Assumptions 1 and 3 hold with $\mu>0$. Let
$\alpha\leq\frac{(1-\sigma_{\gamma})^{3}}{3385L\gamma^{3}\sqrt{1+\frac{1}{\tau}}}$
and $\theta_{k}\equiv\theta=\frac{\sqrt{\mu\alpha}}{2}$. Then for algorithm
(12a)-(12d), we have

$\displaystyle\begin{aligned}
&\max\left\\{\sum_{k=0}^{T\gamma}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2},\sum_{k=0}^{T\gamma}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{x}^{k}\|^{2}\right\\}\\\
&~{}~{}\leq\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}+\frac{\theta^{2}}{7mL(1+\frac{1}{\tau})}\sum_{s=0}^{T\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s+1}},\end{aligned}$
(52)

where $\tau$ and $\Phi^{r}$ are defined in Lemma 3, and $C_{3}$ is defined in
Lemma 8.

###### Proof 11

From the definition of $\mathcal{M}_{\mathbf{y}}^{t\gamma,\gamma}$ and (46),
we have

$\displaystyle\begin{aligned}
&\sum_{k=1}^{T\gamma}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2}\\\
&~{}~{}=\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{L}{2m(1-\theta)^{t\gamma+r+1}}\|\Pi\mathbf{y}^{t\gamma+r}\|^{2}\leq\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{L}{2m(1-\theta)^{t\gamma+r+1}}\mathcal{M}_{\mathbf{y}}^{(t+1)\gamma,\gamma}\\\
&~{}~{}\leq\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{C_{3}L\rho^{t\gamma}}{2m(1-\theta)^{t\gamma+r+1}}+\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{C_{4}L}{2m(1-\theta)^{t\gamma+r+1}}\sum_{s=0}^{(t+1)\gamma-1}\rho^{(t-1)\gamma-s}\theta^{2}\Phi^{s}\\\
&~{}~{}\leq\frac{C_{3}L}{2m(1-\theta)}\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{\rho^{t\gamma+r}}{\rho^{\gamma}(1-\theta)^{t\gamma+r}}+\frac{C_{4}L\theta^{2}}{2m(1-\theta)}\sum_{t=0}^{T-1}\sum_{r=1}^{\gamma}\frac{\rho^{t\gamma+r}}{\rho^{2\gamma}(1-\theta)^{t\gamma+r}}\sum_{s=0}^{(t+1)\gamma-1}\frac{\Phi^{s}}{\rho^{s}}\\\
&~{}~{}=\frac{C_{3}L}{2m\rho^{\gamma}(1-\theta)}\sum_{k=1}^{T\gamma}\left(\frac{\rho}{1-\theta}\right)^{k}+\frac{C_{4}L\theta^{2}}{2m\rho^{2\gamma}(1-\theta)}\sum_{k=1}^{T\gamma}\left(\frac{\rho}{1-\theta}\right)^{k}\sum_{s=0}^{\lceil\frac{k}{\gamma}\rceil\gamma-1}\frac{\Phi^{s}}{\rho^{s}}.\end{aligned}$

Similar to (LABEL:cont36), we have

$\displaystyle\begin{aligned}
\sum_{k=1}^{T\gamma}\left(\frac{\rho}{1-\theta}\right)^{k}\sum_{s=0}^{\lceil\frac{k}{\gamma}\rceil\gamma-1}\frac{\Phi^{s}}{\rho^{s}}\leq\sum_{s=0}^{\gamma-1}\frac{\Phi^{s}}{\rho^{s}}\sum_{k=1}^{T\gamma}\left(\frac{\rho}{1-\theta}\right)^{k}+\sum_{s=\gamma}^{T\gamma-1}\frac{\Phi^{s}}{\rho^{s}}\sum_{k=s-\gamma+1}^{T\gamma}\left(\frac{\rho}{1-\theta}\right)^{k}.\end{aligned}$

From the settings of $\theta$ and $\alpha$, we know
$\theta\leq\frac{1-\sigma_{\gamma}}{116\gamma}$. From (49), we further have
$\frac{\rho}{1-\theta}<1$ and
$1-\rho-\theta\geq\frac{0.19(1-\sigma_{\gamma})}{\gamma}$. So we have
$\sum_{k=r+1}^{K}\left(\frac{\rho}{1-\theta}\right)^{k}\leq\left(\frac{\rho}{1-\theta}\right)^{r}\frac{\rho}{1-\theta-\rho}$.
It follows from $\|\Pi\mathbf{y}^{0}\|=0$ that

$\displaystyle\begin{aligned}
&\sum_{k=0}^{T\gamma}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{y}^{k}\|^{2}\\\
&~{}~{}\leq\frac{C_{3}L}{2m\rho^{\gamma-1}(1-\theta)(1-\theta-\rho)}+\frac{C_{4}L\theta^{2}}{2m\rho^{2\gamma-1}(1-\theta)(1-\theta-\rho)}\left(\sum_{s=0}^{\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s}}\left(\frac{1-\theta}{\rho}\right)^{s}+\left(\frac{\rho}{1-\theta}\right)^{-\gamma}\sum_{s=\gamma}^{T\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s}}\right)\\\
&~{}~{}\overset{a}{\leq}\frac{C_{3}L}{2m\rho^{\gamma-1}(1-\theta)(1-\theta-\rho)}+\frac{C_{4}L\theta^{2}(1-\theta)^{\gamma}}{2m\rho^{3\gamma-1}(1-\theta-\rho)}\sum_{s=0}^{T\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s+1}}\\\
&~{}~{}\overset{b}{\leq}\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}+\frac{\theta^{2}}{7mL(1+\frac{1}{\tau})}\sum_{s=0}^{T\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s+1}}.\end{aligned}$

where $\overset{a}{\leq}$ uses $\frac{1-\theta}{\rho}>1$ such that
$\left(\frac{1-\theta}{\rho}\right)^{s}\leq\left(\frac{1-\theta}{\rho}\right)^{\gamma}$
for all $s\leq\gamma-1$, $\overset{b}{\leq}$ uses (49),
$1-\rho-\theta\geq\frac{0.19(1-\sigma_{\gamma})}{\gamma}$, and the definition
of $C_{4}$ given in Lemma 8. Replacing $\|\Pi\mathbf{y}^{k}\|$ by
$\|\Pi\mathbf{x}^{k}\|$ in the above analysis, we have the same bound for
$\|\Pi\mathbf{x}^{k}\|^{2}$.

Now, we are ready to prove Theorems 3 and 4. We first prove Theorem 3.

###### Proof 12

Plugging (LABEL:cont30) into (LABEL:cont3) and using the definition of
$\Phi^{r}$ in (24), we have

$\displaystyle\begin{aligned}
&\frac{F(\overline{x}^{T\gamma+1})-F(x^{*})}{\theta_{T\gamma}^{2}}+\frac{1}{2\alpha}\|\overline{z}^{T\gamma+1}-x^{*}\|^{2}\\\
&~{}~{}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}-\sum_{k=0}^{T\gamma}\left(\left(\frac{1}{2\alpha}-\frac{L}{2}-\frac{20L\gamma^{2}}{(1-\sigma_{\gamma})^{2}}\right)\|\overline{z}^{t+1}-\overline{z}^{t}\|^{2}\right.\\\
&~{}~{}\hskip
179.25244pt\left.+\frac{1}{\theta_{k-1}^{2}}\left(1-\frac{20(1+\tau)\gamma^{2}}{(1+\frac{1}{\tau})(1-\sigma_{\gamma})^{2}}\right)D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)\\\
&~{}~{}\overset{a}{\leq}\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}-\sum_{k=0}^{T\gamma}\left(\frac{1}{4\alpha}\|\overline{z}^{t+1}-\overline{z}^{t}\|^{2}+\frac{1}{2\theta_{k-1}^{2}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})\right)\\\
&~{}~{}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}-\frac{1}{5mL}\sum_{r=0}^{T\gamma-1}\Phi^{r},\end{aligned}$

where in $\overset{a}{\leq}$ we let
$\tau=\frac{(1-\sigma_{\gamma})^{2}}{40\gamma^{2}}$ so to have
$\frac{20(1+\tau)\gamma^{2}}{(1+\frac{1}{\tau})(1-\sigma_{\gamma})^{2}}=\frac{1}{2}$,
$\alpha=\frac{(1-\sigma_{\gamma})^{4}}{21675L\gamma^{4}}\leq\frac{(1-\sigma_{\gamma})^{3}}{3385L\gamma^{3}\sqrt{1+\frac{1}{\tau}}}$,
and
$\frac{1}{4\alpha}\geq\frac{L}{2}+\frac{20L\gamma^{2}}{(1-\sigma_{\gamma})^{2}}$.
So we have

$\displaystyle\begin{aligned}
&F(\overline{x}^{T\gamma+1})-F(x^{*})\leq\theta_{T\gamma}^{2}\left(\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}\right),\\\
&\frac{1}{5mL}\sum_{r=0}^{T\gamma-1}\Phi^{r}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}.\end{aligned}$

It follows from (LABEL:cont30) that

$\displaystyle\begin{aligned}
\sum_{k=0}^{T\gamma}\frac{L}{2m\theta_{k}^{2}}\|\Pi\mathbf{x}^{k}\|^{2}\leq&\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}+\frac{10\gamma^{2}}{mL(1+\frac{1}{\tau})(1-\sigma_{\gamma})^{2}}\sum_{s=0}^{T\gamma-1}\Phi^{s}\\\
\leq&\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}+\frac{1}{4mL}\sum_{s=0}^{T\gamma-1}\Phi^{s}\\\
\leq&\frac{9}{4}\left(\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}\right).\end{aligned}$

From the definition of $C_{3}$ given in Lemma 8, we have

$\displaystyle\begin{aligned}
\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{235\gamma^{3}C_{3}L}{m(1-\sigma_{\gamma})^{3}}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{27mL\gamma}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\frac{103870L\gamma^{5}}{m(1-\sigma_{\gamma})^{5}}\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}+\frac{470L\gamma^{3}}{m(1-\sigma_{\gamma})^{3}}\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}\equiv
C_{5}.\end{aligned}$

The conclusion follows from Lemma 10.

The next lemma gives a sharper bound of the constant $C_{5}$ appeared in the
above proof.

###### Lemma 10

Under the settings of Theorem 3, we can further bound $C_{5}$ by

$\displaystyle
C_{5}\leq\frac{1}{2\alpha}\|\overline{z}^{0}-x^{*}\|^{2}+\frac{1-\sigma_{\gamma}}{20mL\gamma}\max_{r=0,...,\gamma}\|\Pi\mathbf{s}^{r}\|^{2}.$

###### Proof 13

From step (12c) with $\mu=0$, we have for any $k\leq\gamma-1$,

$\displaystyle\begin{aligned}
\theta_{k+1}\|\Pi\mathbf{z}^{k+1}\|\leq&\theta_{k}\|\Pi\mathbf{z}^{k+1}\|\leq\theta_{k}\|\Pi\mathbf{z}^{k}\|+\alpha\|\Pi\mathbf{s}^{k}\|\\\
\leq&\theta_{0}\|\Pi\mathbf{z}^{0}\|+\alpha\sum_{t=0}^{k}\|\Pi\mathbf{s}^{t}\|\leq\alpha\sum_{t=0}^{\gamma-1}\|\Pi\mathbf{s}^{t}\|\end{aligned}$

where we use $\Pi\mathbf{z}^{0}=0$. Squaring both sides gives

$\displaystyle\theta_{k+1}^{2}\|\Pi\mathbf{z}^{k+1}\|^{2}\leq\alpha^{2}\gamma\sum_{t=0}^{\gamma-1}\|\Pi\mathbf{s}^{t}\|^{2}\leq\alpha^{2}\gamma^{2}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\alpha^{2}\gamma\|\Pi\mathbf{s}^{0}\|^{2}.$

From the setting of $\alpha$ and the definition of
$\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}$, we have

$\displaystyle\frac{103870L\gamma^{5}}{m(1-\sigma_{\gamma})^{5}}\mathcal{M}_{\mathbf{z}}^{\gamma,\gamma}\leq\frac{1-\sigma_{\gamma}}{4523mL\gamma}(\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\|\Pi\mathbf{s}^{0}\|^{2}).$

On the other hand, it follows from step (12d) that

$\displaystyle\|\Pi\mathbf{x}^{k+1}\|\leq\theta_{k}\|\Pi\mathbf{z}^{k+1}\|+\|\Pi\mathbf{x}^{k}\|\leq\sum_{t=0}^{k}\theta_{t}\|\Pi\mathbf{z}^{t+1}\|\leq
1.62\sum_{t=0}^{\gamma-1}\theta_{t+1}\|\Pi\mathbf{z}^{t+1}\|.$

Squaring both sides gives

$\displaystyle\|\Pi\mathbf{x}^{k+1}\|^{2}\leq
2.63\gamma\sum_{t=0}^{\gamma-1}\theta_{t+1}^{2}\|\Pi\mathbf{z}^{t+1}\|^{2}\leq
2.63\gamma^{2}\left(\alpha^{2}\gamma^{2}\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\alpha^{2}\gamma\|\Pi\mathbf{s}^{0}\|^{2}\right).$

From the setting of $\alpha$ and the definition of
$\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}$, we have

$\displaystyle\frac{470L\gamma^{3}}{m(1-\sigma_{\gamma})^{3}}\mathcal{M}_{\mathbf{x}}^{\gamma,\gamma}\leq\frac{1-\sigma_{\gamma}}{380070mL\gamma}(\mathcal{M}_{\mathbf{s}}^{\gamma,\gamma}+\|\Pi\mathbf{s}^{0}\|^{2}).$

So we have the conclusion.

Next, we prove Theorem 4.

###### Proof 14

Plugging (LABEL:cont31) into (LABEL:cont4) and using the definition of
$\Phi^{r}$ in (24), we have

$\displaystyle\begin{aligned}
&\frac{1}{(1-\theta)^{T\gamma+1}}\left(F(\overline{x}^{T\gamma+1})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{T\gamma+1}-x^{*}\|^{2}\right)\\\
&~{}~{}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}\\\
&~{}~{}\quad-\sum_{k=0}^{T\gamma}\left(\frac{1}{(1-\theta)^{k}}\left(1-\frac{2(1+\tau)}{7(1+\frac{1}{\tau})}\right)D_{f}(\overline{x}^{k},\mathbf{y}^{k})+\frac{1}{(1-\theta)^{k+1}}\left(\frac{\theta^{2}}{2\alpha}-\frac{L\theta^{2}}{2}-\frac{2L\theta^{2}}{7}\right)\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}\right)\\\
&~{}~{}\overset{a}{\leq}F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}\\\
&~{}~{}\quad-\sum_{k=0}^{T\gamma}\left(\frac{1}{2(1-\theta)^{k}}D_{f}(\overline{x}^{k},\mathbf{y}^{k})+\frac{\theta^{2}}{4\alpha(1-\theta)^{k+1}}\|\overline{z}^{k+1}-\overline{z}^{k}\|^{2}\right)\\\
&~{}~{}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}-\frac{\theta^{2}}{11mL}\sum_{r=0}^{T\gamma-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}},\end{aligned}$

where in $\overset{a}{\leq}$ we let $\tau=\frac{7}{4}$ so to have
$\frac{2(1+\tau)}{7(1+\frac{1}{\tau})}=\frac{1}{2}$,
$\alpha=\frac{(1-\sigma_{\gamma})^{3}}{4244L\gamma^{3}}\leq\frac{(1-\sigma_{\gamma})^{3}}{3385L\gamma^{3}\sqrt{1+\frac{1}{\tau}}}$,
and $\frac{1}{4\alpha}\geq\frac{L}{2}+\frac{2L}{7}$. Thus, we have the first
conclusion and

$\displaystyle\frac{\theta^{2}}{11mL}\sum_{r=0}^{T\gamma-1}\frac{\Phi^{r}}{(1-\theta)^{r+1}}\leq
F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}.$

It follows from (LABEL:cont31) that

$\displaystyle\begin{aligned}
&\sum_{k=0}^{T\gamma}\frac{L}{2m(1-\theta)^{k+1}}\|\Pi\mathbf{x}^{k}\|^{2}\\\
&~{}~{}\leq\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}+\frac{\theta^{2}}{7mL(1+\frac{1}{\tau})}\sum_{s=0}^{T\gamma-1}\frac{\Phi^{s}}{(1-\theta)^{s+1}}\\\
&~{}~{}\leq
2\left(F(\overline{x}^{0})-F(x^{*})+\left(\frac{\theta^{2}}{2\alpha}+\frac{\mu\theta}{2}\right)\|\overline{z}^{0}-x^{*}\|^{2}+\frac{3.3C_{3}L\gamma}{m(1-\theta)(1-\sigma_{\gamma})}\right).\end{aligned}$

Thus, we have the second conclusion.

##  5 Conclusion

This paper studies the widely used accelerated gradient tracking in
decentralized optimization, which is originally proposed in (Qu & Li, 2020).
When the network is static, we prove sharper upper bounds for both nonstrongly
convex and strongly convex problems, which improve significantly on the
previous ones proved in (Qu & Li, 2020). When combing with Chebyshev
acceleration, Our complexities exactly match the lower bounds. When the
network is time-varying, we extend the accelerated gradient tracking with
almost no change, and prove the state-of-the-art complexities with the optimal
dependence on the precision $\epsilon$ and the condition number $L/\mu$, which
matches that of the classical centralized accelerated gradient descent.

##  Appendix A Proof of Lemma 1

###### Proof 15

From the $\mu$-strong convexity and $L$-smoothness of $f_{(i)}$, we have

$\displaystyle\begin{aligned} F(w)=&\frac{1}{m}\sum_{i=1}^{m}f_{(i)}(w)\\\
\geq&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{\mu}{2}\|w-y_{(i)}^{k}\|^{2}\right)\\\
=&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{\mu}{2}\|w-\overline{y}^{k}\|^{2}+\frac{\mu}{2}\|\overline{y}^{k}-y_{(i)}^{k}\|^{2}+\mu\left\langle
w-\overline{y}^{k},\overline{y}^{k}-y_{(i)}^{k}\right\rangle\right)\\\
\overset{a}{=}&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{\mu}{2}\|w-\overline{y}^{k}\|^{2}+\frac{\mu}{2}\|\overline{y}^{k}-y_{(i)}^{k}\|^{2}\right)\\\
\geq&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{\mu}{2}\|w-\overline{y}^{k}\|^{2}\right)\\\
\overset{b}{=}&f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},w-\overline{y}^{k}\right\rangle+\frac{\mu}{2}\|w-\overline{y}^{k}\|^{2},\end{aligned}$

and

$\displaystyle\begin{aligned}
F(w)\leq&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{L}{2}\|w-y_{(i)}^{k}\|^{2}\right)\\\
=&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{L}{2}\|w-\overline{y}^{k}\|^{2}+\frac{L}{2}\|\overline{y}^{k}-y_{(i)}^{k}\|^{2}+L\left\langle
w-\overline{y}^{k},\overline{y}^{k}-y_{(i)}^{k}\right\rangle\right)\\\
\overset{c}{=}&\frac{1}{m}\sum_{i=1}^{m}\left(f_{(i)}(y_{(i)}^{k})+\left\langle\nabla
f_{(i)}(y_{(i)}^{k}),w-y_{(i)}^{k}\right\rangle+\frac{L}{2}\|w-\overline{y}^{k}\|^{2}+\frac{L}{2}\|\overline{y}^{k}-y_{(i)}^{k}\|^{2}\right)\\\
\overset{d}{=}&f(\overline{y}^{k},\mathbf{y}^{k})+\left\langle\overline{s}^{k},w-\overline{y}^{k}\right\rangle+\frac{L}{2}\|w-\overline{y}^{k}\|^{2}+\frac{L}{2m}\|\Pi\mathbf{y}^{k}\|^{2},\end{aligned}$

where $\overset{a}{=}$ and $\overset{c}{=}$ use the definition of
$\overline{y}$ in (3), $\overset{b}{=}$ and $\overset{d}{=}$ use the
definition of $f(\overline{y}^{k},\mathbf{y}^{k})$ in (15), (14), and the
definition of $\Pi\mathbf{y}$ in (4).

## References

  * Alghunaim et al. (2020) Alghunaim, S. A., Ryu, E. K., Yuan, K., and H.Sayed, A.  Decentralized proximal gradient algorithms with linear covnergence rates.  _preprint arXiv:1909.06479_ , 2020.
  * Arioli & Scott (2014) Arioli, M. and Scott, J.  Chebyshev acceleration of iterative refinement.  _Numerical Algorithms_ , 66(3):591–608, 2014\.
  * Auzinger & Melenk (2017) Auzinger, W. and Melenk, J. M.  Iterative solution of large linear systems.  _Lecture notes, TU Wien_ , 2017.
  * Aybat et al. (2018) Aybat, N. S., Wang, Z., Lin, T., and Ma, S.  Distributed linearized alternating direction method of multipliers for composite convex consensus optimization.  _IEEE Transactions on Automatic Control_ , 63(1):5–20, 2018.
  * Bertsekas (1983) Bertsekas, D. P.  Distributed asynchromous computation of fixed points.  _Mathmatical Programming_ , 27:107–120, 1983.
  * Bonawitz et al. (2019) Bonawitz, K., Eichner, H., and et al.  Towards federated learning at scale: System design.  In _Conference on Machine Learning and Systems (MLSys)_ , 2019.
  * Devolder et al. (2014) Devolder, O., Glineur, F., and Nesterov, Y.  First-order methods of smooth convex optimization with inexact oracle.  _Mathematical Programming_ , 146:37–75, 2014.
  * Duchi et al. (2012) Duchi, J., Agarwal, A., and Wainwright, M.  Dual averaging for distributed optimization: Convergence analysis and network scaling.  _IEEE Transactions on Automatic Control_ , 57(3):592–606, 2012.
  * Dvinskikh & Gasnikov (2019) Dvinskikh, D. and Gasnikov, A.  Decentralized and parallelized primal and dual accelerated methods for stochastic convex programming problems.  _preprint arXiv:1904.09015_ , 2019.
  * Fallah et al. (2019) Fallah, A., Gurbuzbalaban, M., Ozdaglar, A., Simsekli, U., and Zhu, L.  Robust distributed accelerated stochastic gradient methods for multi-agent networks.  _preprint arXiv:1910.08701_ , 2019.
  * Hendrikx et al. (2020) Hendrikx, H., Bach, F., and Massoulié, L.  An optimal algorithm for decentralized finite sum optimization.  _preprint arXiv:2005.10675_ , 2020.
  * Hong et al. (2017) Hong, M., Hajinezhad, D., and Zhao, M.-M.  Prox-PDA: The proximal primal-dual algorithm for fast distributed nonconvex optimization and learning over networks.  In _International Conference on Machine Learning (ICML)_ , pp. 1529–1538, 2017.
  * Iutzeler et al. (2016) Iutzeler, F., Bianchi, P., Ciblat, P., and Hachem, W.  Explicit convergence rate of a distributed alternating direction method of multipliers.  _IEEE Transactions on Automatic Control_ , 61(4):892–904, 2016.
  * Jakovetić (2019) Jakovetić, D.  A unification and generatliztion of exact distributed first order methods.  _IEEE Transactions on Signal and Information Processing over Networks_ , 5(1):31–46, 2019.
  * Jakovetić et al. (2014) Jakovetić, D., Xavier, J., and Moura, J. M. F.  Fast distributed gradient methods.  _IEEE Transactions on Automatic Control_ , 59(5):1131–1146, 2014.
  * Kairouz et al. (2019) Kairouz, P., McMahan, H. B., and et al.  Advances and open problems in federated learning.  _preprint arXiv:1912.04977_ , 2019.
  * Koloskova et al. (2020) Koloskova, A., Loizou, N., Boreiri, S., Jaggi, M., and Stich, S. U.  A unified theory of decentralized SGD with changing topology and local updates.  In _International Conference on Machine Learning (ICML)_ , pp. 5381–5393, 2020.
  * Koralev et al. (2020) Koralev, D., Salim, A., and Richtárik, P.  Optimal and practical algorithms for smooth and strongly convex decentralized optimization.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020\.
  * Kovalev et al. (2021) Kovalev, D., Shulgin, E., Richtarik, P., Rogozin, A., and Gasnikov, A.  ADOM: accelerated decentralized optimization method for time-varying networks.  _preprint arXiv:2102.09234_ , 2021.
  * Lan et al. (2020) Lan, G., Lee, S., and Zhou, Y.  Communication-efficient algorithms for decentralized and stochastic optimization.  _Mathematical Programming_ , 180:237–284, 2020.
  * Li & Lin (2020a) Li, H. and Lin, Z.  On the complexity analysis of the primal solutions for the accelerated randomized dual coordinate ascent.  _Journal of Machine Learning Research_ , 21(33):1–45, 2020a.
  * Li & Lin (2020b) Li, H. and Lin, Z.  Revisiting EXTRA for smooth distributed optimization.  _SIAM Journal Optimization_ , 30(3):1795–1821, 2020b.
  * Li et al. (2020a) Li, H., Fang, C., Yin, W., and Lin, Z.  Decentralized accelerated gradient methods with increasing penalty parameters.  _IEEE transactions on Signal Processing_ , 68:4855–4870, 2020a.