# Variance Reduced EXTRA and DIGing and Their Optimal Acceleration for
Strongly Convex Decentralized Optimization

Huan Li  Zhouchen Lin  Yongchun Fang

###### Abstract

We study stochastic decentralized optimization for the problem of training
machine learning models with large-scale distributed data. We extend the
widely used EXTRA and DIGing methods with variance reduction (VR), and propose
two methods: VR-EXTRA and VR-DIGing. The proposed VR-EXTRA requires the time
of ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient
evaluations and ${\cal O}((\kappa_{b}+\kappa_{c})\log\frac{1}{\epsilon})$
communication rounds to reach precision $\epsilon$, which are the best
complexities among the non-accelerated gradient-type methods, where
$\kappa_{s}$ and $\kappa_{b}$ are the stochastic condition number and batch
condition number for strongly convex and smooth problems, respectively,
$\kappa_{c}$ is the condition number of the communication network, and $n$ is
the sample size on each distributed node. The proposed VR-DIGing has a little
higher communication cost of ${\cal
O}((\kappa_{b}+\kappa_{c}^{2})\log\frac{1}{\epsilon})$. Our stochastic
gradient computation complexities are the same as the ones of single-machine
VR methods, such as SAG, SAGA, and SVRG, and our communication complexities
keep the same as those of EXTRA and DIGing, respectively. To further speed up
the convergence, we also propose the accelerated VR-EXTRA and VR-DIGing with
both the optimal ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$
stochastic gradient computation complexity and ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication
complexity. Our stochastic gradient computation complexity is also the same as
the ones of single-machine accelerated VR methods, such as Katyusha, and our
communication complexity keeps the same as those of accelerated full batch
decentralized methods, such as MSDA. To the best of our knowledge, our
accelerated methods are the first to achieve both the optimal stochastic
gradient computation complexity and communication complexity in the class of
gradient-type methods.

##  1 Introduction

Emerging machine learning applications involve huge amounts of data samples,
and the data are often distributed across multiple machines for storage and
computational reasons. In this paper, we consider the following distributed
convex optimization problem with $m$ nodes, and each node has $n$ local
training samples:

$\displaystyle\min_{x\in\mathbb{R}^{p}}\sum_{i=1}^{m}f_{(i)}(x),\quad\mbox{where}\quad
f_{(i)}(x)=\frac{1}{n}\sum_{j=1}^{n}f_{(i),j}(x),$ (1)

where the local component function $f_{(i),j}$ represents the $j$th sample of
node $i$, and it is not accessible by any other node in the communication
network. The network is abstracted as a connected and undirected graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\\{1,2,...,m\\}$
is the set of nodes, and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is
the set of edges. Nodes $i$ and $j$ can send information to each other if and
only if $(i,j)\in\mathcal{E}$. The goal of the networked nodes is to
cooperatively solve problem (1) via local computation and communication, that
is, each node $i$ makes its decision only based on the local computations on
$f_{(i)}$, for example, the gradient, and the local information received from
its neighbors in the network.

When the local data size $n$ is large, the cost of computing the full batch
gradient $\nabla f_{(i)}$ at each iteration is expensive. To address the issue
of large-scale distributed data, stochastic decentralized algorithms are often
used to solve problem (1), where each node only randomly samples one component
gradient at each iteration (extendable to the mini-batch settings with more
than one randomly selected component). Most decentralized algorithms alternate
between computations and communications. Thus to compare the performance of
such methods, two measures are used: the number of communication rounds and
the number of stochastic gradient evaluations, where one communication round
allows each node to send information to their neighbors, for example, ${\cal
O}(1)$ vectors of size $p$, and one stochastic gradient evaluation refers to
computing the randomly sampled $\nabla f_{(i),j}$ for all $i\in\mathcal{V}$ in
parallel (Koralev et al., 2020).

Although stochastic decentralized optimization has been a hot topic in recent
years, and several algorithms have been proposed, to the best of our
knowledge, in the class of algorithms not relying on the expensive dual
gradient evaluations, there is no algorithm optimal in both the number of
communication rounds and the number of stochastic gradient evaluations
(Koralev et al., 2020), where “optimal” means matching the corresponding lower
bounds. In this paper, we extend two widely used decentralized algorithms of
EXTRA (Shi et al., 2015) and DIGing (Nedić et al., 2017; Qu & Li, 2018), which
have sparked a log of interest in the distributed optimization community, to
stochastic decentralized optimization by combing them with the powerful
variance reduction technique. Furthermore, we propose two accelerated
stochastic decentralized algorithms, which are optimal in the above two
measures of communications and stochastic gradient computations.

###  1.1 Notations and Assumptions

Denote $x_{(i)}\in\mathbb{R}^{p}$ to be the local variable for node $i$. To
simplify the algorithm description in a compact form, we introduce the
aggregate objective function $f(\mathbf{x})$ with its aggregate variable
$\mathbf{x}$ and aggregate gradient $\nabla f(\mathbf{x})$ as

$\displaystyle\qquad\begin{aligned}
\mathbf{x}=\left(\begin{array}[]{c}x_{(1)}^{T}\\\ \vdots\\\
x_{(m)}^{T}\end{array}\right),\quad
f(\mathbf{x})=\sum_{i=1}^{m}f_{(i)}(x_{(i)}),\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 $x^{*}$ to be the optimal solution of problem (1), and let
$\mathbf{x}^{*}=\mathbf{1}(x^{*})^{T}$, where $\mathbf{1}$ is the column
vector of $m$ ones. Denote $I$ as the identity matrix, and $\mathcal{N}_{(i)}$
as the neighborhood of node $i$. Denote
$\mbox{Ker}(U)=\\{x\in\mathbb{R}^{m}|Ux=0\\}$ as the kernel space of matrix
$U\in\mathbb{R}^{m\times m}$, and
$\mbox{Span}(U)=\\{y\in\mathbb{R}^{m}|y=Ux,\forall x\in\mathbb{R}^{m}\\}$ as
the linear span of all the columns of $U$. For matrices, we denote $\|\cdot\|$
as the Frobenius norm for simplicity without ambiguity, since it is the only
matrix norm we use in this paper. The notation $A\succeq B$ means $A-B$ is
positive semidefinite.

We make the following assumptions for the functions in (1).

###### Assumption 1

Each $f_{(i)}(x)$ is $L_{(i)}$-smooth and $\mu$-strongly convex. Each
$f_{(i),j}(x)$ is $L_{(i),j}$-smooth and convex.

We say a function $g(x)$ is $L$-smooth if its gradient satisfies $\|\nabla
g(\mathbf{y})-\nabla g(\mathbf{x})\|\leq L\|\mathbf{y}-\mathbf{x}\|$.
Motivated by (Hendrikx et al., 2020a, b), we define several notations as
follows:

$L_{f}=\max_{i}L_{(i)},\quad\overline{L}_{(i)}=\frac{1}{n}\sum_{j=1}^{n}L_{(i),j},\quad\overline{L}_{f}=\max_{i}\overline{L}_{(i)},\quad\kappa_{s}=\frac{\overline{L}_{f}}{\mu},\quad\kappa_{b}=\frac{L_{f}}{\mu}.$
(3)

Then $f(\mathbf{x})$ is also $\mu$-strongly convex and $L_{f}$-smooth. It
always holds that $L_{(i)}\leq\overline{L}_{(i)}\leq nL_{(i)}$111See footnote
14 in (Allen-Zhu, 2018) for the analysis., which further gives

$L_{f}\leq\overline{L}_{f}\leq
nL_{f}\quad\mbox{and}\quad\kappa_{b}\leq\kappa_{s}\leq n\kappa_{b}.$ (4)

We follow (Hendrikx et al., 2020a) to call $\kappa_{b}$ the batch condition
number, and $\kappa_{s}$ the stochastic condition number, which are classical
quantities in the analysis of batch optimization methods and finite-sum
optimization methods, respectively. Generally, we have $\kappa_{s}\ll
n\kappa_{b}$, see (Allen-Zhu, 2018) for the example and analysis.

In decentralized optimization, communication is often represented as a matrix
multiplication with a weight matrix $W\in\mathbb{R}^{m\times m}$. We make the
following assumptions for this weight matrix associated to the network.

###### Assumption 2

  1. 1.

$W_{i,j}\neq 0$ if and only if agents $i$ and $j$ are neighbors or $i=j$.
Otherwise, $W_{i,j}=0$.

  2. 2.

$W=W^{T}$, $I\succeq W\succeq\omega I$, and $W\mathbf{1}=\mathbf{1}$.

We let $\omega=0$ for EXTRA, and $\omega=\frac{\sqrt{2}}{2}$ for DIGing. We
can relax $\omega$ to be any small positive constant for DIGing, and fix it to
$\frac{\sqrt{2}}{2}$ to simplify the analysis. Part 2 of Assumption 2 implies
that the eigenvalues of $W$ lie in $[\omega,1]$, and its largest one
$\sigma_{1}(W)$ equals 1. Moreover, if the network is connected, we have
$\sigma_{2}(W)<1$, where $\sigma_{2}(W)$ means the second largest eigenvalue.
We often use

$\kappa_{c}=\frac{1}{1-\sigma_{2}(W)}$ (5)

as the condition number of the communication network, which upper bounds the
ratio between the largest eigenvalue and the smallest non-zero eigenvalue of
$(I-W)$, which is a gossip matrix (Scaman et al., 2017).

As will be introduced in the next section, we often use $\kappa_{b}$ and
$\kappa_{c}$ to describe the number of communication rounds, and $\kappa_{s}$
for the number of stochastic gradient evaluations in stochastic decentralized
optimization.

###  1.2 Literature Review

In this section, we give a brief review for the decentralized and stochastic
methods, as well as their combination. Table 1 sums up the complexities of the
representative ones.

####  1.2.1 Full Batch Decentralized Algorithms

Distributed optimization has gained significant attention for a long time
(Bertsekas, 1983; Tsitsiklis et al., 1986). The modern distributed gradient
descent (DGD) was proposed in (Nedić & Ozdaglar, 2009) for the general network
topology, and was further extended in (Nedić, 2011; Ram et al., 2010; Yuan et
al., 2016). These algorithms are usually slow due to the diminishing step-
size, and suffer from the sublinear convergence even for strongly convex and
smooth objectives. To avoid the diminishing step-size and speed up the
convergence, several methods with gradient tracking have been proposed.
Typical examples include EXTRA (Shi et al., 2015), DIGing (Nedić et al., 2017;
Qu & Li, 2018), NIDS (Li et al., 2019), and other similar algorithms (Xu et
al., 2015; Xin et al., 2018). Especially, EXTRA (Li & Lin, 2020) and NIDS (Li
et al., 2019) have the ${\cal
O}((\kappa_{b}+\kappa_{c})\log\frac{1}{\epsilon})$ complexity both in
communications and full batch gradient evaluations to solve problem (1) to
reach precision $\epsilon$, which is the best among the non-accelerated
algorithms. DIGing has a slight higher complexity of ${\cal
O}((\kappa_{b}+\kappa_{c}^{2})\log\frac{1}{\epsilon})$ (Alghunaim et al.,
2020). Another typical class of distributed algorithms is based on the
Lagrangian function, and they work with the Fenchel dual. Examples include the
dual ascent (Terelius et al., 2011; Scaman et al., 2017; Uribe et al., 2018),
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). However, the dual-based methods often need to
compute the gradient of the Fenchel conjugate of the local functions, called
dual gradient in the sequel, which is expensive.

Nesterov’s acceleration technique is an efficient approach to speed up the
convergence of first-order methods, and it has also been successfully applied
to decentralized optimization. Typical examples include the distributed
Nesterov gradient with consensus (Jakovetić et al., 2014), the distributed
Nesterov gradient descent (Qu & Li, 2020), the multi-step dual accelerated
method (MSDA) (Scaman et al., 2017, 2019), accelerated penalty method (Li et
al., 2020b), accelerated EXTRA (Li & Lin, 2020), and the accelerated proximal
alternating predictor-corrector method (APAPC) (Koralev et al., 2020). Some of
these methods have suboptimal computation complexity, and Chebyshev
acceleration (CA) (Arioli & Scott, 2014) is a powerful technique to further
reduce the computation cost. Scaman et al. (2017, 2019) proved the
$\varOmega(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ lower bound on
the number of communication rounds and the
$\varOmega(\sqrt{\kappa_{b}}\log\frac{1}{\epsilon})$ lower bound on the number
of full batch gradient evaluations, which means that any first-order full
batch decentralized methods cannot be faster than these bounds. The MSDA and
APAPC methods with CA achieve these lower bounds.

####  1.2.2 Stochastic Algorithms on a Single Machine

Stochastic gradient descent (SGD) has been the workhorse in machine learning.
However, since the variance of the noisy gradient will not go to zero, SGD
often suffers from the slow sublinear convergence. Variance reduction (VR) was
designed to reduce the negative effect of the noise, which can improve the
stochastic gradient computation complexity to ${\cal
O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$. On the other hand, full batch
methods, such as gradient descent, require ${\cal
O}(\kappa_{b}\log\frac{1}{\epsilon})$ iterations, and thus ${\cal
O}(n\kappa_{b}\log\frac{1}{\epsilon})$ individual gradient evaluations for
finite-sum problems with $n$ samples, which may be much larger than ${\cal
O}((n+\kappa_{s})\log\frac{1}{\epsilon})$ when $\kappa_{s}\ll n\kappa_{b}$.
Representative examples of VR methods include SAG (Schmidt et al., 2017), SAGA
(Defazio et al., 2014), and SVRG (Johnson & Zhang, 2013; Xiao & Zhang, 2014).
We can further accelerate the VR methods to the ${\cal
O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity by Nesterov’s acceleration technique. Examples include
Katyusha (Allen-Zhu, 2018) and its extensions in (Zhou et al., 2019; Kovalev
et al., 2020). Other accelerated stochastic algorithms can be found in (Lan &
Zhou, 2018; Lin et al., 2018; Fercoq & Richtárik, 2015; Lin et al., 2015). Lan
& Zhou (2018) proved the
$\varOmega((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ lower bound for
strongly convex and smooth stochastic optimization, and Katyusha achieves this
lower bound.

####  1.2.3 Stochastic Decentralized Algorithms

Table 1: Comparisons of various state-of-the-art decentralized and stochastic algorithms. See (3) and (5) for the definitions of $\kappa_{b}$, $\kappa_{s}$, and $\kappa_{c}$. $\widetilde{\cal O}$ hides the poly-logarithmic factors. The complexities of Acc-VR-EXTRA and Acc-VR-DIGing hold under some conditions to restrict the size of $\kappa_{c}$. See part 2 of Remark 3. Acc-VR-EXTRA-CA and Acc-VR-DIGing-CA remove these restrictions. Methods |  | stochastic gradient
---
computation complexity
| communication
---
complexity
| dual
---
gradient
based ?
Full batch decentralized algorithms
| EXTRA
---
(Shi et al., 2015)
(Li & Lin, 2020)
${\cal O}\left(n\left(\kappa_{b}+\kappa_{c}\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{b}+\kappa_{c}\right)\log\frac{1}{\epsilon}\right)$ | no
| DIGing
---
(Nedić et al., 2017)
(Alghunaim et al., 2020)
${\cal O}\left(n\left(\kappa_{b}+\kappa_{c}^{2}\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{b}+\kappa_{c}^{2}\right)\log\frac{1}{\epsilon}\right)$ | no
| MSDA+CA
---
(Scaman et al., 2017)
${\cal O}\left(n\sqrt{\kappa_{b}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | yes
| APAPC+CA
---
(Koralev et al., 2020)
${\cal O}\left(n\sqrt{\kappa_{b}}\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | no
Stochastic algorithms on a single machine
| VR methods
---
(Schmidt et al., 2017)
(Defazio et al., 2014)
(Johnson & Zhang, 2013)
${\cal O}\left(\left(\kappa_{s}+n\right)\log\frac{1}{\epsilon}\right)$ | $\backslash$ | no
| Katyusha
---
(Allen-Zhu, 2018)
${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | $\backslash$ | no
Stochastic decentralized algorithms
| GT-SAGA
---
(Xin et al., 2020)
${\cal O}\left(\left(\kappa_{s}^{2}\kappa_{c}^{2}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{s}^{2}\kappa_{c}^{2}+n\right)\log\frac{1}{\epsilon}\right)$ | no
| GT-SVRG
---
(Xin et al., 2020)
${\cal O}\left(\left(\kappa_{s}^{2}\kappa_{c}^{2}\log\kappa_{c}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{s}^{2}\kappa_{c}^{2}\log\kappa_{c}+n\right)\log\frac{1}{\epsilon}\right)$ | no
| ADFS
---
(Hendrikx et al., 2020a)
${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | yes
| DVR+CA
---
(Hendrikx et al., 2020b)
${\cal O}\left(\left(\kappa_{s}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\kappa_{b}\sqrt{\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | no
| DVR+Catalyst
---
(Hendrikx et al., 2020b)
$\widetilde{\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | $\widetilde{\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\sqrt{\frac{n\kappa_{b}}{\kappa_{s}}}\log\frac{1}{\epsilon}\right)$ | no
| Lower bounds
---
(Hendrikx et al., 2020a)
$\varOmega\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | $\varOmega\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | $\backslash$
Our results for stochastic decentralized optimization
VR-EXTRA | ${\cal O}\left(\left(\kappa_{s}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{b}+\kappa_{c}\right)\log\frac{1}{\epsilon}\right)$ | no
VR-DIGing | ${\cal O}\left(\left(\kappa_{s}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\left(\kappa_{b}+\kappa_{c}^{2}\right)\log\frac{1}{\epsilon}\right)$ | no
Acc-VR-EXTRA | ${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | no
Acc-VR-DIGing | ${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\kappa_{c}\sqrt{\kappa_{b}}\log\frac{1}{\epsilon}\right)$ | no
Acc-VR-EXTRA+CA | ${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | no
Acc-VR-DIGing+CA | ${\cal O}\left(\left(\sqrt{n\kappa_{s}}+n\right)\log\frac{1}{\epsilon}\right)$ | ${\cal O}\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ | no

To address the issue of large-scale distributed data, Chen & Sayed (2012) and
Ram et al. (2010) extended the DGD method to the distributed stochastic
gradient descent (DSGD). To further improve the convergence of stochastic
decentralized algorithms, Pu & Nedić (2020) combined DSGD with gradient
tracking, Mokhtari & Ribeiro (2016) combined EXTRA with SAGA, and proposed the
decentralized double stochastic averaging gradient algorithm, Xin et al.
(2019) combined gradient tracking with the VR technique, and two algorithms
are proposed, namely, GT-SATA and GT-SVRG. Li et al. (2020a) generalized the
approximate Newton-type method called DANE with gradient tracking and variance
reduction. See (Xin et al., 2020) for a detailed review for the non-
accelerated stochastic decentralized algorithms. Hendrikx et al. (2020a)
proposed an accelerated decentralized stochastic algorithm called ADFS, which
achieves the optimal ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication
complexity. However, ADFS is a dual-based method, and it needs to compute the
dual gradient at each iteration, which is expensive. Recently, Hendrikx et al.
(2020b) further proposed a dual-free decentralized method with variance
reduction, called DVR, which achieves the ${\cal
O}(\kappa_{b}\sqrt{\kappa_{c}}\log\frac{1}{\epsilon})$ communication
complexity and the ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic
gradient computation complexity. These complexities can be further improved to
$\widetilde{\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\sqrt{\frac{n\kappa_{b}}{\kappa_{s}}}\log\frac{1}{\epsilon})$
and $\widetilde{\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ by the
Catalyst acceleration (Lin et al., 2018), respectively, where $\widetilde{\cal
O}$ hides the poly-logarithmic factor, which is at least ${\cal
O}(\log\kappa_{b})$222See Proposition 17 in (Lin et al., 2018) and Corollary 7
in (Li & Lin, 2020).. We see that DVR-Catalyst achieves the optimal stochastic
gradient computation complexity up to log factor. However, its communication
cost is increased by a factor ${\cal
O}(\sqrt{\frac{n\kappa_{b}}{\kappa_{s}}})$ compared with ADFS, which is always
much larger than 1 in machine learning applications333As discussed in Section
1.2.2 for the comparison between the VR methods and gradient descent,
stochastic methods have no advantage when $\kappa_{s}\approx n\kappa_{b}$. We
often assume $\kappa_{s}\ll n\kappa_{b}$., and it is of the ${\cal
O}(\sqrt{n})$ order in the worst case. Hendrikx et al. (2020a) proved the
$\varOmega((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation and the
$\varOmega(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication
lower bounds.

###  1.3 Contributions

Although both the decentralized methods and stochastic methods have been well
studied, their combination still has much work to do. For example, as far as
we know, there is no gradient-type stochastic decentralized method achieving
both the state-of-the-art communication and stochastic gradient computation
complexities (either accelerated or non-accelerated) of the decentralized
methods and stochastic methods simultaneously. In this paper we aim to address
this issue. Our contributions include:

  1. 1.

We extend the widely used EXTRA and DIGing methods to deal with large-scale
distributed data by combining them with the powerful VR technique. We prove
the ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity and the ${\cal
O}((\kappa_{b}+\kappa_{c})\log\frac{1}{\epsilon})$ communication complexity
for VR-EXTRA, which are the best complexities among the non-accelerated
stochastic decentralized methods as far as we know. The stochastic gradient
computation complexity is the same as the single-machine VR methods, while the
communication complexity is the same as the full batch EXTRA. For VR-DIGing,
we establish the ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic
gradient computation complexity and the ${\cal
O}((\kappa_{b}+\kappa_{c}^{2})\log\frac{1}{\epsilon})$ communication
complexity. The latter one is a little worse than that of VR-EXTRA on the
dependence of $\kappa_{c}$. Due to the parallelism across $m$ nodes, running
VR-EXTRA and VR-DIGing with $mn$ samples is as fast as running the single-
machine VR methods with $n$ samples.

  2. 2.

To further speed up the convergence, we combine EXTRA and DIGing with the
accelerated VR technique. The proposed Acc-VR-EXTRA achieves the optimal
${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity and the optimal ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication
complexity under some mild conditions to restrict the size of $\kappa_{c}$.
The proposed Acc-VR-DIGing has the optimal ${\cal
O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity and the ${\cal
O}(\kappa_{c}\sqrt{\kappa_{b}}\log\frac{1}{\epsilon})$ communication
complexity with a little worse dependence on $\kappa_{c}$. The two methods are
implemented in a single loop, and thus they are practical. We further combine
Acc-VR-EXTRA and Acc-VR-DIGing with the Chebyshev acceleration to remove the
restrictions on the size of $\kappa_{c}$, and improve the communication
complexity of Acc-VR-DIGing to be optimal. Our complexities do not hide any
poly-logarithmic factor. To the best of our knowledge, our methods are the
first to exactly achieve both the optimal stochastic gradient computation
complexity and the communication complexity in the class of gradient-type
methods.

Table 1 summarizes the complexity comparisons to the state-of-the-art
stochastic decentralized methods. Our VR-EXTRA has the same stochastic
gradient computation complexity as DVR-CA, but our communication cost is lower
than theirs when $\kappa_{c}\leq{\cal O}(\kappa_{b}^{2})$. On the other hand,
by combining with Chebyshev acceleration, our VR-EXTRA and VR-DIGing can also
obtain the ${\cal O}(\kappa_{b}\sqrt{\kappa_{c}}\log\frac{1}{\epsilon})$
communication complexity. For the accelerated methods, our Acc-VR-EXTRA-CA and
Acc-VR-DIGing-CA outperform DVR-Catalyst on the stochastic gradient
computation complexity at least by the poly-logarithmic factor ${\cal
O}(\log\kappa_{b})$, and our communication cost is also lower than that of
DVR-Catalyst by the factor ${\cal
O}\left(\sqrt{\frac{n\kappa_{b}}{\kappa_{s}}}\right)$. On the other hand, DVR
and its Catalyst acceleration require ${\cal O}(np)$ memory at each node,
while our methods only need ${\cal O}(p)$ memory444This is similar to the
memory cost comparison between SAG/SAGA and SVRG.. Although ADFS has the same
complexities as our Acc-VR-EXTRA-CA and Acc-VR-DIGing-CA, our methods are
gradient-type methods, while theirs requires to compute the dual gradient at
each iteration, which is much more expensive.

##  2 Non-accelerated Variance Reduced EXTRA and DIGing

We first review the classical EXTRA and DIGing methods in Section 2.1. Then we
develop the variance reduced EXTRA and DIGing in Sections 2.2 and 2.3. At
last, we discuss the complexities of the proposed methods in Section 2.4.

###  2.1 Review of EXTRA and DIGing

A traditional way to analyze the decentralized optimization model is to write
problem (1) in the following equivalent manner:

$\displaystyle\min_{x_{(1)},\cdots,x_{(m)}}\sum_{i=1}^{m}f_{(i)}(x_{(i)}),\quad\mbox{s.t.}\quad
x_{(1)}=x_{(2)}=\cdots=x_{(m)}.$

Following (Alghunaim et al., 2020) and using the notations in (2), we further
reformulate the above problem as the following linearly constrained problem:

$\displaystyle\min_{\mathbf{x}}f(\mathbf{x})+\frac{1}{2\alpha}\|V\mathbf{x}\|^{2},\quad\mbox{s.t.}\quad
U\mathbf{x}=0,$ (6)

where the symmetric matrices $U\in\mathbb{R}^{m\times m}$ and
$V\in\mathbb{R}^{m\times m}$ satisfy

$U\mathbf{x}=0\Leftrightarrow x_{(1)}=\cdots=x_{(m)}\quad\mbox{and}\quad
V\mathbf{x}=0\Leftrightarrow x_{(1)}=\cdots=x_{(m)}.$ (7)

Introducing the following Lagrangian function

$L(\mathbf{x},\lambda)=f(\mathbf{x})+\frac{1}{2\alpha}\|V\mathbf{x}\|^{2}+\frac{1}{\alpha}\left\langle
U\mathbf{x},\mathbf{\lambda}\right\rangle,$

we can apply the basic gradient method with a step-size $\alpha$ in the
Gauss$-$Seidel-like order to compute the saddle point of problem (6), which
leads to the following iterations (Alghunaim et al., 2020; Nedić et al.,
2017):

$\displaystyle\begin{aligned}
&\mathbf{x}^{k+1}=\mathbf{x}^{k}-\left(\alpha\nabla
f(\mathbf{x}^{k})+U\mathbf{\lambda}^{k}+V^{2}\mathbf{x}^{k}\right),\\\
&\mathbf{\lambda}^{k+1}=\mathbf{\lambda}^{k}+U\mathbf{x}^{k+1}.\end{aligned}$
(8)

Iteration (LABEL:alm) is a unified algorithmic framework, and different
choices of $U$ and $V$ give different methods (Alghunaim et al., 2020).
Specifically, when we choose $U=\sqrt{\frac{I-W}{2}}$ and
$V=\sqrt{\frac{I-W}{2}}$, (LABEL:alm) reduces to the famous EXTRA algorithm
(Shi et al., 2015), which consists of the following iterations:

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=(I+W)\mathbf{x}^{k}-\frac{I+W}{2}\mathbf{x}^{k-1}-\alpha\left(\nabla
f(\mathbf{x}^{k})-\nabla f(\mathbf{x}^{k-1})\right).\end{aligned}$

When we choose $U=I-W$ and $V=\sqrt{I-W^{2}}$, (LABEL:alm) reduces to the
DIGing (Nedić et al., 2017) method with the following iterations:

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

Both EXTRA and DIGing belong to the class of gradient tracking methods, since
they all track the difference of gradients at each iteration.

###  2.2 Development of VR-EXTRA and VR-DIGing

Now, we come to extend EXTRA and DIGing with the variance reduction technique
proposed in SVRG (Johnson & Zhang, 2013). Specifically, SVRG maintains a
snapshot vector $w_{(i)}^{k}$ after several SGD iterations, and keeps an
iterative estimator $\widetilde{\nabla}f_{(i)}(x_{(i)}^{k})=\nabla
f_{(i),j}(x_{(i)}^{k})-\nabla f_{(i),j}(w_{(i)}^{k})+\nabla
f_{(i)}(w_{(i)}^{k})$ of the full batch gradient for some randomly selected
$j$. When extending EXTRA and DIGing to stochastic decentralized optimization,
a straightforward idea is to replace the local gradient $\nabla
f_{(i)}(x_{(i)}^{k})$ in (LABEL:alm) by its VR estimator
$\widetilde{\nabla}f_{(i)}(x_{(i)}^{k})$. However, in this way the resultant
algorithm needs the same number of stochastic gradient evaluations and
communication rounds to precision $\epsilon$. As summarized in Table 1, our
goal is to provide computation and communication complexities matching those
of SVRG and EXTRA/DIGing, respectively, which are not equal. To address this
issue, we use the mini-batch VR technique, that is, select $b$ independent
samples with replacement as a mini-batch $\mathbb{S}_{(i)}$, and use this
mini-batch to update the VR estimator. By carefully choosing the mini-batch
size $b$, we can balance the communication and stochastic gradient computation
costs. Moreover, to simplify the algorithm development and analysis, we adopt
the loopless SVRG proposed in (Kovalev et al., 2020). Combing the above ideas,
we have the following VR variant of (LABEL:alm) described in a distributed
way:

$\displaystyle\nabla_{(i)}^{k}=\frac{1}{b}\sum_{j\in\mathbb{S}_{(i)}^{k}}\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(x_{(i)}^{k})-\nabla f_{(i),j}(w_{(i)}^{k})\right)+\nabla
f_{(i)}(w_{(i)}^{k}),\quad\forall i,$ (9a) $\displaystyle
x_{(i)}^{k+1}=x_{(i)}^{k}-\left(\alpha\nabla_{(i)}^{k}+\sum_{j\in\mathcal{N}_{(i)}}U_{ij}\mathbf{\lambda}_{(j)}^{k}+\sum_{j\in\mathcal{N}_{(i)}}(V^{2})_{ij}x_{(j)}^{k}\right),\quad\forall
i,$ (9b)
$\displaystyle\mathbf{\lambda}_{(i)}^{k+1}=\mathbf{\lambda}_{(i)}^{k}+\sum_{j\in\mathcal{N}_{(i)}}U_{ij}x_{(j)}^{k+1},\quad\forall
i,$ (9c) $\displaystyle
w_{(i)}^{k+1}=\left\\{\begin{array}[]{l}x_{(i)}^{k+1}\mbox{ with probability
}\frac{b}{n},\\\ w_{(i)}^{k}\mbox{ with probability
}1-\frac{b}{n},\end{array}\right.\forall i,$ (9f)

where the mini-batch VR estimator update rule (9a) is motivated by (Allen-Zhu,
2018), in which each sample $j$ on node $i$ is selected with probability
$p_{(i),j}=\frac{L_{(i),j}}{\sum_{j=1}^{n}L_{(i),j}}$. The probabilistic
update of the snapshot vector in (9f) is motivated by (Kovalev et al., 2020),
in which we update the full batch gradient $\nabla f_{(i)}(w_{(i)}^{k+1})$ if
$w_{(i)}^{k+1}=x_{(i)}^{k+1}$; otherwise, we use the old one. Steps (9b) and
(9c) come from (LABEL:alm), but replacing the local gradients by their VR
estimators. In steps (9a) and (9f), each node selects $\mathbb{S}_{(i)}^{k}$
and computes $w_{(i)}^{k+1}$ independent of the other nodes.

At last, we write (9a)-(9f) in the EXTRA/DIGing style. Similar to (2), we
denote

$\displaystyle\begin{aligned}
\quad\nabla^{k}=\left(\begin{array}[]{c}(\nabla_{(1)}^{k})^{T}\\\ \vdots\\\
(\nabla_{(m)}^{k})^{T}\end{array}\right)\end{aligned}$ (10)

to simplify the algorithm description. From steps (9b) and (9c), we have

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=(2I-U^{2}-V^{2})\mathbf{x}^{k}-(I-V^{2})\mathbf{x}^{k-1}-\alpha\left(\nabla^{k}-\nabla^{k-1}\right)\end{aligned}$
(11)

in the compact form. Plugging $U=\sqrt{\frac{I-W}{2}}$ and
$V=\sqrt{\frac{I-W}{2}}$ into (11), we have

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=(I+W)\mathbf{x}^{k}-\frac{I+W}{2}\mathbf{x}^{k-1}-\alpha\left(\nabla^{k}-\nabla^{k-1}\right),\end{aligned}$

which is the VR variant of EXTRA, called VR-EXTRA. Plugging $U=I-W$ and
$V=\sqrt{I-W^{2}}$ into (11), we have

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=2W\mathbf{x}^{k}-W^{2}\mathbf{x}^{k-1}-\alpha\left(\nabla^{k}-\nabla^{k-1}\right),\end{aligned}$

which is further equivalent to the following method, called VR-DIGing,

$\displaystyle\begin{aligned}
&\mathbf{s}^{k+1}=W\mathbf{s}^{k}+\nabla^{k}-\nabla^{k-1},\\\
&\mathbf{x}^{k+1}=W\mathbf{x}^{k}-\alpha\mathbf{s}^{k+1}.\end{aligned}$

We see that VR-EXTRA and VR-DIGing are quite similar to the original EXTRA and
DIGing. The only difference is that we replace the local gradients by their VR
estimators. Thus the implementation is as simple as that of the original EXTRA
and DIGing. We give the specific descriptions of VR-EXTRA and VR-DIGing in
Algorithm 1 in a distributed way, including the parameter settings. To discuss
EXTRA and DIGing in a unified framework, we denote

$\displaystyle\kappa=2\kappa_{c}\mbox{ for
EXTRA}\qquad\mbox{and}\qquad\kappa=\kappa_{c}^{2}\mbox{ for DIGing.}$ (12)

See Lemma 1 for the reason. We will use $\kappa$ frequently in this paper when
we do not distinguish EXTRA and DIGing, and the readers can use (12) to get
the specific properties of EXTRA and DIGing, respectively.

Algorithm 1 VR-EXTRA and VR-DIGing

Initialize: $x_{(i)}^{0}=w_{(i)}^{0}$, $\mathbf{\lambda}_{(i)}^{0}=0$, compute
$x_{(i)}^{1}$ and $w_{(i)}^{1}$ for all $i$ by (9b) and (9f), respectively.
Let $\alpha={\cal O}(\frac{1}{\max\\{L_{f},\kappa\mu\\}})$ and
$b=\frac{\max\\{\overline{L}_{f},n\mu\\}}{\max\\{L_{f},\kappa\mu\\}}$, where
$\kappa=2\kappa_{c}$ for EXTRA, and $\kappa=\kappa_{c}^{2}$ for DIGing. Let
$s_{(i)}^{1}=\nabla f_{(i)}(w_{(i)}^{0})$ for DIGing.

Let distribution $\mathcal{D}_{(i)}$ be to output $j\in[1,n]$ with probability
$p_{(i),j}=\frac{L_{(i),j}}{n\overline{L}_{(i)}}$.

for $k=1,2,...$ do

Step 1: $\mathbb{S}_{(i)}^{k}\leftarrow b$ independent samples from
$\mathcal{D}_{(i)}$ with replacement, $\forall i$,

Step 2: Compute $\nabla_{(i)}^{k}$ by (9a), $\forall i$,

Step 3: For EXTRA, compute $x_{(i)}^{k+1}$ by
$x_{(i)}^{k+1}=\left(x_{(i)}^{k}+\sum_{j\in\mathcal{N}_{(i)}}W_{ij}x_{(j)}^{k}\right)-\frac{1}{2}\left(x_{(i)}^{k-1}+\sum_{j\in\mathcal{N}_{(i)}}W_{ij}x_{(j)}^{k-1}\right)-\alpha\left(\nabla_{(i)}^{k}-\nabla_{(i)}^{k-1}\right),\forall
i,$ For DIGing, compute $x_{(i)}^{k+1}$ by
$s_{(i)}^{k+1}=\sum_{j\in\mathcal{N}_{(i)}}W_{ij}s_{(j)}^{k}+\nabla_{(i)}^{k}-\nabla_{(i)}^{k-1},\qquad
x_{(i)}^{k+1}=\sum_{j\in\mathcal{N}_{(i)}}W_{ij}x_{(j)}^{k}-\alpha
s_{(i)}^{k+1},\quad\forall i,$

Step 4: Compute $w_{(i)}^{k+1}$ by (9f), $\forall i$.

end for

###  2.3 Extension to Large $\kappa$

The particular choice of the mini-batch size $b$ in Algorithm 1 may be smaller
than 1 when $\kappa$ is large, which makes the algorithm meaningless. We
discuss EXTRA and DIGing in a unified way in this section, so we use $\kappa$
in this section, which is defined in (12). In fact, $b\geq 1$ if and only if
$\kappa\leq\max\\{\kappa_{s},n\\}$, see the proof of Lemma 6 in Section 4. In
this section we consider the case of $\kappa>\max\\{\kappa_{s},n\\}$.

Intuitively speaking, when $\kappa$ is very large such that
$\kappa_{b}+\kappa\geq\kappa_{s}+n$, to reach the desired ${\cal
O}((\kappa_{b}+\kappa)\log\frac{1}{\epsilon})$ communication complexity and
the ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity, as summarized in Table 1, we should perform less than
1 stochastic gradient evaluation in average at each iteration. This
observation motivates us to introduce some zero samples, that is to say, let
$f_{(i),n+1}=\cdots=f_{(i),n^{\prime}}=0$ for all $i$, and consider problem

$\displaystyle\min_{x\in\mathbb{R}^{p}}\sum_{i=1}^{m}f_{(i)}^{\prime}(x),\quad\mbox{where}\quad
f_{(i)}^{\prime}(x)=\frac{1}{n^{\prime}}\sum_{j=1}^{n^{\prime}}f_{(i),j}(x).$
(13)

The zero samples do not spend time to compute the stochastic gradient. We see
that problems (13) and (1) are equivalent. To use Algorithm 1 to solve problem
(13), we denote

$L_{(i),j}=\frac{n\mu n^{\prime}-n\overline{L}_{(i)}}{n^{\prime}-n},\quad
n<j\leq n^{\prime},$

and let each sample be selected with probability
$\frac{L_{(i),j}}{\sum_{j=1}^{n^{\prime}}L_{(i),j}}$. Then we select the
samples in $[1,n]$ with probability $\frac{\overline{L}_{(i)}}{\mu
n^{\prime}}$, and select the zero samples with probability
$1-\frac{\overline{L}_{(i)}}{\mu n^{\prime}}$. It can be seen that
$f_{(i)}^{\prime}(x)$ is $\frac{nL_{(i)}}{n^{\prime}}$-smooth and
$\frac{n\mu}{n^{\prime}}$-strongly convex. Define the following notations:

$n^{\prime}=\kappa,\quad\mu^{\prime}=\frac{n\mu}{n^{\prime}},\quad
L_{f}^{\prime}=\max_{i}\frac{nL_{(i)}}{n^{\prime}}=\frac{nL_{f}}{n^{\prime}},\quad\overline{L}_{(i)}^{\prime}=\frac{\sum_{j=1}^{n^{\prime}}L_{(i),j}}{n^{\prime}},\quad\overline{L}_{f}^{\prime}=\max_{i}\overline{L}_{(i)}^{\prime}.$
(14)

We can easily check
$\overline{L}_{f}^{\prime}=\overline{L}_{(i)}^{\prime}=n\mu$, $\alpha={\cal
O}(\frac{1}{\max\\{L_{f}^{\prime},\kappa\mu^{\prime}\\}})={\cal
O}(\frac{1}{n\mu})$, and
$b=\frac{\max\\{\overline{L}_{f}^{\prime},n^{\prime}\mu^{\prime}\\}}{\max\\{L_{f}^{\prime},\kappa\mu^{\prime}\\}}=1$
since $\kappa\geq\kappa_{s}\geq\frac{L_{f}}{\mu}$. Then we can use Algorithm 1
to solve problem (13).

###  2.4 Complexities

We prove the convergence of VR-EXTRA and VR-DIGing in a unified framework.
From Assumption 2, we have the following easy-to-identify lemma, where the
third inequality in (15) can be proved similar to Lemma 4 in (Li et al.,
2020b).

###### Lemma 1

Suppose that Assumption 2 holds with $\omega=0$ for EXTRA. Let
$U=V=\sqrt{\frac{I-W}{2}}$. Then we have

$\displaystyle\quad\qquad\|U\mathbf{x}\|^{2}\leq\|V\mathbf{x}\|^{2},\quad\|V\mathbf{x}\|^{2}\leq\frac{1}{2}\|\mathbf{x}\|^{2},\quad\mbox{and}\quad\|U\mathbf{\lambda}\|^{2}\geq\frac{1}{\kappa}\|\mathbf{\lambda}\|^{2},\forall\mathbf{\lambda}\in\mbox{Span}(U),$
(15)

where $\kappa=\frac{2}{1-\sigma_{2}(W)}=2\kappa_{c}$. Suppose that Assumption
2 holds with $\omega=\frac{\sqrt{2}}{2}$ for DIGing. Let $U=I-W$ and
$V=\sqrt{I-W^{2}}$. Then (15) also holds with
$\kappa=\frac{1}{(1-\sigma_{2}(W))^{2}}=\kappa_{c}^{2}$.

Denote the following set of random variables:

$\mathbb{S}^{k}=\cup_{i=1}^{m}\mathbb{S}_{(i)}^{k},\qquad\xi^{k}=\\{\mathbb{S}^{0},\mathbf{w}^{1},\mathbb{S}^{1},\mathbf{w}^{2}\cdots,\mathbb{S}^{k-1},\mathbf{w}^{k}\\}.$

The next theorem gives the communication complexity and stochastic gradient
computation complexity of algorithm (9a)-(9f) in a unified way.

###### Theorem 1

Suppose that Assumption 1 holds, and $U$ and $V$ satisfy (7) and (15). Assume
$\kappa\leq\max\\{\kappa_{s},n\\}$. Let
$\alpha=\frac{1}{28\max\\{L_{f},\kappa\mu\\}}$ and
$b=\frac{\max\\{\overline{L}_{f},n\mu\\}}{\max\\{L_{f},\kappa\mu\\}}$. Then
algorithm (9a)-(9f) requires the time of ${\cal
O}((\kappa_{b}+\kappa)\log\frac{1}{\epsilon})$ communication rounds and ${\cal
O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient evaluations to
find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Remark 1

Let’s explain the time of communication rounds and stochastic gradient
evaluations. At each iteration, algorithm (9a)-(9f) performs one round of
communication, that is, each node $i$ receives information $x_{(j)}^{k}$ and
$\mathbf{\lambda}_{(j)}^{k}$ from its neighbors for all
$j\in\mathcal{N}_{(i)}$. Then each node $i$ selects $\mathbb{S}_{(i)}^{k}$
randomly and computes $\nabla_{(i)}^{k}$ with $b$ stochastic gradient
evaluations. $\nabla f_{(i)}(w_{(i)}^{k+1})$ is updated with probability
$b/n$, and each time with $n$ stochastic gradient evaluations. So each node
computes $b$ stochastic gradients in average at each iteration. Since the
computation is performed in parallel across all the nodes, we say that each
iteration requires the time of one communication round and $b$ stochastic
gradient evaluations in average.

Theorem 1 holds under assumption $\kappa\leq\max\\{\kappa_{s},n\\}$. Although
algorithm (9a)-(9f) also converges when $\kappa\geq\max\\{\kappa_{s},n\\}$
with $b=1$, the computation cost increases to ${\cal
O}((\kappa_{b}+\kappa)\log\frac{1}{\epsilon})$. See part 2 of Lemma 6. We can
use the zero-sample strategy described in Section 2.3 to reduce the
computation cost to ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$, as
described in the following theorem.

###### Theorem 2

Suppose that Assumption 1 and conditions (7) and (15) hold. Assume
$\kappa>\max\\{\kappa_{s},n\\}$. Applying Algorithm 1 to solve problem (13),
it requires the time of ${\cal O}((\kappa_{b}+\kappa)\log\frac{1}{\epsilon})$
communication rounds and ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$
stochastic gradient evaluations to find an $\epsilon$-precision solution of
problem (1) such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

We see that by introducing the zero samples with carefully designed
$n^{\prime}$ and $L_{(i),j}$ for $n<j\leq n^{\prime}$, the complexities in
Theorem 2 keep the same as those in Theorem 1.

For the particular VR-EXTRA and VR-DIGing methods, we have the following
complexities accordingly, where we replace $\kappa$ in Theorems 1 and 2 by
$2\kappa_{c}$ and $\kappa_{c}^{2}$, respectively.

###### Corollary 1

Suppose that Assumptions 1 and 2 hold with $\omega=0$. Use the zero-sample
strategy if $2\kappa_{c}\geq\max\\{\kappa_{s},n\\}$. Then the VR-EXTRA method
in Algorithm 1 requires the time of ${\cal
O}((\kappa_{b}+\kappa_{c})\log\frac{1}{\epsilon})$ communication rounds and
${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient
evaluations to find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Corollary 2

Suppose that Assumptions 1 and 2 hold with $\omega=\frac{\sqrt{2}}{2}$. Use
the zero-sample strategy if $\kappa_{c}^{2}\geq\max\\{\kappa_{s},n\\}$. Then
the VR-DIGing method in Algorithm 1 requires the time of ${\cal
O}((\kappa_{b}+\kappa_{c}^{2})\log\frac{1}{\epsilon})$ communication rounds
and ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient
evaluations to find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Remark 2

  1. 1.

The communication complexity of VR-DIGing has a worse dependence on
$\kappa_{c}$ than that of VR-EXTRA. This is because EXTRA uses
$U=\sqrt{\frac{I-W}{2}}$ in problem (6), while DIGing uses $U=I-W$. From Lemma
1, we see that different choice of $U$ gives different order of $\kappa_{c}$.

  2. 2.

From Table 1, we see that EXTRA and VR-EXTRA have the same communication
complexity, and DIGing and VR-DIGing also have the same communication
complexity. Thus extending EXTRA and DIGing to stochastic decentralized
optimization does not need to pay a price of more communication cost
theoretically.

  3. 3.

Running VR-EXTRA and VR-DIGing with $mn$ samples needs the time of ${\cal
O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$ stochastic gradient evaluations,
which is the same as that of running the single-machine VR methods with $n$
samples when we ignore the communication time. On the other hand, when we run
the single-machine VR methods with $mn$ samples, the required time increases
to ${\cal O}((\kappa_{s}+mn)\log\frac{1}{\epsilon})$. Thus the linear speedup
is achieved by parallelism when $n$ is larger than $\kappa_{s}$.

  4. 4.

Both in theory and in practice, we can choose a larger mini-batch size $b$
than the particular choice given in Algorithm 1, at the expense of higher
stochastic gradient computation complexity than ${\cal
O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$. However, the communication
complexity remains unchanged. See the proof of Lemma 6. Denote $\tau$ to be
the ratio between the practical running time of performing one communication
round and one stochastic gradient computation. If
$\kappa_{s}+n\leq\tau(\kappa_{b}+\kappa)$, that is, communications dominate
the total running time, we can increase the mini-batch size to
$\frac{\max\\{\overline{L}_{f},n\mu\\}}{\max\\{L_{f},\kappa\mu\\}}\frac{\tau(\kappa_{b}+\kappa)}{\kappa_{s}+n}$,
which does not increase the total running time of ${\cal
O}(\tau(\kappa_{b}+\kappa)\log\frac{1}{\epsilon})$.

Algorithm 2 Acc-VR-EXTRA and Acc-VR-DIGing

Initialize: $x^{0}_{(i)}=z^{0}_{(i)}=w^{0}_{(i)}$,
$\mathbf{\lambda}^{0}_{(i)}=0$ for all $i$, $\alpha={\cal
O}(\frac{1}{L_{f}})$, $b=\sqrt{\frac{n\max\\{\overline{L}_{f},n\mu\\}}{\kappa
L_{f}}}$, $\theta_{1}=\frac{1}{2}\sqrt{\frac{\kappa\mu}{L_{f}}}$,
$\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}$, where $\kappa=2\kappa_{c}$ for
EXTRA, and $\kappa=\kappa_{c}^{2}$ for DIGing.

Let $U=V=\sqrt{\frac{I-W}{2}}$ for EXTRA, and $U=I-W$ and $V=\sqrt{I-W^{2}}$
for DIGing.

Let distribution $\mathcal{D}_{(i)}$ be to output $j\in[1,n]$ with probability
$p_{(i),j}=\frac{L_{(i),j}}{n\overline{L}_{(i)}}$.

for $k=0,1,2,...$ do

$\mathbb{S}_{(i)}^{k}\leftarrow b$ independent samples from
$\mathcal{D}_{(i)}$ with replacement, $\forall i$,

Perform steps (16a)-(16h), $\forall i$,

end for

##  3 Accelerated Variance Reduced EXTRA and DIGing

In this section, we develop the accelerated VR-EXTRA and VR-DIGing methods. In
algorithm (9a)-(9f), we combine (LABEL:alm) with the loopless SVRG to get the
non-accelerated methods. To develop the accelerated methods, a straightforward
idea is to combine (LABEL:alm) with the loopless Katyusha proposed in (Kovalev
et al., 2020), which leads to the following algorithm (16a)-(16h). We give the
parameter settings in Algorithm 2. We will not write (16a)-(16h) in the
EXTRA/DIGing style since the resultant methods are complex, and they are not
very similar to the original EXTRA and DIGing besides the feature of gradient
tracking.

$\displaystyle
y_{(i)}^{k}=\theta_{1}z_{(i)}^{k}+\theta_{2}w_{(i)}^{k}+(1-\theta_{1}-\theta_{2})x_{(i)}^{k},\quad\forall
i,$ (16a)
$\displaystyle\nabla_{(i)}^{k}=\frac{1}{b}\sum_{j\in\mathbb{S}_{(i)}^{k}}\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(y_{(i)}^{k})-\nabla f_{(i),j}(w_{(i)}^{k})\right)+\nabla
f_{(i)}(w_{(i)}^{k}),\quad\forall i,$ (16b) $\displaystyle
z_{(i)}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{1}}}\left(\frac{\mu\alpha}{\theta_{1}}y_{(i)}^{k}+z_{(i)}^{k}-\frac{1}{\theta_{1}}\left(\alpha\nabla_{(i)}^{k}+\sum_{j\in\mathcal{N}_{(i)}}U_{ij}\mathbf{\lambda}_{(j)}^{k}+\theta_{1}\sum_{j\in\mathcal{N}_{(i)}}(V^{2})_{ij}z_{(j)}^{k}\right)\right),\forall
i,$ (16c)
$\displaystyle\mathbf{\lambda}_{(i)}^{k+1}=\mathbf{\lambda}_{(i)}^{k}+\theta_{1}\sum_{j\in\mathcal{N}_{(i)}}U_{ij}z_{(j)}^{k+1},\quad\forall
i,$ (16d) $\displaystyle
x_{(i)}^{k+1}=y_{(i)}^{k}+\theta_{1}\left(z_{(i)}^{k+1}-z_{(i)}^{k}\right),\quad\forall
i,$ (16e) $\displaystyle
w_{(i)}^{k+1}=\left\\{\begin{array}[]{l}x_{(i)}^{k+1}\mbox{ with probability
}\frac{b}{n},\\\ w_{(i)}^{k}\mbox{ with probability
}1-\frac{b}{n},\end{array}\right.\forall i.$ (16h)

In the above algorithm, steps (16a) and (16e) are the Nesterov’s acceleration
steps, which are motivated by (Allen-Zhu, 2018; Kovalev et al., 2020). Steps
(16c) and (16d) involve the operation of $U\mathbf{x}$, which is uncomputable
for $U=\sqrt{\frac{I-W}{2}}$ in EXTRA in the distributed environment.
Introducing the auxiliary variable
$\widetilde{\mathbf{\lambda}}^{k}=U\mathbf{\lambda}^{k}$ and multiplying both
sides of (16d) by $U$ leads to

$\displaystyle\begin{aligned}
&\mathbf{z}^{k+1}=\frac{1}{1+\frac{\mu\alpha}{\theta_{1}}}\left(\frac{\mu\alpha}{\theta_{1}}\mathbf{y}^{k}+\mathbf{z}^{k}-\frac{1}{\theta_{1}}\left(\alpha\nabla^{k}+\widetilde{\mathbf{\lambda}}^{k}+\theta_{1}V^{2}\mathbf{z}^{k}\right)\right),\\\
&\widetilde{\mathbf{\lambda}}^{k+1}=\widetilde{\mathbf{\lambda}}^{k}+\theta_{1}U^{2}\mathbf{z}^{k+1},\end{aligned}$
(17)

in the compact form. From the definitions of $U=V=\sqrt{\frac{I-W}{2}}$, we
only need to compute $W\mathbf{z}$, which corresponds to the gossip-style
communications. For DIGing, we do not need such auxiliary variables.

###  3.1 Complexities

Theorem 3 gives the complexities of algorithm (16a)-(16h) in a unified way,
and Corollaries 3 and 4 provide the complexities for the particular Acc-VR-
EXTRA and Acc-VR-DIGing methods, respectively.

###### Theorem 3

Suppose that Assumption 1 holds, and $U$ and $V$ satisfy (7) and (15). Assume
$\kappa\leq\kappa_{b}$ and
$\kappa\leq\max\\{\frac{n\kappa_{b}}{\kappa_{s}},\frac{n^{2}\kappa_{b}}{\kappa_{s}^{2}}\\}$.
Let $\theta_{1}=\frac{1}{2}\sqrt{\frac{\kappa\mu}{L_{f}}}$,
$\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}$,
$b=\sqrt{\frac{n\max\\{\overline{L}_{f},n\mu\\}}{\kappa L_{f}}}$, and
$\alpha=\frac{1}{10L_{f}}$. Then algorithm (16a)-(16h) requires the time of
${\cal O}(\sqrt{\kappa_{b}\kappa}\log\frac{1}{\epsilon})$ communication rounds
and ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Remark 3

  1. 1.

If
$\kappa>\max\\{\frac{n\kappa_{b}}{\kappa_{s}},\frac{n^{2}\kappa_{b}}{\kappa_{s}^{2}}\\}$,
we can take the mini-batch size $b=\frac{\overline{L}_{f}}{L_{f}}$. Then
algorithm (16a)-(16h) also converges with the communication complexity
unchanged, but the stochastic gradient computation complexity increases to
${\cal O}\Big{(}\sqrt{\frac{\kappa\overline{L}_{f}^{2}}{\mu
L_{f}}}\log\frac{1}{\epsilon}\Big{)}$. See part 2 of Lemma 9. When
$\kappa\gg\kappa_{b}$, it is unclear currently whether acceleration can be
achieved without Chebyshev acceleration, which will be introduced in the next
section.

  2. 2.

As introduced in Section 1.1, we have $\kappa_{b}\leq\kappa_{s}\leq
n\kappa_{b}$, and we always assume $\kappa_{s}\ll n\kappa_{b}$ in the analysis
of stochastic algorithms. Thus we can expect
$\max\\{\frac{n\kappa_{b}}{\kappa_{s}},\frac{n^{2}\kappa_{b}}{\kappa_{s}^{2}}\\}$
to be large for large-scale data. On the other hand, $\kappa_{c}$ depends on
the network scale and connectivity. For example, $\kappa_{c}={\cal O}(1)$ for
the commonly used Erdős$-$Rényi random graph, and $\kappa_{c}={\cal O}(m\log
m)$ for the geometric graph. In the worst case, for example, the linear graph
or cycle graph, we have $\kappa_{c}={\cal O}(m^{2})$ (Nedić et al., 2018).
Thus we can also expect $\kappa$ to be not very large when the number of
distributed nodes is limited and the network is well connected. So we can
expect that the assumption
$\kappa\leq\max\\{\frac{n\kappa_{b}}{\kappa_{s}},\frac{n^{2}\kappa_{b}}{\kappa_{s}^{2}}\\}$
always holds for large-scale distributed data, for example, thousands of nodes
and each node with millions of data.

###### Corollary 3

Suppose that Assumptions 1 and 2 hold with $\omega=0$. Under the assumptions
on $\kappa$ and the parameter settings in Theorem 3 with $\kappa=2\kappa_{c}$,
the Acc-VR-EXTRA algorithm requires the time of ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication rounds
and ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Corollary 4

Suppose that Assumptions 1 and 2 hold with $\omega=\frac{\sqrt{2}}{2}$. Under
the assumptions on $\kappa$ and the parameter settings in Theorem 3 with
$\kappa=\kappa_{c}^{2}$, the Acc-VR-DIGing algorithm requires the time of
${\cal O}(\kappa_{c}\sqrt{\kappa_{b}}\log\frac{1}{\epsilon})$ communication
rounds and ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Remark 4

  1. 1.

From Table 1, we see that the communication complexity and stochastic gradient
computation complexity of Acc-VR-EXTRA are both optimal under some conditions
to restrict the size of $\kappa_{c}$. Similarly, the stochastic gradient
computation complexity of Acc-VR-DIGing is also optimal. However, its
communication complexity is worse than the corresponding lower bound by the
${\cal O}(\sqrt{\kappa_{c}})$ factor.

  2. 2.

Running Acc-VR-EXTRA and Acc-VR-DIGing with $mn$ samples needs the time of
${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
evaluations, which is the same as that of running the single-machine Katyusha
with $n$ samples when we ignore the communication time. On the other hand,
when we run the single-machine Katyusha with $mn$ samples, the required time
increases to ${\cal O}((\sqrt{mn\kappa_{s}}+mn)\log\frac{1}{\epsilon})$. Since
acceleration takes effect only when $\kappa_{s}\gg mn$, the parallelism speeds
up Katyusha by the $\sqrt{m}$ factor. On the other hand, when $\kappa_{s}\leq
n$, the linear speedup is achieved.

  3. 3.

Similar to VR-EXTRA and VR-DIGing, both in theory and in practice, we can
choose a larger mini-batch size $b$ than the particular choice given in
Algorithm 2, at the expense of higher stochastic gradient computation
complexity than ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$.
However, the ${\cal O}(\sqrt{\kappa_{b}\kappa}\log\frac{1}{\epsilon})$
communication complexity remains unchanged. See the proof of Lemma 9. Recall
the definition of $\tau$ in Remark 2(4). If
$\sqrt{n\kappa_{s}}+n\leq\tau\sqrt{\kappa_{b}\kappa}$, that is, communications
dominate the total running time, we can increase the mini-batch size to
$\sqrt{\frac{n\max\\{\overline{L}_{f},n\mu\\}}{\kappa
L_{f}}}\frac{\tau\sqrt{\kappa_{b}\kappa}}{\sqrt{n\kappa_{s}}+n}$, which does
not increase the total running time of ${\cal
O}(\tau\sqrt{\kappa_{b}\kappa}\log\frac{1}{\epsilon})$.

At last, we compare VR-EXTRA and VR-DIGing with Acc-VR-EXTRA and Acc-VR-
DIGing. Both the accelerated methods and non-accelerated methods have their
own advantages.

  1. 1.

The accelerated methods need less stochastic gradient computation evaluations
than the non-accelerated methods when $\kappa_{s}>n$. In this case,
acceleration takes effect. Otherwise, the accelerated methods have no
advantage over non-accelerated methods on the computation cost. Moreover, the
non-accelerated methods have the superiority of simple implementation.

  2. 2.

The accelerated methods always need less communication rounds than their non-
accelerated counterparts. However, when dealing with large-scale distributed
data in machine learning, we may expect that computation often dominates the
total running time. Otherwise, the full batch accelerated decentralized
methods such as APAPC (Koralev et al., 2020) may be a better choice.

###  3.2 Chebyshev Acceleration

In this section we remove the restrictions on the size of $\kappa_{c}$ in
Corollaries 3 and 4, which come from matrix $U$, as shown in (15). To make
$\kappa$ small, our goal is to construct a new matrix $\hat{U}$ by $U$ such
that $\mbox{Ker}(\hat{U})=\mbox{Span}(\mathbf{1})$ and
$\|\hat{U}\mathbf{\lambda}\|^{2}\geq\frac{1}{c}\|\mathbf{\lambda}\|^{2}$ for
all $\mathbf{\lambda}\in\mbox{Span}(\hat{U})$, where $c$ is a much smaller
constant than $\kappa$. Moreover, the construction procedure should not take
more than ${\cal O}(\sqrt{\kappa_{c}})$ time. Then we only need to replace $U$
and $V$ by $\hat{U}$ and some matrix $\hat{V}$ in algorithm (16a)-(16h), where
$\hat{U}$ and $\hat{V}$ should satisfy the relations in (15). We follow
(Scaman et al., 2017) to use Chebyshev acceleration to construct $\hat{U}$,
which is a common acceleration scheme to minimize $c$.

####  3.2.1 Review of Chebyshev Acceleration

We first give a brief description of Chebyshev acceleration, which was first
used to accelerate distributed optimization in (Scaman et al., 2017). We first
introduce the Chebyshev polynomials defined 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$. Given a positive
semidefinite symmetric matrix $L\in\mathbb{R}^{m\times m}$ such that
$\mbox{Ker}(L)=\mbox{Span}(\mathbf{1})$, denote
$\lambda_{1}(L)\geq\lambda_{2}(L)\geq\cdots\geq\lambda_{n-1}(L)>\lambda_{n}(L)=0$
as the eigenvalues of $L$. Following the notations in (Scaman et al., 2017),
we define $\gamma(L)=\frac{\lambda_{n-1}(L)}{\lambda_{1}(L)}$,
$c_{1}=\frac{1-\sqrt{\gamma(L)}}{1+\sqrt{\gamma(L)}}$,
$c_{2}=\frac{1+\gamma(L)}{1-\gamma(L)}$, and
$c_{3}=\frac{2}{\lambda_{1}(L)+\lambda_{n-1}(L)}$. Then $c_{3}L$ has the
spectrum in $[1-c_{2}^{-1},1+c_{2}^{-1}]$. For any polynomial $p_{t}(x)$ of
degree at most $t$, Theorem 6.1 in (Auzinger & Melenk, 2017) tells us that the
solution of the following problem

$\min_{p_{t}:p_{t}(0)=0}\max_{x\in[1-c_{2}^{-1},1+c_{2}^{-1}]}|p_{t}(x)-1|$

is

$P_{t}(x)=1-\frac{T_{t}(c_{2}(1-x))}{T_{t}(c_{2})}.$

Moreover, from Corollary 6.1 in (Auzinger & Melenk, 2017), we have

$\min_{p_{t}:p_{t}(0)=0}\max_{x\in[1-c_{2}^{-1},1+c_{2}^{-1}]}|p_{t}(x)-1|=\frac{2c_{1}^{t}}{1+c_{1}^{2t}},$

which means that the spectrum of $P_{t}(c_{3}L)$ lies in
$\left[1-\frac{2c_{1}^{t}}{1+c_{1}^{2t}},1+\frac{2c_{1}^{t}}{1+c_{1}^{2t}}\right]$.
For the particular choice of $t=\frac{3}{\sqrt{\gamma(L)}}$, it can be checked
that
$c_{1}^{t}\leq\Big{(}\left(1-\sqrt{\gamma(L)}\right)^{1/\sqrt{\gamma(L)}}\Big{)}^{3}\leq
e^{-3}$, which further leads to
$\frac{2c_{1}^{t}}{1+c_{1}^{2t}}\leq\frac{2}{e^{3}+e^{-3}}\leq 0.1$. Thus the
spectrum of $P_{t}(c_{3}L)$ is a subinterval of $[0.9,1.1]$. On the other
hand, it can be checked that $P_{t}(c_{3}L)$ is a gossip matrix satisfying
$\mbox{Ker}(P_{t}(c_{3}L))=\mbox{Span}(\mathbf{1})$ (Scaman et al., 2017). In
practice, we can compute the operation $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: $P_{t}(c_{3}L)\mathbf{x}=\mathbf{x}-\frac{\mathbf{z}^{t}}{a^{t}}$.

####  3.2.2 Remove the Restrictions on the Size of $\kappa_{c}$

For the particular choice of $U=V=\sqrt{\frac{I-W}{2}}$, define
$\hat{U}=\hat{V}=\sqrt{\frac{1}{2.2}P_{t}(c_{3}U^{2})}$, where
$c_{3}=\frac{2}{\lambda_{1}(U^{2})+\lambda_{n-1}(U^{2})}$. Then we have
$\|\hat{V}\mathbf{x}\|^{2}\leq\frac{1}{2}\|\mathbf{x}\|^{2}$ and
$\|\hat{U}\mathbf{\lambda}\|^{2}\geq\frac{0.9}{2.2}\|\mathbf{\lambda}\|^{2}\geq\frac{1}{3}\|\mathbf{\lambda}\|^{2}$
for all $\mathbf{\lambda}\in\mbox{Span}(\hat{U})$ with
$t=\frac{3}{\sqrt{\gamma(U^{2})}}=\frac{3}{\sqrt{1-\sigma_{2}(W)}}={\cal
O}(\sqrt{\kappa_{c}})$. So $\hat{U}$ and $\hat{V}$ satisfy the relations in
(15), and replacing $U$ and $V$ by $\hat{U}$ and $V$ does not destroy the
proof of Theorem 3. In the algorithm implementation, we only need to replace
the operations $U^{2}\mathbf{z}$ and $V^{2}\mathbf{z}$ in (LABEL:acc-extra2)
by $\frac{1}{2.2}P_{t}(c_{3}U^{2})\mathbf{z}$. Moreover, replacing $\kappa$ by
the constant $3$ in Theorem 3, we can expect that the assumptions on $\kappa$
always hold. Since we need ${\cal O}(\sqrt{\kappa_{c}})$ time to construct
$\hat{U}$ at each iteration, so the communication complexity remains
$\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$.

###### Corollary 5

Suppose that Assumptions 1 and 2 hold with $\omega=0$. Under the parameter
settings in Theorem 3 with $\kappa=3$, Acc-VR-EXTRA with Chebyshev
acceleration (CA) requires the time of
$\left(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon}\right)$ communication
rounds and ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

For the particular choice of $U=I-W$ and $V=\sqrt{I-W^{2}}$, define
$\hat{U}=\frac{2-\sqrt{2}}{2.2}P_{t}(c_{3}U)$, $\hat{W}=I-\hat{U}$, and
$\hat{V}=\sqrt{I-\hat{W}^{2}}$, where
$c_{3}=\frac{2}{\lambda_{1}(U)+\lambda_{n-1}(U)}$. Then we have
$\|\hat{V}\mathbf{x}\|^{2}\leq\frac{1}{2}\|\mathbf{x}\|^{2}$ and
$\|\hat{U}\mathbf{\lambda}\|^{2}\geq\frac{1}{20}\|\mathbf{\lambda}\|^{2}$ for
all $\mathbf{\lambda}\in\mbox{Span}(\hat{U})$ with
$t=\frac{3}{\sqrt{\gamma(U)}}={\cal O}(\sqrt{\kappa_{c}})$. Similar to the
above analysis for the Acc-VR-EXTRA-CA method, we have the following
complexity corollary. Note that since we replace $\kappa$ by the constant $20$
in Theorem 3, and use the fact that the construction of $\hat{U}$ needs ${\cal
O}(\sqrt{\kappa_{c}})$ time at each iteration, we can reduce the communication
cost from ${\cal O}(\kappa_{c}\sqrt{\kappa_{b}}\log\frac{1}{\epsilon})$ to
${\cal O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$.

###### Corollary 6

Suppose that Assumptions 1 and 2 hold with $\omega=\frac{\sqrt{2}}{2}$. Under
the parameter settings of Theorem 3 with $\kappa=20$, Acc-VR-DIGing-CA
requires the time of ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication rounds
and ${\cal O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}[\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}]\leq\epsilon$.

###### Remark 5

  1. 1.

From Corollaries 5 and 6, we see that the restrictions on $\kappa_{c}$ in
Corollaries 3 and 4 have been removed, and the communication complexity of
Acc-VR-DIGing has been improved to be optimal by Chebyshev acceleration.

  2. 2.

We can also combine Chebyshev acceleration with the non-accelerated VR-EXTRA
and VR-DIGing, and give the ${\cal
O}\left(\left(\kappa_{s}+n\right)\log\frac{1}{\epsilon}\right)$ stochastic
gradient computation complexity and the ${\cal
O}\left(\left(\kappa_{b}\sqrt{\kappa_{c}}\right)\log\frac{1}{\epsilon}\right)$
communication complexity, which are the same as those of DVR (Hendrikx et al.,
2020b).

##  4 Proof of Theorems

We prove Theorems 1 and 3 in this section. We first introduce some useful
properties. For $L$-smooth and convex function $f(\mathbf{x})$, we have
(Nesterov, 2004)

$\displaystyle\begin{aligned} f(\mathbf{y})-f(\mathbf{x})-\left\langle\nabla
f(\mathbf{x}),\mathbf{y}-\mathbf{x}\right\rangle\geq\frac{1}{2L}\|\nabla
f(\mathbf{y})-\nabla f(\mathbf{x})\|^{2}.\end{aligned}$ (18)

Recall that $x^{*}$ is the optimal solution of problem (1), then
$\mathbf{x}^{*}$ is also the optimal solution of the following linearly
constrained convex problem

$\displaystyle\min_{\mathbf{x}}f(\mathbf{x}),\quad\mbox{s.t.}\quad
U\mathbf{x}=0,$ (19)

where $U$ satisfies (7). Furthermore, there exists
$\mathbf{\lambda}^{*}\in\mbox{Span}(U)$ such that

$\displaystyle\begin{aligned} \nabla
f(\mathbf{x}^{*})+\frac{1}{\alpha}U\mathbf{\lambda}^{*}=0.\end{aligned}$ (20)

The existence of $\mathbf{\lambda}^{*}$ is proved in (Shi et al., 2015, Lemma
3.1). $U\mathbf{x}^{*}=0$ and (20) are the Karush-Kuhn-Tucker (KKT) optimality
conditions of problem (19).

###  4.1 Non-accelerated VR-EXTRA and VR-DIGing

We first give a classical property of the VR technique (Johnson & Zhang, 2013;
Xiao & Zhang, 2014).

###### Lemma 2

Suppose that Assumption 1 holds. Then for algorithm (9a)-(9f), we have

$\displaystyle\begin{aligned}
\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla^{k}-\nabla
f(\mathbf{x}^{k})\|^{2}\big{]}\leq\frac{4\overline{L}_{f}}{b}\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\frac{4\overline{L}_{f}}{b}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right).\end{aligned}$
(21)

###### Proof 1

From Lemma D.2 in (Allen-Zhu, 2018), we have

$\displaystyle\mathbb{E}_{\mathbb{S}_{(i)}^{k}}\big{[}\|\nabla_{(i)}^{k}-\nabla
f_{(i)}(x_{(i)}^{k})\|^{2}\big{]}\leq\frac{1}{b}\mathbb{E}_{j\sim\mathcal{D}_{(i)}}\left[\left\|\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(x_{(i)}^{k})-\nabla
f_{(i),j}(w_{(i)}^{k})\right)\right\|^{2}\right],$

where $\mathcal{D}_{(i)}$ is defined in Algorithm 1. Using identity
$\|a+b\|^{2}\leq 2\|b\|^{2}+2\|b\|^{2}$ and (18), from Lemma D.2 in (Allen-
Zhu, 2018), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}_{(i)}^{k}}\big{[}\|\nabla_{(i)}^{k}-\nabla
f_{(i)}(x_{(i)}^{k})\|^{2}\big{]}\\\
~{}~{}&\leq\frac{2}{b}\mathbb{E}_{j\sim\mathcal{D}_{(i)}}\left[\left\|\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(x_{(i)}^{k})-\nabla
f_{(i),j}(x^{*})\right)\right\|^{2}\right]+\frac{2}{b}\mathbb{E}_{j\sim\mathcal{D}_{(i)}}\left[\left\|\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(w_{(i)}^{k})-\nabla f_{(i),j}(x^{*})\right)\right\|^{2}\right]\\\
~{}~{}&\leq\frac{4\overline{L}_{(i)}}{b}\left(f_{(i)}(x_{(i)}^{k})-f_{(i)}(x^{*})-\left\langle\nabla
f_{(i)}(x^{*}),x_{(i)}^{k}-x^{*}\right\rangle\right)+\frac{4\overline{L}_{(i)}}{b}\left(f_{(i)}(w_{(i)}^{k})-f_{(i)}(x^{*})-\left\langle\nabla
f_{(i)}(x^{*}),w_{(i)}^{k}-x^{*}\right\rangle\right).\end{aligned}$

From the convexity of $f_{(i)}(x)$, the definitions in (2), (3), and (10), and
the fact that $\mathbb{S}^{k}_{(i)}$ and $\mathbb{S}^{k}_{(j)}$ are selected
independently for all $i$ and $j$, we have

$\displaystyle\begin{aligned}
\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla^{k}-\nabla
f(\mathbf{x}^{k})\|^{2}\big{]}\leq&\frac{4\overline{L}_{f}}{b}\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})-\left\langle\nabla
f(\mathbf{x}^{*}),\mathbf{x}^{k}-\mathbf{x}^{*}\right\rangle\right)+\frac{4\overline{L}_{f}}{b}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})-\left\langle\nabla
f(\mathbf{x}^{*}),\mathbf{w}^{k}-\mathbf{x}^{*}\right\rangle\right).\end{aligned}$

From the optimality condition in (20) and $U\mathbf{x}^{*}=0$, we have the
conclusion.

The following property is also useful in the analysis of mini-batch VR
methods.

###### Lemma 3

For algorithm (9a)-(9f), we have

$\displaystyle\begin{aligned}
\mathbb{E}_{\mathbb{S}^{k}}\big{[}\nabla^{k}\big{]}=\nabla
f(\mathbf{x}^{k}).\end{aligned}$ (22)

###### Proof 2

From the definition of $\nabla_{(i)}^{k}$ in (9a), and the fact that the
elements in $\mathbb{S}_{(i)}^{k}$ are selected independently with
replacement, we have

$\displaystyle\begin{aligned}
\mathbb{E}_{\mathbb{S}_{(i)}^{k}}\big{[}\nabla_{(i)}^{k}\big{]}=&\mathbb{E}_{j\sim\mathcal{D}_{(i)}}\left[\frac{1}{np_{(i),j}}\left(\nabla
f_{(i),j}(x_{(i)}^{k})-\nabla f_{(i),j}(w_{(i)}^{k})\right)+\nabla
f_{(i)}(w_{(i)}^{k})\right]=\nabla f_{(i)}(x_{(i)}^{k}).\end{aligned}$

Using the definitions in (2) and (10), we have the conclusion.

The next lemma describes a progress in one iteration of (9a)-(9f).

###### Lemma 4

Suppose that Assumption 1 and conditions (7) and (15) hold. Then for algorithm
(9a)-(9f), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq\left(\frac{1}{2\alpha}-\frac{\mu}{2}\right)\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right)\\\
~{}~{}&\quad+\frac{1}{2\tau}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla
f(\mathbf{x}^{k})-\nabla^{k}\|^{2}\big{]}-\frac{1}{2\alpha}\|V\mathbf{x}^{k}\|^{2}-\left(\frac{1}{4\alpha}-\frac{\tau+L_{m}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\big{]},\end{aligned}$
(23)

for some $\tau>0$ and $L_{m}=\max\\{L_{f},\kappa\mu\\}$.

###### Proof 3

From the $L_{f}$-smoothness of $f(\mathbf{x})$ and the definition of $L_{m}$,
we have

$\displaystyle\begin{aligned} f(\mathbf{x}^{k+1})&\leq
f(\mathbf{x}^{k})+\left\langle\nabla
f(\mathbf{x}^{k}),\mathbf{x}^{k+1}-\mathbf{x}^{k}\right\rangle+\frac{L_{m}}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\\\
&=f(\mathbf{x}^{k})+\left\langle\nabla
f(\mathbf{x}^{k})-\nabla^{k},\mathbf{x}^{k+1}-\mathbf{x}^{k}\right\rangle+\left\langle\nabla^{k},\mathbf{x}^{k+1}-\mathbf{x}^{k}\right\rangle+\frac{L_{m}}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\\\
&\overset{a}{\leq}f(\mathbf{x}^{k})+\frac{1}{2\tau}\|\nabla
f(\mathbf{x}^{k})-\nabla^{k}\|^{2}+\frac{\tau+L_{m}}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}+\left\langle\nabla^{k},\mathbf{x}^{k+1}-\mathbf{x}^{*}\right\rangle+\left\langle\nabla^{k},\mathbf{x}^{*}-\mathbf{x}^{k}\right\rangle,\end{aligned}$
(24)

where we use Young’s inequality in $\overset{a}{\leq}$. Since

$\displaystyle\nabla^{k}=\frac{1}{\alpha}(\mathbf{x}^{k}-\mathbf{x}^{k+1})-\frac{1}{\alpha}U\mathbf{\lambda}^{k}-\frac{1}{\alpha}V^{2}\mathbf{x}^{k},$
(25)
$\displaystyle\mathbf{\lambda}^{k+1}=\mathbf{\lambda}^{k}+U\mathbf{x}^{k+1},$
(26)

from (9b) and (9c), we have

$\displaystyle\begin{aligned}
&\left\langle\nabla^{k},\mathbf{x}^{k+1}-\mathbf{x}^{*}\right\rangle\\\
~{}~{}&\overset{b}{=}\frac{1}{\alpha}\left\langle\mathbf{x}^{k}-\mathbf{x}^{k+1},\mathbf{x}^{k+1}-\mathbf{x}^{*}\right\rangle-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{k},U\mathbf{x}^{k+1}\right\rangle-\frac{1}{\alpha}\left\langle
V\mathbf{x}^{k},V\mathbf{x}^{k+1}\right\rangle\\\
~{}~{}&\overset{c}{=}\frac{1}{\alpha}\left\langle\mathbf{x}^{k}-\mathbf{x}^{k+1},\mathbf{x}^{k+1}-\mathbf{x}^{*}\right\rangle-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\\\
~{}~{}&\quad-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*},\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\right\rangle-\frac{1}{\alpha}\left\langle
V\mathbf{x}^{k},V\mathbf{x}^{k+1}\right\rangle\\\
~{}~{}&=\frac{1}{2\alpha}\left(\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}-\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\right)\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}+\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\|^{2}\right)\\\
~{}~{}&\quad-\frac{1}{2\alpha}\left(\|V\mathbf{x}^{k}\|^{2}+\|V\mathbf{x}^{k+1}\|^{2}-\|V\mathbf{x}^{k}-V\mathbf{x}^{k+1}\|^{2}\right)-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\\\
~{}~{}&\overset{d}{\leq}\frac{1}{2\alpha}\left(\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\right)+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\right)\\\
~{}~{}&\quad-\frac{1}{2\alpha}\|V\mathbf{x}^{k}\|^{2}-\frac{1}{4\alpha}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle,\end{aligned}$
(27)

where we use $U\mathbf{x}^{*}=0$, $V\mathbf{x}^{*}=0$, and the symmetry of $U$
and $V$ in $\overset{b}{=}$, (26) in $\overset{c}{=}$,
$\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\|^{2}=\|U\mathbf{x}^{k+1}\|^{2}\leq\|V\mathbf{x}^{k+1}\|^{2}$
and
$\|V(\mathbf{x}^{k+1}-\mathbf{x}^{k})\|^{2}\leq\frac{1}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}$
in $\overset{d}{\leq}$. On the other hand, from (22) and the strong convexity
of $f(\mathbf{x})$, we have

$\displaystyle\begin{aligned}
\mathbb{E}_{\mathbb{S}^{k}}\left[\left\langle\nabla^{k},\mathbf{x}^{*}-\mathbf{x}^{k}\right\rangle\right]=&\left\langle\nabla
f(\mathbf{x}^{k}),\mathbf{x}^{*}-\mathbf{x}^{k}\right\rangle\leq
f(\mathbf{x}^{*})-f(\mathbf{x}^{k})-\frac{\mu}{2}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}.\end{aligned}$
(28)

Plugging (LABEL:non-acc-cont4) and (28) into (24), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}^{k}}\big{[}f(\mathbf{x}^{k+1})\big{]}\\\ ~{}~{}&\leq
f(\mathbf{x}^{*})-\frac{\mu}{2}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}+\frac{1}{2\tau}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla
f(\mathbf{x}^{k})-\nabla^{k}\|^{2}\big{]}\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\right)+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right)\\\
~{}~{}&\quad-\frac{1}{2\alpha}\|V\mathbf{x}^{k}\|^{2}-\left(\frac{1}{4\alpha}-\frac{\tau+L_{m}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\big{]}-\frac{1}{\alpha}\mathbb{E}_{\mathbb{S}^{k}}\left[\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right].\end{aligned}$

Rearranging the terms, we have the conclusion.

To prove the linear convergence, we should make the constant before
$\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}$ in (LABEL:non-acc-one-
iter) smaller than that before
$\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}$, which is established in
the next lemma.

###### Lemma 5

Suppose that Assumption 1 and conditions (7) and (15) hold. Let
$\alpha=\frac{1}{28L_{m}}$ and $\mathbf{\lambda}^{0}=0$. Then for algorithm
(9a)-(9f), we have

$\displaystyle\begin{aligned}
&\frac{1}{2}\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq\left(\frac{1}{2\alpha}-\frac{\mu}{2}\right)\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{1-\nu}{4\kappa
L_{m}\alpha^{2}}\right)\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\frac{\overline{L}_{f}}{6L_{m}b}\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\frac{\overline{L}_{f}}{6L_{m}b}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right),\end{aligned}$
(29)

with $\nu=\frac{3140}{3141}$.

###### Proof 4

From the optimality condition in (20) and the smoothness property in (18), we
have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\lambda^{*},U\mathbf{x}^{k+1}\right\rangle=f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})-\left\langle\nabla
f(\mathbf{x}^{*}),\mathbf{x}^{k+1}-\mathbf{x}^{*}\right\rangle\\\
~{}~{}&\geq\frac{1}{2L_{m}}\|\nabla f(\mathbf{x}^{k+1})-\nabla
f(\mathbf{x}^{*})\|^{2}=\frac{1}{2L_{m}\alpha^{2}}\|\alpha\nabla
f(\mathbf{x}^{k+1})+U\lambda^{*}\|^{2}\\\
~{}~{}&\overset{a}{=}\frac{1}{2L_{m}\alpha^{2}}\left\|\mathbf{x}^{k+1}-\mathbf{x}^{k}+U(\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*})+V^{2}\mathbf{x}^{k}+\alpha\nabla^{k}-\alpha\nabla
f(\mathbf{x}^{k})+\alpha\nabla f(\mathbf{x}^{k})-\alpha\nabla
f(\mathbf{x}^{k+1})\right\|^{2}\\\
~{}~{}&\overset{b}{\geq}\frac{1-\nu}{2L_{m}\alpha^{2}}\|U(\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*})\|^{2}-\frac{1}{2L_{m}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\left\|\mathbf{x}^{k+1}-\mathbf{x}^{k}+V^{2}\mathbf{x}^{k}+\alpha\nabla^{k}-\alpha\nabla
f(\mathbf{x}^{k})+\alpha\nabla f(\mathbf{x}^{k})-\alpha\nabla
f(\mathbf{x}^{k+1})\right\|^{2}\\\
~{}~{}&\overset{c}{\geq}\frac{1-\nu}{2\kappa
L_{m}\alpha^{2}}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\left(\frac{2}{L_{m}\alpha^{2}}+2L_{m}\right)\left(\frac{1}{\nu}-1\right)\|\mathbf{x}^{k+1}-\mathbf{x}^{k}\|^{2}\\\
~{}~{}&\quad-\frac{2}{L_{m}}\left(\frac{1}{\nu}-1\right)\|\nabla^{k}-\nabla
f(\mathbf{x}^{k})\|^{2}-\frac{2}{L_{m}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\|V\mathbf{x}^{k}\|^{2},\end{aligned}$
(30)

where we use (25) in $\overset{a}{=}$,
$\|a-b\|^{2}\geq(1-\nu)\|a\|^{2}-(\frac{1}{\nu}-1)\|b\|^{2}$ in
$\overset{b}{\geq}$ for some $0<\nu<1$, (15), $\|\sum_{i=1}^{n}a_{i}\|^{2}\leq
n\sum_{i=1}^{n}\|a_{i}\|^{2}$, the $L_{f}$-smoothness of $f(\mathbf{x})$, and
$\|V^{2}\mathbf{x}^{k}\|^{2}\leq\|V\mathbf{x}^{k}\|^{2}$ in
$\overset{c}{\geq}$. Dividing both sides of (LABEL:non-acc-cont6) by 2 and
plugging it into (LABEL:non-acc-one-iter), we have

$\displaystyle\begin{aligned}
&\frac{1}{2}\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq\left(\frac{1}{2\alpha}-\frac{\mu}{2}\right)\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{1-\nu}{4\kappa
L_{m}\alpha^{2}}\right)\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\tau}+\frac{1}{L_{m}}\left(\frac{1}{\nu}-1\right)\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla
f(\mathbf{x}^{k})-\nabla^{k}\|^{2}\big{]}-\left(\frac{1}{2\alpha}-\frac{1}{L_{m}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\right)\|V\mathbf{x}^{k}\|^{2}\\\
~{}~{}&\quad-\left(\frac{1}{4\alpha}-\frac{\tau+L_{m}}{2}-\left(\frac{1}{L_{m}\alpha^{2}}+L_{m}\right)\left(\frac{1}{\nu}-1\right)\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{k+1}\|^{2}\big{]}.\end{aligned}$

Letting $\tau=12.5L_{m}$, $\nu=\frac{3140}{3141}$, and
$\alpha=\frac{1}{28L_{m}}$, such that
$\frac{1}{2\alpha}-\frac{1}{L_{m}\alpha^{2}}(\frac{1}{\nu}-1)\geq 0$,
$\frac{1}{4\alpha}-\frac{\tau+L_{m}}{2}-(\frac{1}{L_{m}\alpha^{2}}+L_{m})(\frac{1}{\nu}-1)\geq
0$, and
$\frac{1}{2\tau}+\frac{1}{L_{m}}(\frac{1}{\nu}-1)\leq\frac{1}{24L_{m}}$, and
using (21), we have the conclusion.

Now, we are ready to prove Theorem 1, which can be directly obtained by part 1
of the following lemma.

###### Lemma 6

Suppose that Assumption 1 and conditions (7) and (15) hold. Let
$\alpha=\frac{1}{28L_{m}}$ and $\mathbf{\lambda}^{0}=0$.

  1. 1.

If $\kappa\leq\max\\{\frac{\overline{L}_{f}}{\mu},n\\}$, let
$b=\frac{\max\\{\overline{L}_{f},n\mu\\}}{L_{m}}$. Algorithm (9a)-(9f)
requires the time of ${\cal
O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$ communication rounds and
${\cal O}((\frac{\overline{L}_{f}}{\mu}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$.

  2. 2.

If $\kappa\geq\max\\{\frac{\overline{L}_{f}}{\mu},n\\}$, let $b=1$. Algorithm
(9a)-(9f) requires the time of ${\cal
O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$ communication rounds and
${\cal O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$.

###### Proof 5

From step (9f), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{w_{(i)}^{k+1}}\left[f_{(i)}(w_{(i)}^{k+1})-\left\langle\nabla
f_{(i)}(x^{*}),w_{(i)}^{k+1}-x^{*}\right\rangle\right]\\\
~{}~{}&=\frac{b}{n}\left(f_{(i)}(x_{(i)}^{k})-\left\langle\nabla
f_{(i)}(x^{*}),x_{(i)}^{k}-x^{*}\right\rangle\right)+\left(1-\frac{b}{n}\right)\left(f_{(i)}(w_{(i)}^{k})-\left\langle\nabla
f_{(i)}(x^{*}),w_{(i)}^{k}-x^{*}\right\rangle\right).\end{aligned}$

From the definitions in (2), and the optimality condition in (20), we further
have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbf{w}^{k+1}}\left[f(\mathbf{w}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k+1}\right\rangle\right]\\\
~{}~{}&=\frac{b}{n}\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\left(1-\frac{b}{n}\right)\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right).\end{aligned}$
(31)

Multiplying both sides of (LABEL:non-acc-cont3) by
$\frac{n}{b}(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b})$ and
adding it to (LABEL:non-acc-cont2), taking expectation with respect to
$\xi^{k}$, from the easy-to-identity equation
$\frac{n}{b}(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b})(1-\frac{b}{n})+\frac{\overline{L}_{f}}{6L_{m}b}\leq\frac{n}{b}(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b})(1-\frac{b}{10n})$
under the condition $\frac{\overline{L}_{f}}{L_{m}b}\leq 1$, we have

$\displaystyle\begin{aligned}
&\frac{1}{2}\mathbb{E}_{\xi^{k+1}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad+\frac{n}{b}\left(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b}\right)\mathbb{E}_{\xi^{k+1}}\left[f(\mathbf{w}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k+1}}\big{[}\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k+1}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\leq\left(\frac{1}{2}-\frac{b}{10n}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right]\\\
~{}~{}&\quad+\frac{n}{b}\left(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b}\right)\left(1-\frac{b}{10n}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right]\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{\mu}{2}\right)\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}\big{]}+\left(\frac{1}{2\alpha}-\frac{1-\nu}{4\kappa
L_{m}\alpha^{2}}\right)\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\overset{a}{\leq}\left\\{\frac{1}{2}\mathbb{E}_{\xi^{k}}\left[f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right]\right.\\\
~{}~{}&\quad\left.+\frac{n}{b}\left(\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right]\right.\\\
~{}~{}&\quad\left.+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}\big{]}+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right\\}\\\
~{}~{}&\quad\times\max\left\\{1-\frac{b}{5n},1-\frac{b}{10n},1-\alpha\mu,1-\frac{1-\nu}{2\kappa
L_{m}\alpha}\right\\},\end{aligned}$

where we use the fact
$f(\mathbf{x})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}\right\rangle\geq
f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{*}\right\rangle$
for any $\mathbf{x}$, and
$\frac{1}{2}-\frac{b}{10n}-\frac{\overline{L}_{f}}{6L_{m}b}>0$ in
$\overset{a}{\leq}$. From the setting of $\alpha$, we know the algorithm needs
${\cal
O}((\frac{n}{b}+\frac{L_{m}}{\mu}+\kappa)\log\frac{1}{\epsilon})\overset{b}{=}{\cal
O}((\frac{n}{b}+\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$ iterations
to find $\mathbf{x}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{x}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$,
where we use $L_{m}=\max\\{L_{f},\kappa\mu\\}$ in $\overset{b}{=}$. Recall
that each iteration requires the time of one communication round and $b$
stochastic gradient evaluations in average, see Remark 1. So the communication
complexity is ${\cal
O}((\frac{n}{b}+\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$, and the
stochastic gradient computation complexity is ${\cal
O}((n+\frac{bL_{f}}{\mu}+b\kappa)\log\frac{1}{\epsilon})={\cal
O}((n+\frac{bL_{m}}{\mu})\log\frac{1}{\epsilon})$.

Case 1. If $\kappa\leq\max\\{\frac{\overline{L}_{f}}{\mu},n\\}$, we have
$\kappa\mu\leq\max\\{\overline{L}_{f},n\mu\\}$ and
$b=\frac{\max\\{\overline{L}_{f},n\mu\\}}{\max\\{L_{f},\kappa\mu\\}}\geq\frac{\max\\{\overline{L}_{f},n\mu\\}}{\max\\{\overline{L}_{f},n\mu\\}}=1$,
where we use $L_{f}\leq\overline{L}_{f}\leq\max\\{\overline{L}_{f},n\mu\\}$.
On the other hand, since $b=\frac{\max\\{\overline{L}_{f},n\mu\\}}{L_{m}}$, we
have
$\frac{\overline{L}_{f}}{L_{m}b}=\frac{\overline{L}_{f}}{\max\\{\overline{L}_{f},n\mu\\}}\leq
1$ and
$\frac{n}{b}=\frac{nL_{m}}{\max\\{\overline{L}_{f},n\mu\\}}\leq\frac{L_{m}}{\mu}=\max\\{\frac{L_{f}}{\mu},\kappa\\}$.
Then the communication complexity is ${\cal
O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$, and the stochastic
gradient computation complexity is ${\cal
O}((\frac{\overline{L}_{f}}{\mu}+n)\log\frac{1}{\epsilon})$, where we use
$\frac{bL_{m}}{\mu}=\frac{\max\\{\overline{L}_{f},n\mu\\}}{\mu}$.

If we choose $b\geq\frac{\max\\{\overline{L}_{f},n\mu\\}}{L_{m}}$, similar to
the above analysis, we also have $\frac{\overline{L}_{f}}{L_{m}b}\leq 1$ and
$\frac{n}{b}\leq\max\\{\frac{L_{f}}{\mu},\kappa\\}$. So the communication
complexity remains unchanged, but the stochastic gradient computation
complexity increases. This verifies Remark 2(4).

Case 2. If $\kappa\geq\max\\{\frac{\overline{L}_{f}}{\mu},n\\}$, letting
$b=1$, we have
$\frac{\overline{L}_{f}}{L_{m}b}\leq\frac{\overline{L}_{f}}{\kappa\mu}\leq 1$.
The communication complexity and stochastic gradient computation complexity
are both ${\cal O}((\frac{L_{f}}{\mu}+n+\kappa)\log\frac{1}{\epsilon})={\cal
O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$.

Now, we prove Theorem 2, which improves the computation complexity in the case
of $\kappa\geq\max\\{\frac{\overline{L}_{f}}{\mu},n\\}$ by the zero-sample
strategy.

###### Proof 6

Replacing $n$, $L_{f}$, $\mu$, and $\overline{L}_{f}$ in Lemma 6 by
$n^{\prime}$, $L_{f}^{\prime}$, $\mu^{\prime}$, and
$\overline{L}_{f}^{\prime}$ given in (14), respectively, since
$\frac{\overline{L}_{f}^{\prime}}{\mu^{\prime}}=n^{\prime}=\kappa$, from the
first case in Lemma 6, we have the ${\cal
O}((\frac{L_{f}^{\prime}}{\mu^{\prime}}+\kappa)\log\frac{1}{\epsilon})={\cal
O}((\frac{L_{f}}{\mu}+\kappa)\log\frac{1}{\epsilon})$ communication
complexity, and the ${\cal
O}((\frac{\overline{L}_{f}^{\prime}}{\mu^{\prime}}+n^{\prime})\log\frac{1}{\epsilon})={\cal
O}(\kappa\log\frac{1}{\epsilon})$ stochastic gradient computation complexity.

Since we select the samples in $\big{[}1,n\big{]}$ with probability
$\frac{\sum_{j=1}^{n}L_{(i),j}}{\sum_{j=1}^{n^{\prime}}L_{(i),j}}=\frac{n\overline{L}_{f}}{n\mu\kappa}$,
and the zero samples do not spend the computation time, so the valid number of
stochastic gradient evaluations is ${\cal
O}(\frac{\overline{L}_{f}}{\mu\kappa}\kappa\log\frac{1}{\epsilon})={\cal
O}(\frac{\overline{L}_{f}}{\mu}\log\frac{1}{\epsilon})$. On the other hand, we
compute the full batch gradient with probability
$\frac{b}{n^{\prime}}=\frac{1}{\kappa}$, which takes ${\cal
O}(n\frac{1}{\kappa}\kappa\log\frac{1}{\epsilon})={\cal
O}(n\log\frac{1}{\epsilon})$ stochastic gradient evaluations in total. So the
final valid stochastic gradient computation complexity is ${\cal
O}((\frac{\overline{L}_{f}}{\mu}+n)\log\frac{1}{\epsilon})$.

At last, we explain that the zero samples do not destroy the proof of Lemma 6.
For the zero sample $f_{(i),j}(x)=0$, we have $\nabla f_{(i),j}(x)=0$. So it
also satisfies the convexity and $L_{(i),j}$-smooth property (18) even for
positive $L_{(i),j}$. We can check that (21) and (22) also hold. In the proofs
of Lemmas 4 and 5, we use the smoothness and strong convexity of
$f_{(i)}^{\prime}(x)$, as explained in Section 2.3, which also hold.

###  4.2 Accelerated VR-EXTRA and VR-DIGing

From Lemma D.2 in (Allen-Zhu, 2018) and similar to Lemma 2, we have

$\displaystyle\begin{aligned}
\qquad\qquad\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\nabla^{k}-\nabla
f(\mathbf{y}^{k})\|^{2}\big{]}\leq\frac{2\overline{L}_{f}}{b}\left(f(\mathbf{w}^{k})-f(\mathbf{y}^{k})-\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\right).\end{aligned}$
(32)

Similar to (22), we also have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}^{k}}\big{[}\nabla^{k}\big{]}=\nabla
f(\mathbf{y}^{k}).\end{aligned}$ (33)

The following lemma is the counterpart of Lemma 4, which gives a progress in
one iteration of procedure (16a)-(16h).

###### Lemma 7

Suppose that Assumption 1 and conditions (7) and (15) hold. Let
$\theta_{1}+\theta_{2}\leq 1$. Then for algorithm (16a)-(16h), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq(1-\theta_{1}-\theta_{2})\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\theta_{2}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\left(\frac{\overline{L}_{f}}{\tau
b}-\theta_{2}\right)\left(f(\mathbf{w}^{k})-f(\mathbf{y}^{k})-\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\frac{1}{2\alpha}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad-\frac{\theta_{1}^{2}}{2\alpha}\|V\mathbf{z}^{k}\|^{2}-\left(\frac{\theta_{1}^{2}}{4\alpha}-\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\big{]}-\frac{\mu\theta_{1}}{2}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}\big{]},\end{aligned}$
(34)

for some $\tau>0$.

###### Proof 7

From the $L_{f}$-smoothness of $f(\mathbf{x})$, similar to (24), we have

$\displaystyle\begin{aligned} f(\mathbf{x}^{k+1})&\leq
f(\mathbf{y}^{k})+\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\mathbf{y}^{k}\right\rangle+\frac{L_{f}}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|^{2}\\\
~{}~{}&\leq f(\mathbf{y}^{k})+\frac{1}{2\tau}\|\nabla
f(\mathbf{y}^{k})-\nabla^{k}\|^{2}+\frac{\tau+L_{f}}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|^{2}+\left\langle\nabla^{k},\mathbf{x}^{k+1}-\mathbf{y}^{k}\right\rangle\\\
~{}~{}&\overset{a}{=}f(\mathbf{y}^{k})+\frac{1}{2\tau}\|\nabla
f(\mathbf{y}^{k})-\nabla^{k}\|^{2}+\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}+\theta_{1}\left\langle\nabla^{k},\mathbf{z}^{k+1}-\mathbf{z}^{*}\right\rangle+\theta_{1}\left\langle\nabla^{k},\mathbf{z}^{*}-\mathbf{z}^{k}\right\rangle.\end{aligned}$
(35)

where we use

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

in $\overset{a}{=}$, which is from (16e). Since

$\displaystyle\nabla^{k}=\frac{\theta_{1}}{\alpha}(\mathbf{z}^{k}-\mathbf{z}^{k+1})+\mu(\mathbf{y}^{k}-\mathbf{z}^{k+1})-\frac{1}{\alpha}U\mathbf{\lambda}^{k}-\frac{\theta_{1}}{\alpha}V^{2}\mathbf{z}^{k},$
(37)
$\displaystyle\mathbf{\lambda}^{k+1}=\mathbf{\lambda}^{k}+\theta_{1}U\mathbf{z}^{k+1},$
(38)

from (16c) and (16d), similar to (LABEL:non-acc-cont4), we have

$\displaystyle\begin{aligned}
&\theta_{1}\left\langle\nabla^{k},\mathbf{z}^{k+1}-\mathbf{x}^{*}\right\rangle\\\
~{}~{}&=\frac{\theta_{1}^{2}}{\alpha}\left\langle\mathbf{z}^{k}-\mathbf{z}^{k+1},\mathbf{z}^{k+1}-\mathbf{x}^{*}\right\rangle+\mu\theta_{1}\left\langle\mathbf{y}^{k}-\mathbf{z}^{k+1},\mathbf{z}^{k+1}-\mathbf{x}^{*}\right\rangle-\frac{\theta_{1}}{\alpha}\left\langle\mathbf{\lambda}^{k},U\mathbf{z}^{k+1}\right\rangle-\frac{\theta_{1}^{2}}{\alpha}\left\langle
V\mathbf{z}^{k},V\mathbf{z}^{k+1}\right\rangle\\\
~{}~{}&\overset{b}{=}\frac{\theta_{1}^{2}}{\alpha}\left\langle\mathbf{z}^{k}-\mathbf{z}^{k+1},\mathbf{z}^{k+1}-\mathbf{x}^{*}\right\rangle+\mu\theta_{1}\left\langle\mathbf{y}^{k}-\mathbf{z}^{k+1},\mathbf{z}^{k+1}-\mathbf{x}^{*}\right\rangle\\\
~{}~{}&\quad-\frac{\theta_{1}}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{z}^{k+1}\right\rangle-\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*},\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\right\rangle-\frac{\theta_{1}^{2}}{\alpha}\left\langle
V\mathbf{z}^{k},V\mathbf{z}^{k+1}\right\rangle\\\
~{}~{}&=\frac{\theta_{1}^{2}}{2\alpha}\left(\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\right)\\\
~{}~{}&\quad+\frac{\mu\theta_{1}}{2}\left(\|\mathbf{y}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}\right)\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}+\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\|^{2}\right)\\\
~{}~{}&\quad-\frac{\theta_{1}^{2}}{2\alpha}\left(\|V\mathbf{z}^{k}\|^{2}+\|V\mathbf{z}^{k+1}\|^{2}-\|V\mathbf{z}^{k+1}-V\mathbf{z}^{k}\|^{2}\right)-\frac{\theta_{1}}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{z}^{k+1}\right\rangle\\\
~{}~{}&\overset{c}{\leq}\frac{\theta_{1}^{2}}{2\alpha}\left(\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\right)+\frac{\mu\theta_{1}}{2}\left(\|\mathbf{y}^{k}-\mathbf{x}^{*}\|^{2}-\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\right)\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\right)-\frac{\theta_{1}^{2}}{2\alpha}\|V\mathbf{z}^{k}\|^{2}-\frac{\theta_{1}^{2}}{4\alpha}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\\\
~{}~{}&\quad-\frac{\mu\theta_{1}}{2}\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}-\frac{\theta_{1}}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{z}^{k+1}\right\rangle,\end{aligned}$
(39)

where we use (38) in $\overset{b}{=}$,
$\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{k}\|^{2}=\|\theta_{1}U\mathbf{z}^{k+1}\|^{2}\leq\theta_{1}^{2}\|V\mathbf{z}^{k+1}\|^{2}$
and
$\|V(\mathbf{z}^{k+1}-\mathbf{z}^{k})\|^{2}\leq\frac{1}{2}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}$
in $\overset{c}{\leq}$. On the other hand, from (LABEL:acc-nabla-y), we have

$\displaystyle\begin{aligned}
&\theta_{1}\mathbb{E}_{\mathbb{S}^{k}}\left[\left\langle\nabla^{k},\mathbf{x}^{*}-\mathbf{z}^{k}\right\rangle\right]\\\
~{}~{}&=\theta_{1}\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{*}-\mathbf{z}^{k}\right\rangle\\\
~{}~{}&\overset{d}{=}\left\langle\nabla
f(\mathbf{y}^{k}),\theta_{1}\mathbf{x}^{*}+\theta_{2}\mathbf{w}^{k}+(1-\theta_{1}-\theta_{2})\mathbf{x}^{k}-\mathbf{y}^{k}\right\rangle\\\
~{}~{}&=\theta_{1}\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{*}-\mathbf{y}^{k}\right\rangle+(1-\theta_{1}-\theta_{2})\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k}-\mathbf{y}^{k}\right\rangle+\theta_{2}\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\\\
~{}~{}&\overset{e}{\leq}\theta_{1}f(\mathbf{x}^{*})+(1-\theta_{1}-\theta_{2})f(\mathbf{x}^{k})-(1-\theta_{2})f(\mathbf{y}^{k})-\frac{\mu\theta_{1}}{2}\|\mathbf{y}^{k}-\mathbf{x}^{*}\|^{2}+\theta_{2}\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle,\end{aligned}$
(40)

where we use (16a) in $\overset{d}{=}$, and the strong convexity of
$f(\mathbf{x})$ in $\overset{e}{=}$. Plugging (LABEL:acc-cont2) and
(LABEL:acc-cont3) into (35), and using (32), we have

$\displaystyle\begin{aligned}
&\mathbb{E}_{\mathbb{S}^{k}}\big{[}f(\mathbf{x}^{k+1})\big{]}\\\
~{}~{}&\leq\theta_{1}f(\mathbf{x}^{*})+(1-\theta_{1}-\theta_{2})f(\mathbf{x}^{k})+\theta_{2}f(\mathbf{y}^{k})-\frac{\mu\theta_{1}}{2}\|\mathbf{y}^{k}-\mathbf{x}^{*}\|^{2}+\theta_{2}\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\\\
~{}~{}&\quad+\frac{\overline{L}_{f}}{\tau
b}\left(f(\mathbf{w}^{k})-f(\mathbf{y}^{k})-\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\left(\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\right)+\frac{\mu\theta_{1}}{2}\left(\|\mathbf{y}^{k}-\mathbf{x}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\right)\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right)-\frac{\theta_{1}}{\alpha}\mathbb{E}_{\mathbb{S}^{k}}\left[\left\langle\mathbf{\lambda}^{*},U\mathbf{z}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad-\frac{\theta_{1}^{2}}{2\alpha}\|V\mathbf{z}^{k}\|^{2}-\left(\frac{\theta_{1}^{2}}{4\alpha}-\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\big{]}-\frac{\mu\theta_{1}}{2}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}\big{]}\\\
~{}~{}&\overset{f}{=}\theta_{1}f(\mathbf{x}^{*})+(1-\theta_{1}-\theta_{2})f(\mathbf{x}^{k})+\theta_{2}f(\mathbf{w}^{k})\\\
~{}~{}&\quad+\left(\frac{\overline{L}_{f}}{\tau
b}-\theta_{2}\right)\left(f(\mathbf{w}^{k})-f(\mathbf{y}^{k})-\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\frac{1}{2\alpha}\left(\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right)\\\
~{}~{}&\quad-\frac{1}{\alpha}\mathbb{E}_{\mathbb{S}^{k}}\left[\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}-\theta_{2}U\mathbf{w}^{k}-(1-\theta_{1}-\theta_{2})U\mathbf{x}^{k}\right\rangle\right]\\\
~{}~{}&\quad-\frac{\theta_{1}^{2}}{2\alpha}\|V\mathbf{z}^{k}\|^{2}-\left(\frac{\theta_{1}^{2}}{4\alpha}-\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\big{]}-\frac{\mu\theta_{1}}{2}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}\big{]},\end{aligned}$

where we use (16a) and (16e) in $\overset{f}{=}$. Rearranging the terms, we
have the conclusion.

Similar to Lemma 5, we establish the smaller constant before
$\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}$ than that before
$\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}$ in the next lemma.

###### Lemma 8

Suppose that Assumption 1 and conditions (7) and (15) hold. Choose $b$ such
that $\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}\leq\frac{1}{2}$. Let
$\theta_{1}\leq\frac{1}{2}$, $\alpha=\frac{1}{10L_{f}}$, and
$\mathbf{\lambda}^{0}=0$. Then for algorithm (16a)-(16h), we have

$\displaystyle\begin{aligned}
&\left(1-\frac{\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq(1-\theta_{1}-\theta_{2})\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\theta_{2}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{(1-\nu)\theta_{1}}{4\kappa
L_{f}\alpha^{2}}\right)\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]},\end{aligned}$
(41)

with $\nu=\frac{127}{128}$.

###### Proof 8

From (18) and (20), similar to (LABEL:non-acc-cont6), we have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\lambda^{*},U\mathbf{x}^{k+1}\right\rangle\geq\frac{1}{2L_{f}\alpha^{2}}\|\alpha\nabla
f(\mathbf{x}^{k+1})+U\lambda^{*}\|^{2}\\\
~{}~{}&\overset{a}{=}\frac{1}{2L_{f}\alpha^{2}}\left\|\alpha\mu(\mathbf{z}^{k+1}-\mathbf{y}^{k})+\theta_{1}(\mathbf{z}^{k+1}-\mathbf{z}^{k})+U(\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*})+\theta_{1}V^{2}\mathbf{z}^{k}\right.\\\
~{}~{}&\quad\hskip 38.41139pt\left.+\alpha\nabla^{k}-\alpha\nabla
f(\mathbf{y}^{k})+\alpha\nabla f(\mathbf{y}^{k})-\alpha\nabla
f(\mathbf{x}^{k+1})\right\|^{2}\\\
~{}~{}&\geq\frac{1-\nu}{2L_{f}\alpha^{2}}\|U(\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*})\|^{2}-\frac{1}{2L_{f}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\left\|\alpha\mu(\mathbf{z}^{k+1}-\mathbf{y}^{k})+\theta_{1}(\mathbf{z}^{k+1}-\mathbf{z}^{k})\right.\\\
~{}~{}&\quad\hskip
79.6678pt\left.+\theta_{1}V^{2}\mathbf{z}^{k}+\alpha\nabla^{k}-\alpha\nabla
f(\mathbf{y}^{k})+\alpha\nabla f(\mathbf{y}^{k})-\alpha\nabla
f(\mathbf{x}^{k+1})\right\|^{2}\\\
~{}~{}&\overset{b}{\geq}\frac{1-\nu}{2\kappa
L_{f}\alpha^{2}}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{5\mu^{2}}{2L_{f}}\left(\frac{1}{\nu}-1\right)\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}-\frac{5\theta_{1}^{2}}{2L_{f}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\|V\mathbf{z}^{k}\|^{2}\\\
~{}~{}&\quad-\frac{5}{2L_{f}}\left(\frac{1}{\nu}-1\right)\|\nabla^{k}-\nabla
f(\mathbf{y}^{k})\|^{2}-\left(\frac{5\theta_{1}^{2}}{2L_{f}\alpha^{2}}+\frac{5L_{f}\theta_{1}^{2}}{2}\right)\left(\frac{1}{\nu}-1\right)\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2},\end{aligned}$
(42)

where we use (37) in $\overset{a}{=}$, (15), the $L_{f}$-smoothness of
$f(\mathbf{x})$, (36), and
$\|V^{2}\mathbf{z}^{k}\|^{2}\leq\|V\mathbf{z}^{k}\|^{2}$ in
$\overset{b}{\geq}$. Multiplying both sides of (LABEL:acc-cont7) by
$\frac{\theta_{1}}{2}$ and plugging it into (LABEL:acc-cont8), using (32), we
have

$\displaystyle\begin{aligned}
&\left(1-\frac{\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq(1-\theta_{1}-\theta_{2})\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)+\theta_{2}\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\left(\frac{\overline{L}_{f}}{\tau
b}+\frac{5\overline{L}_{f}\theta_{1}}{2bL_{f}}\left(\frac{1}{\nu}-1\right)-\theta_{2}\right)\left(f(\mathbf{w}^{k})-f(\mathbf{y}^{k})-\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{w}^{k}-\mathbf{y}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{(1-\nu)\theta_{1}}{4\kappa
L_{f}\alpha^{2}}\right)\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad-\left(\frac{\theta_{1}^{2}}{2\alpha}-\frac{5\theta_{1}^{3}}{4L_{f}\alpha^{2}}\left(\frac{1}{\nu}-1\right)\right)\|V\mathbf{z}^{k}\|^{2}-\left(\frac{\mu\theta_{1}}{2}-\frac{5\mu^{2}\theta_{1}}{4L_{f}}\left(\frac{1}{\nu}-1\right)\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{y}^{k}\|^{2}\big{]}\\\
~{}~{}&\quad-\left(\frac{\theta_{1}^{2}}{4\alpha}-\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}-\left(\frac{5\theta_{1}^{3}}{4L_{f}\alpha^{2}}+\frac{5L_{f}\theta_{1}^{3}}{4}\right)\left(\frac{1}{\nu}-1\right)\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{z}^{k}\|^{2}\big{]}.\end{aligned}$

Letting $\theta_{1}\leq\frac{1}{2}$,
$\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}$, $\tau=3L_{f}$,
$\nu=\frac{127}{128}$, and $\alpha=\frac{1}{10L_{f}}$ such that
$\frac{\overline{L}_{f}}{\tau
b}+\frac{5\overline{L}_{f}\theta_{1}}{2L_{f}b}(\frac{1}{\nu}-1)-\theta_{2}\leq
0$,
$\frac{\theta_{1}^{2}}{2\alpha}-\frac{5\theta_{1}^{3}}{4L_{f}\alpha^{2}}(\frac{1}{\nu}-1)\geq
0$,
$\frac{\mu\theta_{1}}{2}-\frac{5\mu^{2}\theta_{1}}{4L_{f}}(\frac{1}{\nu}-1)\geq
0$, and
$\frac{\theta_{1}^{2}}{4\alpha}-\frac{\tau\theta_{1}^{2}+L_{f}\theta_{1}^{2}}{2}-(\frac{5\theta_{1}^{3}}{4L_{f}\alpha^{2}}+\frac{5L_{f}\theta_{1}^{3}}{4})(\frac{1}{\nu}-1)\geq
0$, we have the conclusion.

Now, we are ready to prove Theorem 3, which can be directly obtained by part 1
of the following lemma.

###### Lemma 9

Suppose that Assumption 1 and conditions (7) and (15) hold. Assume
$\frac{\kappa\mu}{L_{f}}\leq 1$ and $\kappa\geq 1$. Let
$\theta_{1}=\frac{1}{2}\sqrt{\frac{\kappa\mu}{L_{f}}}$,
$\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}$, $\alpha=\frac{1}{10L_{f}}$, and
$\mathbf{\lambda}^{0}=0$.

  1. 1.

If
$\kappa\leq\frac{nL_{f}\max\\{\overline{L}_{f},n\mu\\}}{\overline{L}_{f}^{2}}$,
let $b=\sqrt{\frac{n\max\\{\overline{L}_{f},n\mu\\}}{\kappa L_{f}}}$. Then
algorithm (16a)-(16h) requires the time of ${\cal O}(\sqrt{\frac{\kappa
L_{f}}{\mu}}\log\frac{1}{\epsilon})$ communication rounds and ${\cal
O}((\sqrt{\frac{n\overline{L}_{f}}{\mu}}+n)\log\frac{1}{\epsilon})$ stochastic
gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$.

  2. 2.

If
$\kappa\geq\frac{nL_{f}\max\\{\overline{L}_{f},n\mu\\}}{\overline{L}_{f}^{2}}$,
let $b=\frac{\overline{L}_{f}}{L_{f}}$. Then algorithm (16a)-(16h) requires
the time of ${\cal O}(\sqrt{\frac{\kappa L_{f}}{\mu}}\log\frac{1}{\epsilon})$
communication rounds and ${\cal
O}(\sqrt{\frac{\kappa\overline{L}_{f}^{2}}{L_{f}\mu}}\log\frac{1}{\epsilon})$
stochastic gradient evaluations to find $\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$.

###### Proof 9

Let $b\geq\max\\{\sqrt{\frac{n\overline{L}_{f}}{\kappa
L_{f}}},\sqrt{\frac{n^{2}\mu}{\kappa
L_{f}}},\frac{\overline{L}_{f}}{L_{f}}\\}$, then we know
$\theta_{2}=\frac{\overline{L}_{f}}{2L_{f}b}\leq\frac{1}{2}$ and $b\geq 1$.
Note that since $\kappa\geq 1$ and $\mu\leq L_{f}\leq\overline{L}_{f}\leq
nL_{f}$ given in (4), we have $\max\\{\sqrt{\frac{n\overline{L}_{f}}{\kappa
L_{f}}},\sqrt{\frac{n^{2}\mu}{\kappa
L_{f}}},\frac{\overline{L}_{f}}{L_{f}}\\}\leq n$. Multiplying both sides of
(LABEL:non-acc-cont3) by
$\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}$ and adding it to
(LABEL:acc-cont9), we have

$\displaystyle\begin{aligned}
&\left(1-\frac{\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad+\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\mathbb{E}_{\mathbf{w}^{k+1}}\left[f(\mathbf{w}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k+1}\right\rangle\right]\\\
~{}~{}&\leq\left(1-\theta_{1}-\theta_{2}+\frac{b}{n}\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\right)\left(f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\left(\theta_{2}+\left(1-\frac{b}{n}\right)\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\right)\left(f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right)\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}-\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}\\\
~{}~{}&\quad+\left(\frac{1}{2\alpha}-\frac{(1-\nu)\theta_{1}}{4\kappa
L_{f}\alpha^{2}}\right)\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}-\frac{1}{2\alpha}\mathbb{E}_{\mathbb{S}^{k}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}.\end{aligned}$
(43)

We can easily check that

$\displaystyle\begin{aligned}
&1-\theta_{1}-\theta_{2}+\frac{b}{n}\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}=1-\theta_{1}-\theta_{2}+\frac{\theta_{2}}{1-\frac{n\theta_{1}}{20b\kappa}}=1-\theta_{1}+\frac{\frac{n\theta_{1}\theta_{2}}{20b\kappa}}{1-\frac{n\theta_{1}}{20b\kappa}}\overset{a}{\leq}1-\theta_{1}+\frac{\theta_{1}}{39}=1-\frac{38}{39}\theta_{1},\end{aligned}$

and

$\displaystyle\begin{aligned}
\theta_{2}+\left(1-\frac{b}{n}\right)\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}&=\theta_{2}+\left(\frac{\theta_{1}}{20\kappa}-\frac{b}{n}\right)\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}+\left(1-\frac{\theta_{1}}{20\kappa}\right)\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}=\left(1-\frac{\theta_{1}}{20\kappa}\right)\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}},\end{aligned}$

where we use
$\frac{n\theta_{2}}{20b\kappa}=\frac{n\overline{L}_{f}}{40L_{f}b^{2}\kappa}\leq\frac{n\overline{L}_{f}}{40L_{f}\kappa}\frac{\kappa
L_{f}}{n\overline{L}_{f}}=\frac{1}{40}$ and
$\frac{n\theta_{1}}{20b\kappa}\leq\frac{n\theta_{1}}{20\kappa}\sqrt{\frac{\kappa
L_{f}}{n^{2}\mu}}\overset{b}{=}\frac{1}{40}$ in $\overset{a}{\leq}$.
$\overset{b}{=}$ can be verified by the setting of $\theta_{1}$. Taking
expectation with respect to $\xi^{k}$ on both sides of (LABEL:acc-cont10) and
rearranging the terms, we have

$\displaystyle\begin{aligned}
&\left(1-\frac{\theta_{1}}{2}\right)\mathbb{E}_{\xi^{k+1}}\left[f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad+\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\mathbb{E}_{\xi^{k+1}}\left[f(\mathbf{w}^{k+1})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k+1}\right\rangle\right]\\\
~{}~{}&\quad+\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\xi^{k+1}}\big{[}\|\mathbf{z}^{k+1}-\mathbf{x}^{*}\|^{2}\big{]}+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k+1}}\big{[}\|\mathbf{\lambda}^{k+1}-\mathbf{\lambda}^{*}\|^{2}\big{]}\\\
~{}~{}&\leq\left(1-\frac{38}{39}\theta_{1}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right]\\\
~{}~{}&\quad+\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\left(1-\frac{\theta_{1}}{20\kappa}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right]\\\
~{}~{}&\quad+\frac{\theta_{1}^{2}}{2\alpha}\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}\big{]}+\left(\frac{1}{2\alpha}-\frac{(1-\nu)\theta_{1}}{4\kappa
L_{f}\alpha^{2}}\right)\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}\big{]}\end{aligned}$
$\displaystyle\begin{aligned}
~{}~{}&\overset{c}{\leq}\left\\{\left(1-\frac{\theta_{1}}{2}\right)\mathbb{E}_{\xi^{k}}\left[f(\mathbf{x}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{k}\right\rangle\right]\right.\\\
~{}~{}&\quad\left.+\frac{\theta_{2}}{\frac{b}{n}-\frac{\theta_{1}}{20\kappa}}\mathbb{E}_{\xi^{k}}\left[f(\mathbf{w}^{k})-f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{w}^{k}\right\rangle\right]\right.\\\
~{}~{}&\quad\left.+\left(\frac{\theta_{1}^{2}}{2\alpha}+\frac{\mu\theta_{1}}{2}\right)\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}\big{]}+\frac{1}{2\alpha}\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{\lambda}^{k}-\mathbf{\lambda}^{*}\|^{2}\big{]}\right\\}\\\
~{}~{}&\quad\times\max\left\\{\frac{1-\frac{38}{39}\theta_{1}}{1-\frac{\theta_{1}}{2}},1-\frac{\theta_{1}}{20\kappa},\frac{1}{1+\frac{\mu\alpha}{\theta_{1}}},1-\frac{(1-\nu)\theta_{1}}{2\kappa
L_{f}\alpha}\right\\},\end{aligned}$

where we use the fact
$f(\mathbf{x})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}\right\rangle\geq
f(\mathbf{x}^{*})+\frac{1}{\alpha}\left\langle\mathbf{\lambda}^{*},U\mathbf{x}^{*}\right\rangle$
for any $\mathbf{x}$, and $\frac{b}{n}\overset{d}{\geq}\sqrt{\frac{\mu}{\kappa
L_{f}}}\overset{e}{\geq}\frac{\theta_{1}}{20\kappa}$ in $\overset{c}{\leq}$.
$\overset{d}{\geq}$ and $\overset{e}{\geq}$ can be verified by the settings of
$b$ and $\theta_{1}$, respectively.

From the settings of $\theta_{1}$ and $\alpha$ and the assumption $\kappa\geq
1$, we can easily check
$\frac{1-\frac{38}{39}\theta_{1}}{1-\frac{\theta_{1}}{2}}\leq
1-\frac{18}{39}\theta_{1}\leq 1-\frac{18}{39}\frac{\theta_{1}}{\kappa}={\cal
O}(1-\sqrt{\frac{\mu}{\kappa L_{f}}})$ due to $\kappa\geq 1$,
$\frac{1}{1+\frac{\mu\alpha}{\theta_{1}}}\leq
1-\frac{\mu\alpha}{2\theta_{1}}={\cal O}(1-\sqrt{\frac{\mu}{\kappa L_{f}}})$,
and $1-\frac{(1-\nu)\theta_{1}}{2\kappa L_{f}\alpha}={\cal
O}(1-\sqrt{\frac{\mu}{\kappa L_{f}}})$. Thus the algorithm needs ${\cal
O}(\sqrt{\frac{\kappa L_{f}}{\mu}}\log\frac{1}{\epsilon})$ iterations to find
$\mathbf{z}^{k}$ such that
$\mathbb{E}_{\xi^{k}}\big{[}\|\mathbf{z}^{k}-\mathbf{x}^{*}\|^{2}\big{]}\leq\epsilon$.
So the communication complexity is ${\cal O}(\sqrt{\frac{\kappa
L_{f}}{\mu}}\log\frac{1}{\epsilon})$.

When $b=\sqrt{\frac{n\overline{L}_{f}}{\kappa L_{f}}}$, the stochastic
gradient computation complexity is ${\cal O}(b\sqrt{\frac{\kappa
L_{f}}{\mu}}\log\frac{1}{\epsilon})={\cal
O}(\sqrt{\frac{n\overline{L}_{f}}{\mu}}\log\frac{1}{\epsilon})$. When
$b=\sqrt{\frac{n^{2}\mu}{\kappa L_{f}}}$, the stochastic gradient computation
complexity is ${\cal O}(b\sqrt{\frac{\kappa
L_{f}}{\mu}}\log\frac{1}{\epsilon})={\cal O}(n\log\frac{1}{\epsilon})$. Part 1
is proved. When $b=\frac{\overline{L}_{f}}{L_{f}}$, the stochastic gradient
computation complexity is ${\cal O}(b\sqrt{\frac{\kappa
L_{f}}{\mu}}\log\frac{1}{\epsilon})={\cal
O}(\sqrt{\frac{\kappa\overline{L}_{f}^{2}}{L_{f}\mu}}\log\frac{1}{\epsilon})$,
and part 2 is proved.

When $b\geq\max\\{\sqrt{\frac{n\overline{L}_{f}}{\kappa
L_{f}}},\sqrt{\frac{n^{2}\mu}{\kappa
L_{f}}},\frac{\overline{L}_{f}}{L_{f}}\\}$, the stochastic gradient
computation complexity is higher than the above ones. But the communication
complexity remains unchanged. This verifies Remark 4(3).

##  5 Numerical Experiments

Consider the following decentralized regularized logistic regression problem:

$\displaystyle\min_{x\in\mathbb{R}^{p}}\sum_{i=1}^{m}f_{(i)}(x),\quad\mbox{where}\quad
f_{(i)}(x)=\frac{\mu}{2}\|x\|^{2}+\frac{1}{n}\sum_{j=1}^{n}\log\left(1+\exp(-y_{(i),j}A_{(i),j}^{T}x)\right),$

where the pairs $(A_{(i),j},y_{(i),j})\in\mathbb{R}^{p}\times\\{1,-1\\}$ are
taken from the RCV1 dataset555https://www.csie.ntu.edu.tw/
cjlin/libsvmtools/datasets/binary.html with $p=47236$, $m=49$, and $n=500$.
Denote $A_{(i)}=[A_{(i),1},A_{(i),2},\cdots,A_{(i),n}]\in\mathbb{R}^{p\times
n}$ as the data matrix on the $i$th node. For this special problem and
dataset, we observe $L_{f}=\max_{i}\frac{\|A_{(i)}\|_{2}^{2}}{4n}+\mu\approx
0.016+\mu$ and
$\overline{L}_{f}=\max_{i}\frac{\|A_{(i)}\|_{F}^{2}}{4n}+\mu=\frac{1}{4}+\mu$,
respectively. We test the performance of the proposed algorithms on different
ratios between $\kappa_{s}$ and $n$. Specifically, we test on $\mu=5\times
10^{-5}$, $\mu=5\times 10^{-6}$, and $\mu=5\times 10^{-7}$, which correspond
to $\kappa_{s}=\frac{\overline{L}_{f}}{\mu}\approx 5\times 10^{3}$,
$\kappa_{s}\approx 5\times 10^{4}$, and $\kappa_{s}\approx 5\times 10^{5}$,
respectively. Note that $n=500$. We also observe
$\frac{n\kappa_{b}}{\kappa_{s}}\approx 31.9$.

We test the performance on two kinds of networks: the Erdős$-$Rényi random
graph and the two-dimensional grid graph, where each pair of nodes has a
connection with the ratio of $0.2$ for the first graph, and $m$ nodes are
placed in the $\sqrt{m}\times\sqrt{m}$ grid and each node is connected with
its neighbors around it for the second graph. Theoretically, $\kappa_{c}={\cal
O}(1)$ for the first graph, and $\kappa_{c}={\cal O}(m\log m)$ for the second
graph. Practically, we observe $\kappa_{c}=4.62$ and $\kappa_{c}=19.9$ for the
two graphs, respectively. We set the weight matrix as
$W=\frac{M-\lambda_{\min}I}{1-\lambda_{\min}}$ for both graphs, where $M$ is
the Metropolis weight matrix (Boyd et al., 2004) with
$M_{ij}=\left\\{\begin{array}[]{ll}\frac{1}{\max\\{d(i),d(j)\\}}&\mbox{if
}(i,j)\in\mathcal{E},\\\ 1-\sum_{l\in\mathcal{N}_{(i)}}M_{il}&\mbox{if
}i=j,\\\ 0&\mbox{if }(i,j)\notin\mathcal{E}\mbox{ and }i\neq
j.\end{array}\right.$, $d(i)$ is the degree of node $i$, and
$\lambda_{\min}<0$ is the smallest negative eigenvalue of $M$.

We compare the proposed VR-EXTRA, Acc-VR-EXTRA, Acc-VR-EXTRA-CA, VR-DIGing,
Acc-VR-DIGing, and Acc-VR-DIGing-CA with EXTRA (Shi et al., 2015), DIGing
(Nedić et al., 2017), GT-SVRG (Xin et al., 2020), APAPC (Koralev et al.,
2020), and accelerated DVR (Acc-DVR) (Hendrikx et al., 2020b). For the case of
$\mu=5\times 10^{-6}$, we choose the best step-sizes $\alpha=\frac{1}{L_{f}}$
for Acc-VR-EXTRA, Acc-VR-EXTRA-CA, Acc-VR-DIGing, and Acc-VR-DIGing-CA,
$\alpha=\frac{3}{L_{f}}$ for VR-EXTRA, VR-DIGing, and GT-SVRG, and
$\alpha=\frac{7}{L_{f}}$ for EXTRA and DIGing. The other parameters are chosen
according to the theories. We set the parameters of APAPC according to Theorem
2 in (Koralev et al., 2020). For Acc-DVR, we follow the suggestions in the
experimental section in (Hendrikx et al., 2020b) to set the number of inner
iterations to $\frac{n}{1-p_{comm}}$ (one pass over the local dataset), and
the batch Lipschitz constant as $L_{f}=0.01\overline{L}_{f}$, which leads to
better performance of Acc-DVR than the theoretical setting of
$L_{f}=\max_{i}\frac{\|A_{(i)}\|_{2}^{2}}{4n}+\mu$. We follow Algorithm 2 and
Theorem 5 in (Hendrikx et al., 2020b) to choose other parameters of Acc-DVR,
that is, $\alpha=\frac{2}{L_{f}\kappa_{c}}$,
$\eta=\min\\{p_{comm}(\beta+\mu),\frac{p_{ij}}{\alpha(1+1/(4n\mu))}\\}$,
$\beta=\frac{\overline{L}_{f}}{n}-\mu$,
$p_{comm}=(1+\frac{n+\kappa_{s}^{\beta}}{\kappa_{b}^{\beta}\kappa_{c}})^{-1}$,
$p_{ij}=\frac{1-p_{comm}}{n}$,
$\kappa_{s}^{\beta}=\frac{\overline{L}_{f}}{\beta+\mu}$, and
$\kappa_{b}^{\beta}=\frac{L_{f}}{\beta+\mu}$666We do not find the parameters
in APAPC and Acc-DVR in the role as step-sizes in the form of ${\cal
O}(\frac{1}{L_{f}})$, thus we set the parameters according to their theories
directly.. For the case of $\mu=5\times 10^{-7}$, we choose the same
parameters as above. For the case of $\mu=5\times 10^{-5}$, we set the step-
sizes $\alpha=\frac{2}{L_{f}}$ for VR-EXTRA, VR-DIGing, and GT-SVRG, and
$\alpha=\frac{3}{L_{f}}$ for EXTRA and DIGing, and other parameters are chosen
the same as above. Specially, since
$\frac{n\kappa_{b}}{\kappa_{s}}<2\kappa_{c}$ and
$\frac{n\kappa_{b}}{\kappa_{s}}<\kappa_{c}^{2}$ for the grid graph, we set the
mini-batch size $b=\frac{\overline{L}_{f}}{L_{f}}$ for Acc-VR-EXTRA and Acc-
VR-DIGing according to Remark 3(1).

|
---|---
|
|
Figure 1: Comparisons on Erdős$-$Rényi random graph with $\mu=5\times 10^{-7}$ (top), $\mu=5\times 10^{-6}$ (middle), and $\mu=5\times 10^{-5}$ (bottom). |
---|---
|
|
Figure 2: Comparisons on grid graph with $\mu=5\times 10^{-7}$ (top),
$\mu=5\times 10^{-6}$ (middle), and $\mu=5\times 10^{-5}$ (bottom).

Figures 1 and 2 plot the results on the Erdős$-$Rényi random graph and grid
graph, respectively, where $f^{*}$ is approximated by the minimum value of the
objective function over all iterations of all the compared algorithms. We have
the following observations:

  1. 1.

VR-EXTRA and VR-DIGing need less gradient computations than EXTRA and DIGing
to reach the same precision for all cases of $\mu$. This verifies the
efficiency of variance reduction in decentralized optimization to reduce the
computation cost.

  2. 2.

When considering the communication cost, VR-EXTRA and VR-DIGing perform worse
than EXTRA and DIGing in practice, although they have the same communication
complexities theoretically. This is reasonable since EXTRA and DIGing go
through all the data at each communication round, while VR-EXTRA and VR-DIGing
only use a mini-batch. We observe the mini-batch size of
$b=\frac{\overline{L}_{f}}{L_{f}}\approx 16$ in our experiment.

  3. 3.

Acc-VR-EXTRA and Acc-VR-DIGing perform better than VR-EXTRA and VR-DIGing on
both computations and communications when $\kappa_{s}$ is much larger than
$n$. For example, $\kappa_{s}=1000n$ in the top plots and $\kappa_{s}=100n$ in
the middle plots. Otherwise, as seen in the bottom plots with
$\kappa_{s}=10n$, Acc-VR-EXTRA and Acc-VR-DIGing perform quite similarly to
VR-EXTRA and VR-DIGing, especially on the computations. This verifies that
acceleration only takes effect to reduce the computation cost when
$\kappa_{s}\gg n$.

  4. 4.

When considering the communication cost, Acc-VR-EXTRA performs similarly to
the optimal full batch method of APAPC. This observation matches the theory
that the two methods have the same communication complexity.

  5. 5.

Acc-VR-EXTRA-CA and Acc-VR-DIGing-CA do not perform well in practice, although
they are theoretically optimal. Thus Acc-VR-EXTRA-CA and Acc-VR-DIGing-CA are
more interesting in theory, but they are not suggested in practice.

##  6 Conclusion

This paper extends the widely used EXTRA and DIGing methods with variance
reduction, and four VR-based stochastic decentralized algorithms are proposed.
The proposed VR-EXTRA has the ${\cal O}((\kappa_{s}+n)\log\frac{1}{\epsilon})$
stochastic gradient computation complexity and the ${\cal
O}((\kappa_{b}+\kappa_{c})\log\frac{1}{\epsilon})$ communication complexity.
The proposed VR-DIGing has a little worse communication complexity of ${\cal
O}((\kappa_{b}+\kappa_{c}^{2})\log\frac{1}{\epsilon})$. Our stochastic
gradient computation complexities keep the same as the single-machine VR
methods such as SVRG, and our communication complexities are the same as those
of EXTRA and DIGing, respectively. The proposed accelerated VR-EXTRA and VR-
DIGing achieve both the optimal ${\cal
O}((\sqrt{n\kappa_{s}}+n)\log\frac{1}{\epsilon})$ stochastic gradient
computation complexity and ${\cal
O}(\sqrt{\kappa_{b}\kappa_{c}}\log\frac{1}{\epsilon})$ communication
complexity. They are also the same as the ones of single-machine accelerated
VR methods such as Katyusha, and the accelerated full batch decentralized
methods such as MSDA, respectively.

## 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.
  * Allen-Zhu (2018) Allen-Zhu, Z.  Katyusha: The first direct acceleration of stochastic gradient methods.  _Journal of Machine Learning Research_ , 18(221):1–51, 2018.
  * 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.
  * Boyd et al. (2004) Boyd, S., Diaconis, P., and Xiao, L.  Fastest mixing markov chain on a graph.  _SIAM Review_ , 46(4):667–689, 2004.
  * Chen & Sayed (2012) Chen, J. and Sayed, A. H.  Diffusion adaptation strategies for distributed optimization and learning over networks.  _IEEE Transactions on Signal Processing_ , 60(8):4289–4305, 2012.
  * Defazio et al. (2014) Defazio, A., Bach, F., and Lacoste-Julien, S.  SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives.  In _Advances in Neural Information Processing Systems (NIPS)_ , pp. 1646–1654, 2014.
  * Fercoq & Richtárik (2015) Fercoq, O. and Richtárik, P.  Accelerated, parallel, and proximal coordinate descent.  _SIAM Journal on Optimization_ , 25(4):1997–2023, 2015.
  * Hendrikx et al. (2020a) Hendrikx, H., Bach, F., and Massoulié, L.  An optimal algorithm for decentralized finite sum optimization.  _preprint arXiv:2005.10675_ , 2020a.
  * Hendrikx et al. (2020b) Hendrikx, H., Bach, F., and Massoulié, L.  Dual-free stochastic decentralized optimization with variance reduction.  _Acceped by Advances in Neural Information Processing Systems (NeurIPS). Preprint arXiv:2006.14384_ , 2020b.
  * 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.
  * Johnson & Zhang (2013) Johnson, R. and Zhang, T.  Accelerating stochastic gradient descent using predictive variance reduction.  In _Advances in Neural Information Processing Systems (NIPS)_ , pp. 315–323, 2013.
  * Koralev et al. (2020) Koralev, D., Salim, A., and Richtárik, P.  Optimal and practical algorithms for smooth and strongly convex decentralized optimization.  _Accepted by Advances in Neural Information Processing Systems (NeurIPS). Preprint arXiv:2006.11773_ , 2020.
  * Kovalev et al. (2020) Kovalev, D., Horváth, S., and Richtárik, P.  Don’t jump through hoops and remove those loops: SVRG and Katyusha are better without the outer loop.  In _International Conference on Algorithmic Learning Theory (ALT)_ , pp. 451–467, 2020.
  * Lan & Zhou (2018) Lan, G. and Zhou, Y.  An optimal randomized incremental gradient method.  _Mathematical Programming_ , 171:167–215, 2018.
  * 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 et al. (2020a) Li, B., Cen, S., Chen, Y., and Chi, Y.  Communication-efficient distributed optimization in networks with gradient tracking and variance reduction.  _Journal of Machine Learning Research_ , 21(180):1–51, 2020a.
  * Li & Lin (2020) Li, H. and Lin, Z.  Revisiting EXTRA for smooth distributed optimization.  _SIAM Journal Optimization_ , 30(3):1795–1821, 2020.
  * Li et al. (2020b) 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, 2020b.
  * Li et al. (2019) Li, Z., Shi, W., and Yan, M.  A decentralized proximal-gradient method with network independent step-sizes and separated convergence rates.  _IEEE Transactions on Signal Processing_ , 67(17):4494–4506, 2019.
  * Lin et al. (2018) Lin, H., Mairal, J., and Harchaoui, Z.  Catalyst acceleration for first-order convex optimization: from theory to practice.  _Journal of Machine Learning Research_ , 18(212):1–54, 2018.