# Decentralized Accelerated Gradient Methods With Increasing Penalty
Parameters

Huan Li, Cong Fang, Wotao Yin, Zhouchen Lin H. Li is sponsored by Zhejiang Lab
(grant no. 2019KB0AB02). Z. Lin is supported by NSF China (grant no.s 61625301
and 61731018), Major Research Project of Zhejiang Lab (grant no.s 2019KB0AC01
and 2019KB0AB02) and Beijing Academy of Artificial Intelligence.H. Li is with
the Institute of Robotics and Automatic Information Systems, College of
Artificial Intelligence, Nankai University, Tianjin, China
(lihuan_ss@126.com), and the the College of Computer Science and Technology,
Nanjing University of Aeronautics and Astronautics, Nanjing, China. This work
was done when Li was a Ph.D student at the Key Lab. of Machine Perception
(MOE), School of EECS, Peking University, Beijing, China.C. Fang is with the
Department of Electrical Engineering, Princeton University, Princeton, New
Jersey, USA (fangcong@pku.edu.cn).W. Yin is with the Department of
Mathematics, University of California, Los Angeles, USA
(wotaoyin@math.ucla.edu).Z. Lin is with the Key Lab. of Machine Perception
(MOE), School of EECS, Peking University, Beijing, China (zlin@pku.edu.cn). Z.
Lin is the corresponding author.This paper has supplementary downloadable
material available at http://ieeexplore.ieee.org., provided by the author. The
material includes some additional experimental results. This material is 2M in
size.

###### Abstract

In this paper, we study the communication and (sub)gradient computation costs
in distributed optimization. We present two algorithms based on the framework
of the accelerated penalty method with increasing penalty parameters. Our
first algorithm is for smooth distributed optimization and it obtains the near
optimal $O(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon})$
communication complexity and the optimal $O(\sqrt{\frac{L}{\epsilon}})$
gradient computation complexity for $L$-smooth convex problems, where
$\sigma_{2}(W)$ denotes the second largest singular value of the weight matrix
$W$ associated to the network and $\epsilon$ is the target accuracy. When the
problem is $\mu$-strongly convex and $L$-smooth, our algorithm has the near
optimal $O(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log^{2}\frac{1}{\epsilon})$
complexity for communications and the optimal
$O(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon})$ complexity for gradient
computations. Our communication complexities are only worse by a factor of
$(\log\frac{1}{\epsilon})$ than the lower bounds. Our second algorithm is
designed for nonsmooth distributed optimization and it achieves both the
optimal $O(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}})$ communication complexity
and $O(\frac{1}{\epsilon^{2}})$ subgradient computation complexity, which
match the lower bounds for nonsmooth distributed optimization.

###### Index Terms:

Distributed accelerated gradient algorithms, accelerated penalty method,
optimal (sub)gradient computation complexity, near optimal communication
complexity.

##  I Introduction

In this paper, we consider the following distributed convex optimization
problem:

$\displaystyle\min_{x\in\mathbb{R}^{n}}\frac{1}{m}\sum_{i=1}^{m}F_{i}(x)\equiv
f_{i}(x)+h_{i}(x),$ (1)

where $m$ agents form a connected and undirected network
$\mathcal{G}=(\mathcal{V},\mathcal{E})$, $\mathcal{V}=\\{1,2,...,m\\}$ is the
set of agents and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the set
of edges, $F_{i}$ is the local objective function only available to agent $i$
and $x$ is the decision variable. $f_{i}$ is a convex and smooth function
while $h_{i}$ is a convex but possibly nonsmooth one. We consider distributed
algorithms using only local computations and communications, i.e., each agent
$i$ makes its decision only based on the local computations on $F_{i}$ (i.e.,
the gradient of $f_{i}$ and the subgradient of $h_{i}$) and the local
information received from its neighbors in the network. A pair of agents can
exchange information if and only if they are directly connected in the
network. Distributed computation has been widely used in signal processing
[1], automatic control [2, 3] and machine learning [4, 5, 6].

###  I-A Literature Review

Non-strongly convex and smooth case
---
Methods | Complexity of gradient computations | Complexity of communications
DNGD111The authors of [7] did not give the dependence on $1-\sigma_{2}(W)$. It does not mean that their complexity has no dependence on $1-\sigma_{2}(W)$. |  $O\left(\frac{1}{\epsilon^{5/7}}\right)$ [7] |  $O\left(\frac{1}{\epsilon^{5/7}}\right)$ [7]
DN-C |  $O\left({\sqrt{\frac{L}{\epsilon}}}\right)$ [8] |  $O\left(\sqrt{\frac{L}{\epsilon}}\frac{1}{1-\sigma_{2}(W)}\log\frac{1}{\epsilon}\right)$ [8]
Accelerated Dual Ascent |  $O\left(\frac{L}{\epsilon\sqrt{1-\sigma_{2}(W)}}\log^{2}\frac{1}{\epsilon}\right)$ [9] |  $O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right)$ [9]
Our APM-C | $O\left({\sqrt{\frac{L}{\epsilon}}}\right)$ | $O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right)$
Lower Bound |  $O\left({\sqrt{\frac{L}{\epsilon}}}\right)$ [10] |  $O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\right)$[11]
Strongly convex and smooth case
Methods | Complexity of gradient computations | Complexity of communications
DNGD |  $O\left(\big{(}\frac{L}{\mu}\big{)}^{5/7}\frac{1}{(1-\sigma_{2}(W))^{1.5}}\log\frac{1}{\epsilon}\right)$ [7] |  $O\left(\big{(}\frac{L}{\mu}\big{)}^{5/7}\frac{1}{(1-\sigma_{2}(W))^{1.5}}\log\frac{1}{\epsilon}\right)$ [7]
Accelerated Dual Ascent |  $O\left(\frac{L}{\mu\sqrt{1-\sigma_{2}(W)}}\log^{2}\frac{1}{\epsilon}\right)$ 33footnotemark: 3 [9] |  $O\left(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right)$ [12, 9]
Our APM-C | $O\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ | $O\left(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log^{2}\frac{1}{\epsilon}\right)$
Lower Bound |  $O\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$ [10] |  $O\left(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right)$ [12]
Convex and Nonsmooth case
Methods | Complexity of subgradient computations | Complexity of communications
Primal-dual method |  $O\left(\frac{1}{\epsilon^{2}}\right)$ [11] |  $O\left(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$ [11]
Smoothed accelerated gradient sliding method |  $O\left(\frac{1}{\epsilon^{2}}\right)$ [9] |  $O\left(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$ [9]
Our APM | $O\left(\frac{1}{\epsilon^{2}}\right)$ | $O\left(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$
Lower Bound |  $O\left(\frac{1}{\epsilon^{2}}\right)$ [13] |  $O\left(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$ [13]
TABLE I: Complexity comparisons between accelerated dual ascent, DN-C, DNGD,
the primal-dual method and our methods (APM-C,APM) for distributed convex
problems.

Among the classical distributed first-order algorithms, two different types of
methods have been proposed, namely, the primal-only methods and the dual-based
methods.

The distributed subgradient method is a representative primal-only distributed
optimization algorithm over general networks [14], while its stochastic
version was studied in [15], and asynchronous variant in [16]. In the
distributed subgradient method, each agent performs a consensus step and then
follows a subgradient descent with a diminishing step-size. To avoid the
diminishing step-size, three different types of methods have been proposed.
The first type of methods [17, 18, 19, 7] rely on tracking differences of
gradients, which keep a variable to estimate the average gradient and use this
estimation in the gradient descent step. The second type of methods, called
EXTRA [20, 21], introduce two different weight matrices as opposed to a single
one with the standard distributed gradient method [14]. EXTRA also uses the
gradient tracking. The third type of methods employ a multi-consensus inner
loop [8, 22] and thus improve the consensus of the variables at each outer
iteration.

The dual-based methods introduce the Lagrangian function and work in the dual
space. Many classical methods can be used to solve the dual problem, e.g., the
dual subgradient ascent [23], dual gradient ascent [24], accelerated dual
gradient ascent [12, 9], the primal-dual method [25, 13], and ADMM [26, 27,
28, 29, 30, 31]. In general, most dual-based methods require the evaluation of
the Fenchel conjugate of the local objective function $f_{i}(x)$ and thus have
a larger gradient computation cost per iteration than the primal-only
algorithms for smooth distributed optimization. For nonsmooth problems, the
authors of [25, 13, 11] studied the communication-efficient primal-dual
method. Specifically, they use the classical primal-dual method [32] in the
outer loop and the subgradient method in the inner loop. The authors of [13]
used Chebyshev acceleration [33] to further reduce the computation complexity
while the authors of [11] did it via carefully setting the parameters.

Among the methods described above, the distributed Nesterov gradient with
consensus iterations (D-NC) proposed in [8] and the distributed Nesterov
gradient descent (DNGD) proposed in [7] employ Nesterov’s acceleration
technique in the primal space, and the accelerated dual ascent proposed in
[12] use the standard accelerated gradient descent in the dual space.
Moreover, D-NC attains the optimal gradient computation complexity for
nonstrongly convex and smooth problems, and the accelerated dual ascent
achieves the optimal communication complexity for strongly convex and smooth
problems, which match the complexity lower bounds [10, 12]. For nonsmooth
problems, the primal-dual method proposed in [13, 11] and the smoothed
accelerated gradient sliding method in [9] achieve both the optimal
communication and subgradient computation complexities, which also match the
lower bounds [13]. We denote the communication and computation complexities as
the numbers of communications and (sub)gradient computations to find an
$\epsilon$-optimal solution $x$ such that
$\frac{1}{m}\sum_{i=1}^{m}F_{i}(x)-\min_{x}\frac{1}{m}\sum_{i=1}^{m}F_{i}(x)\leq\epsilon$,
respectively.

###  I-B Contributions

In this paper, we study the decentralized accelerated gradient methods with
near optimal complexities from the perspective of the accelerated penalty
method. Specifically, we propose an _A_ ccelerated _P_ enalty _M_ ethod with
increasing penalties for smooth distributed optimization by employing a multi-
_C_ onsensus inner loop (APM-C). The theoretical significance of our method is
that we show the near optimal communication complexities and the optimal
gradient computation complexities for both strongly convex and nonstrongly
convex problems. Our communication complexities are only worse by a logarithm
factor than the lower bounds.

Table I summarizes the complexity comparisons to the state-of-the-art
distributed optimization algorithms (the notations in Table I will be
specified precisely soon), namely, DNGD, D-NC, and the accelerated dual ascent
reviewed above, as well as the complexity lower bounds. Our complexities match
the lower bounds except that the communication ones have an extra factor of
$\log\frac{1}{\epsilon}$. The communication complexity of the accelerated dual
ascent matches ours for nonstrongly convex problems and is optimal for
strongly convex problems (thus better than ours by $\log\frac{1}{\epsilon}$).
On the other hand, our gradient computation complexities match the lower
bounds and they are better than the compared methods. It should be noted that
due to term $\log^{2}\frac{1}{\epsilon}$, our communication complexity for
strongly convex problems is not a linear convergence rate.

Our framework of accelerated penalty method with increasing penalties also
applies to nonsmooth distributed optimization. It drops the multi-consensus
inner loop but employs an inner loop with several runs of subgradient method.
Both the optimal communication and subgradient computation complexities are
achieved, which match the lower bounds for nonsmooth distributed optimization.
Although the theoretical complexities are the same with the methods [11, 9],
our method gives the users a new choice in practice.

###  I-C Notations and Assumptions

Throughout the paper, the variable $x\in\mathbb{R}^{n}$ is the decision
variable of the original problem (1). We denote $x_{(i)}\in\mathbb{R}^{n}$ to
be the local estimate of the variable $x$ for agent $i$. To simplify the
algorithm description in a compact form, we introduce the aggregate variable
$\mathbf{x}$, aggregate objective function $f(\mathbf{x})$ and aggregate
gradient $\nabla f(\mathbf{x})$ as

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

where $\mathbf{x}\in\mathbb{R}^{m\times n}$, whose value at iteration $k$ is
denoted by $\mathbf{x}^{k}$. For the double loop algorithms, we denote
$\mathbf{x}^{k,t}$ as its value at the $k$th outer iteration and $t$th inner
iteration. Assume that the set of minimizers is non-empty. Denote $x^{*}$ as
one minimizer of problem (1), and let
$\mathbf{x}^{*}=\mathbf{1}(x^{*})^{T}\in\mathbb{R}^{m\times n}$, where
$\mathbf{1}=(1,1,\cdots,1)^{T}\in\mathbb{R}^{m}$ is the vector with all ones.
Denote $\partial h_{i}(x)$ as the subdifferential of $h_{i}(x)$ at $x$, and
specifically, $\hat{\nabla}h_{i}(x)\in\partial h_{i}(x)$ as its one
subgradient. For $h_{i}$, we introduce its aggregate objective function
$h(\mathbf{x})$ and aggregate subgradient $\hat{\nabla}h(\mathbf{x})$ as

$h(\mathbf{x})=\sum_{i=1}^{m}h_{i}(x_{(i)})\quad\mbox{and}\quad\hat{\nabla}h(\mathbf{x})=\left(\begin{array}[]{c}\hat{\nabla}h_{1}(x_{(1)})^{T}\\\
\vdots\\\ \hat{\nabla}h_{m}(x_{(m)})^{T}\end{array}\right).$

We use $\|\cdot\|$ and $\|\cdot\|_{1}$ as the $l_{2}$ Euclidean norm and
$l_{1}$ norm for a vector, respectively. For matrices $\mathbf{x}$ and
$\mathbf{y}$, we denote $\|\mathbf{x}\|_{F}$ as the Frobenius norm,
$\|\mathbf{x}\|_{2}$ as the spectral norm and
$\left\langle\mathbf{x},\mathbf{y}\right\rangle=\mbox{trace}(\mathbf{x}^{T}\mathbf{y})$
as their inner product. Denote $I\in\mathbb{R}^{m\times m}$ as the identity
matrix and $\mathcal{N}_{i}$ as the neighborhood of agent $i$ in the network.
Define

$\displaystyle\alpha(\mathbf{x})=\frac{1}{m}\sum_{i=1}^{m}x_{(i)}$ (2)

as the average across the rows of $\mathbf{x}$. Define two operators

$\displaystyle\Pi=I-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\quad\mbox{ and }\quad
U=\sqrt{I-W}$ (3)

to measure the consensus violation, where $W$ is the weight matrix associated
to the network, which describes the information exchange through the network.
Especially, $\|\Pi\mathbf{x}\|_{F}$ directly measures the distance between
$x_{(i)}$ and $\alpha(\mathbf{x})$. We follow [12] to define
$\sqrt{A}=V\sqrt{\Lambda}V^{T}$, given the eigenvalue decomposition
$A=V\Lambda V^{T}$ of the symmetric positive semidefinite matrix $A$.

We make the following assumptions for each function $f_{i}(x)$.

###### Assumption 1

  1. 1.

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

  2. 2.

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

In Assumption 1, $\mu$ and $L$ are the strong-convexity constant and
smoothness constant, respectively. Assumption 1 yields that the aggregate
function $f(\mathbf{x})$ is also $\mu$-strongly convex and $L$-smooth. For the
nonsmooth function $h_{i}(x)$, we follow [25] to make the following
assumptions.

###### Assumption 2

  1. 1.

$h_{i}(x)$ is convex.

  2. 2.

$h_{i}(x)$ is $M$-Lipschitz continuous: $h_{i}(y)\leq
h_{i}(x)+\left\langle\hat{\nabla}h_{i}(x),y-x\right\rangle+M\|y-x\|$.

We can simply verify that $h(\mathbf{x})$ is $(\sqrt{m}M)$-Lipschitz
continuous. For the weight matrix $W$, we make the following assumptions.

###### Assumption 3

  1. 1.

$W\in\mathbb{R}^{m\times m}$ is a symmetric matrix with $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.

$I\succeq W\succeq 0$, and $W\mathbf{1}=\mathbf{1}$.

Examples satisfying Assumption 3 can be found in [20]. We denote by
$1=\sigma_{1}(W)\geq\sigma_{2}(W)\geq\cdots\geq\sigma_{m}(W)$ the spectrum of
$W$. Note that for a connected and undirected network, we always have
$\sigma_{2}(W)<1$, and $\frac{1}{1-\sigma_{2}(W)}$ is a good indication of the
network connectivity. For many commonly used networks, we can give order-
accurate estimate on $\frac{1}{1-\sigma_{2}(W)}$ [34, Proposition 5]. For
example, $\frac{1}{1-\sigma_{2}(W)}=O(m\log m)$ for the geometric graph, and
$\frac{1}{1-\sigma_{2}(W)}=O(1)$ for the expander graph and Erdős$-$Rényi
random graph. Moreover, for any connected and undirected graph,
$\frac{1}{1-\sigma_{2}(W)}=O(m^{2})$ in the worst case [34].

In this paper, we focus on the communication and (sub)gradient computation
complexity development for the proposed algorithms. We define one
communication to be the operation that all the agents exchange information
with their neighbors once, i.e., $\sum_{j\in\mathcal{N}_{i}}W_{ij}x_{(j)}$ for
all $i=1,2,...,m$. One (sub)gradient computation is defined to be the
(sub)gradient evaluations of all the agents once, i.e., $\nabla
f_{i}(x_{(i)})$ ($\hat{\nabla}h_{i}(x_{(i)})$) for all $i$.

##  II Development of the Accelerated Penalty Method

###  II-A Accelerated Penalty Method for Smooth Distributed Optimization

In this section, we consider the smooth distributed optimization, i.e.,
$h_{i}(x)=0$ in problem (1). From the definition of $\Pi$ in (3), we know that
$x_{(1)}=\cdots=x_{(m)}$ is equivalent to $\Pi\mathbf{x}=0$. Thus, we can
reformulate the smooth distributed problem as

$\displaystyle\begin{aligned} \min_{\mathbf{x}\in\mathbb{R}^{m\times
n}}f(\mathbf{x})\quad\mbox{s.t.}\quad\Pi\mathbf{x}=0.\end{aligned}$ (4)

Problem (4) is a standard linearly constrained convex problem, and many
algorithms can be used to solve it, e.g., the primal-dual method [25, 13, 35,
36] and dual ascent [23, 12, 9]. In order to propose an accelerated
distributed gradient method based on the gradient of $f(\mathbf{x})$, rather
than the evaluation of its Fenchel conjugate or proximal mapping, we follow
[37] to use the penalty method to solve problem (4) in this paper.
Specifically, the penalty method solves the following problem instead:

$\displaystyle\min_{\mathbf{x}\in\mathbb{R}^{m\times
n}}f(\mathbf{x})+\frac{\beta}{2}\|\Pi\mathbf{x}\|_{F}^{2},$ (5)

where $\beta$ is a large constant. However, one big issue of the penalty
method is that problems (4) and (5) are not equivalent for finite $\beta$.
When solving problem (5), we can only obtain an approximate solution of (4)
with small $\|\Pi\mathbf{x}\|_{F}$, rather than
$\|\Pi\mathbf{x}\|_{F}\rightarrow 0$, and the algorithm only converges to a
neighborhood of the solution set of problem (1) [37]. Moreover, to find an
$\epsilon$-optimal solution of (4), we need to pre-define a large $\beta$ of
the order $\frac{1}{\epsilon}$ [37]. Thus, the parameter setting depends on
the precision $\epsilon$. When $\beta$ is fixed as a constant of the order
$\frac{1}{\epsilon}$, we can only get the $\epsilon$-accurate solution after
some fixed iterations described by $\epsilon$, and more iterations will not
give a more accurate solution. Please see Section II-C1 for more details. To
solve the above two problems, we use the gradually increasing penalty
parameters, i.e., at the $k$th iteration, we use
$\beta=\frac{\beta_{0}}{\vartheta_{k}}$ with fixed $\beta_{0}$ and diminishing
$\vartheta_{k}\rightarrow 0$. The increasing penalty strategy has two
advantages: 1) The solution of (5) approximates that of (4) infinitely when
the iteration number $k$ is sufficiently large. 2) The parameter setting does
not depend on the accuracy $\epsilon$. The algorithm can be run without
defining the accuracy $\epsilon$ in advance. It can reach arbitrary accuracy
if run for arbitrarily long time.

We use the classical accelerated proximal gradient method (APG) [38] to
minimize the penalized objective in (5), i.e., at the $k$th iteration, we
first compute the gradient of $f(\mathbf{x})$ at some extrapolated point, and
then compute the proximal mapping of
$\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}\|_{F}^{2}$ at some
$\mathbf{z}$, defined as

$\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{m\times
n}}\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}\|_{F}^{2}+\frac{L}{2}\|\mathbf{x}-\mathbf{z}\|_{F}^{2}.$
(6)

Due to the special form of $\Pi$ defined in (3), a simple calculation yields
$\frac{L\vartheta_{k}\mathbf{z}+\beta_{0}\mathbf{1}\alpha(\mathbf{z})^{T}}{L\vartheta_{k}+\beta_{0}}$
as the solution of (6), where $\alpha(\mathbf{x})$ is defined in (2). However,
in the distributed setting, we can only compute $\alpha(\mathbf{z})$
approximately in finite communications. Thus, we use the inexact APG to
minimize (5), i.e., we compute the proximal mapping inexactly. Specifically,
the algorithm framework consists of the following steps:

$\displaystyle\mathbf{y}^{k}=\mathbf{x}^{k}+\frac{L\theta_{k}-\mu}{L-\mu}\frac{1-\theta_{k-1}}{\theta_{k-1}}(\mathbf{x}^{k}-\mathbf{x}^{k-1}),$
(7a) $\displaystyle\mathbf{z}^{k}=\mathbf{y}^{k}-\frac{1}{L}\nabla
f(\mathbf{y}^{k}),$ (7b)
$\displaystyle\mathbf{x}^{k+1}\approx\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{m\times
n}}\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}\|_{F}^{2}+\frac{L}{2}\left\|\mathbf{x}-\mathbf{z}^{k}\right\|_{F}^{2},$
(7c)

where the sequences $\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ and the
precision in step (7c) will be specified in Theorems 1 and 2 latter. Now, we
consider the subproblem in procedure (7c). As discussed above, we only need to
approximate $\alpha(\mathbf{z}^{k})$, which can be obtained by the classical
average consensus [39] or the accelerated average consensus [40]. We only
consider the accelerated average consensus, which consists of the following
iterations:

$\mathbf{z}^{k,t+1}=(1+\eta)W\mathbf{z}^{k,t}-\eta\mathbf{z}^{k,t-1},$ (8)

where we initialize at $\mathbf{z}^{k,0}=\mathbf{z}^{k,-1}=\mathbf{z}^{k}$.
The advantage of using the special $\Pi$ in (4) is that we only need to call
the classic average consensus to solve the subproblem in (7c), which has been
well studied in the literatures, including the extensions over directed
network and time-varying network [41]. In fact, in Lemma 6, we only require
$\|\mathbf{z}^{k,T_{k}}-\mathbf{1}\alpha(\mathbf{z}^{k})\|_{F}^{2}$ to be
within some precision for the method used in the inner loop. Any average
consensus method over undirected graph, directed graph or time-varying graph
can be used in the inner loop, as long as it has a linear convergence.

Combing (7a)-(7c) and (8), we can give our method, which is presented in a
distributed way in Algorithm 1. We use notations $\mathbf{x}^{-1}$ and
$\mathbf{z}^{k,-1}$ in Algorithm 1 only for the writing consistency when
beginning the recursions from $k=0$ and $t=0$.

Algorithm 1 Accelerated Penalty Method with Consensus (APM-C)

Initialize $x_{(i)}^{0}=x_{(i)}^{-1}$ for all $i$, and
$\eta=\frac{1-\sqrt{1-\sigma_{2}^{2}(W)}}{1+\sqrt{1-\sigma_{2}^{2}(W)}}$.

for $k=0,1,2,\cdots$ do

$y_{(i)}^{k}=x_{(i)}^{k}+\frac{L\theta_{k}-\mu}{L-\mu}\frac{1-\theta_{k-1}}{\theta_{k-1}}\left(x_{(i)}^{k}-x_{(i)}^{k-1}\right)\quad\forall
i,$

$z_{(i)}^{k}=y_{(i)}^{k}-\frac{1}{L}\nabla f_{i}(y_{(i)}^{k})\quad\forall i,$

$z_{(i)}^{k,0}=z_{(i)}^{k,-1}=z_{(i)}^{k}\quad\forall i,$

for $t=0,1,\cdots,T_{k}-1$ do

$z_{(i)}^{k,t+1}=(1+\eta)\sum_{j\in\mathcal{N}_{i}}W_{ij}z_{(j)}^{k,t}-\eta
z_{(i)}^{k,t-1}\quad\forall i,$

end for

$x_{(i)}^{k+1}=\frac{L\vartheta_{k}z_{(i)}^{k}+\beta_{0}z_{(i)}^{k,T_{k}}}{L\vartheta_{k}+\beta_{0}}\quad\forall
i.$

end for

####  II-A1 Complexities

In this section, we discuss the complexities of Algorithm 1. We first consider
the strongly convex case and give the complexities in the following theorem.

###### Theorem 1

Assume that Assumptions 1 and 3 hold with $\mu>0$. Setting
$\theta_{k}=\theta=\sqrt{\frac{\mu}{L}}$ for all $\forall k$,
$\vartheta_{k}=(1-\theta)^{k+1}$, and
$T_{k}=O\left(\frac{k\sqrt{\mu/L}}{\sqrt{1-\sigma_{2}(W)}}\right)$. Then,
Algorithm 1 needs $O\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$
gradient computations and
$O\left(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log^{2}\frac{1}{\epsilon}\right)$
total communications to achieve an $\epsilon$-optimal solution $\mathbf{x}$
such that

$\displaystyle\begin{aligned}
&\frac{1}{m}\sum_{i=1}^{m}f_{i}(\alpha(\mathbf{x}))-\frac{1}{m}\sum_{i=1}^{m}f_{i}(x^{*})\leq\epsilon\\\
&\qquad\frac{1}{m}\sum_{i=1}^{m}\left\|x_{(i)}-\alpha(\mathbf{x})\right\|^{2}\leq\epsilon^{2}.\end{aligned}$
(9)

When we drop the strong-convexity assumption, we have the following theorem.

###### Theorem 2

Assume that Assumptions 1 and 3 hold with $\mu=0$. Let sequences
$\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy $\theta_{0}=1$,
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$, and
$\vartheta_{k}=\theta_{k}^{2}$. Setting $T_{k}=O\left(\frac{\log
k}{\sqrt{1-\sigma_{2}(W)}}\right)$ and $\beta_{0}\geq L\|\nabla
f(\mathbf{x}^{*})\|_{F}^{2}$. Then, Algorithm 1 needs
$O\left(\sqrt{\frac{L}{\epsilon}}\right)$ gradient computations and
$O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right)$
total communications to achieve an $\epsilon$-optimal solution $\mathbf{x}$
such that (LABEL:cont14) holds.

###  II-B Accelerated Penalty Method for Nonsmooth Distributed Optimization

In this section, we consider the nonsmooth problem (1). From Assumption 3 and
the definition in (3), we know $I\succeq U\succeq 0$, and
$x_{(1)}=\cdots=x_{(m)}$ is equivalent to $U\mathbf{x}=0$ [12]. Thus, similar
to (4), we can reformulate problem (1) as

$\displaystyle\begin{aligned} \min_{\mathbf{x}\in\mathbb{R}^{m\times
n}}F(\mathbf{x})\equiv f(\mathbf{x})+h(\mathbf{x})\quad\mbox{s.t.}\quad
U\mathbf{x}=0.\end{aligned}$ (10)

Similar to Section II-A, we also further rewrite the problem as a penalized
problem and use APG with increasing penalties to minimize the penalized
objective
$F(\mathbf{x})+\frac{\beta_{0}}{2\vartheta_{k}}\|U\mathbf{x}\|_{F}^{2}$.
However, due to the nonsmooth term $h(\mathbf{x})$, we cannot compute the
proximal mapping of
$h(\mathbf{x})+\frac{\beta_{0}}{2\vartheta_{k}}\|U\mathbf{x}\|_{F}^{2}$
efficiently. Thus, we use a slightly different strategy here. Specifically, we
first compute the gradient of
$f(\mathbf{x})+\frac{\beta_{0}}{2\vartheta_{k}}\|U\mathbf{x}\|_{F}^{2}$ at
some extrapolated point $\mathbf{y}$, i.e., $\nabla
f(\mathbf{y})+\frac{\beta_{0}}{\vartheta_{k}}U^{2}\mathbf{y}$, and then
compute the inexact proximal mapping of $h(\mathbf{x})$. We describe the
iterations as follows:

$\displaystyle\mathbf{y}^{k}=\mathbf{x}^{k}+\frac{\theta_{k}(1-\theta_{k-1})}{\theta_{k-1}}(\mathbf{x}^{k}-\mathbf{x}^{k-1}),$
(11a) $\displaystyle\mathbf{s}^{k}=\nabla
f(\mathbf{y}^{k})+\frac{\beta_{0}}{\vartheta_{k}}U^{2}\mathbf{y}^{k},$ (11b)
$\displaystyle\mathbf{x}^{k+1}\approx\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{m\times
n}}h(\mathbf{x})+\left\langle\mathbf{s}^{k},\mathbf{x}\right\rangle+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\|\mathbf{x}-\mathbf{y}^{k}\|_{F}^{2}.$
(11c)

The reason why we use $U$ in (10), rather than $\Pi$, is that
$U^{2}\mathbf{y}^{k}$ can be efficiently computed, which corresponds to the
gossip-style communications. Otherwise, we need to compute the average across
$y^{k}_{(1)},...,y^{k}_{(m)}$, which cannot be achieved with closed form
solution in the distributed environment.

When the proximal mapping of $h(\mathbf{x})$, i.e.,
$\mbox{Prox}_{h}(\mathbf{z})=\operatorname*{argmin}_{\mathbf{x}\in\mathbb{R}^{m\times
n}}h(\mathbf{x})+\frac{1}{2}\|\mathbf{x}-\mathbf{z}\|^{2}$ for some
$\mathbf{z}$, has closed form solution or can be easily computed, step (11c)
has a low computation cost, which reduces to

$\displaystyle\begin{aligned}
\mathbf{x}^{k+1}=\mbox{Prox}_{h}\left(\mathbf{y}^{k}-\frac{1}{L+\beta_{0}/\vartheta_{k}}\left(\nabla
f(\mathbf{y}^{k})+\frac{\beta_{0}}{\vartheta_{k}}U^{2}\mathbf{y}^{k}\right)\right).\end{aligned}$
(12)

We can see that when we set a large penalty parameter $\beta$, i.e., exchange
$\frac{\beta_{0}}{\vartheta_{k}}$ with a large $\beta$ such that $\beta\gg L$
in (12), (12) approximately reduces to
$\mathbf{x}^{k+1}\approx\mbox{Prox}_{h}\left(\mathbf{y}^{k}-U^{2}\mathbf{y}^{k}\right)$
and $\nabla f(\mathbf{y}^{k})$ is flooded by the large penalty parameters.
This is another reason to use the increasing penalty parameters.

When the proximal mapping of $h(\mathbf{x})$ does not have a closed form
solution, we borrow the idea of gradient and communication sliding proposed in
[42, 43, 44, 25], which skips the computations of $\nabla f$ and the inter-
node communications from time to time so that only $O(1/\epsilon)$ gradient
evaluations and communications are needed in the $O(1/\epsilon^{2})$
iterations required to solve problem (10). Specifically, we incorporate a
subgradient descent procedure to solve the subproblem in (11c) with a sliding
period $T_{k}$, which is also adopted by [13]. The subgradient descent is
described as follows for $T_{k}$ iterations:

$\displaystyle\begin{aligned}
\mathbf{z}^{k,t+1}=\operatorname*{argmin}_{\mathbf{z}\in\mathbb{R}^{m\times
n}}&\left\langle\hat{\nabla}h(\mathbf{z}^{k,t}),\mathbf{z}\right\rangle+\left\langle\mathbf{s}^{k},\mathbf{z}\right\rangle\\\
&+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\|\mathbf{z}-\mathbf{y}^{k}\|_{F}^{2}+\frac{1}{2\eta_{k}}\|\mathbf{z}-\mathbf{z}^{k,t}\|_{F}^{2}.\end{aligned}$

We describe the method in a distributed way in Algorithm 2.

Algorithm 2 Accelerated Penalty Method (APM)

Initialize $x_{(i)}^{0}=x_{(i)}^{-1}$, and $z_{(i)}^{-1,T_{-1}}=x_{(i)}^{0}$
for all $i$.

for $k=0,1,2,\cdots,K$ do

$y_{(i)}^{k}=x_{(i)}^{k}+\frac{\theta_{k}(1-\theta_{k-1})}{\theta_{k-1}}(x_{(i)}^{k}-x_{(i)}^{k-1})\quad\forall
i,$

$\mathbf{s}_{(i)}^{k}=\nabla
f_{i}(y_{(i)}^{k})+\frac{\beta_{0}}{\vartheta_{k}}\left(y_{(i)}^{k}-\sum_{j=1}^{m}W_{i,j}y_{(j)}^{k}\right)\quad\forall
i,$

$z_{(i)}^{k,0}=z_{(i)}^{k-1,T_{k-1}}\quad\forall i$,

for $t=0,1,\cdots,T_{k}-1$ do

$z_{(i)}^{k,t+1}=\operatorname*{argmin}_{z\in\mathbb{R}^{n}}\left\langle\hat{\nabla}h_{i}(z_{(i)}^{k,t})+\mathbf{s}_{(i)}^{k},z\right\rangle$

$\hskip
28.45274pt+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\|z-y_{(i)}^{k}\|^{2}+\frac{1}{2\eta_{k}}\|z-z_{(i)}^{k,t}\|^{2}\quad\forall
i.$

end for

$x_{(i)}^{k+1}=\frac{\sum_{t=0}^{T_{k}-1}z_{(i)}^{k,t+1}}{T_{k}}\quad\forall
i$.

end for

####  II-B1 Complexities

Introduce constants $R_{1}$ and $R_{2}$ such that

$\|x_{(i)}^{0}-x^{*}\|^{2}\leq R_{1}^{2}\quad\mbox{and}\quad\|\nabla
f_{i}(x^{*})\|^{2}\leq R_{2}^{2}\quad\mbox{for all }i,$ (13)

and assume $R_{1}\geq 1$ for simplicity. Then, we describe the convergence
rate for Algorithm 2 in the following theorem.

###### Theorem 3

Assume that Assumptions 1, 2 and 3 hold with $\mu=0$. Let sequences
$\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy $\theta_{0}=1$,
$\frac{1-\theta_{k}}{\theta_{k}}=\frac{1}{\theta_{k-1}}$, and
$\vartheta_{k}=\theta_{k}$. Set $T_{k}=K(1-\sigma_{2}(W))$,
$\eta_{k}=\frac{\theta_{k}}{KM\sqrt{1-\sigma_{2}(W)}}$, and
$\beta_{0}=\frac{\max\left\\{M,L\right\\}}{\sqrt{1-\sigma_{2}(W)}}$, where $K$
is the number of outer iterations. Then, for Algorithm 2, we have

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}F_{i}\left(\alpha(\mathbf{x}^{K})\right)-\frac{1}{m}\sum_{i=1}^{m}F_{i}(x^{*})$
$\displaystyle\leq$
$\displaystyle\frac{\beta_{0}}{K}\left(31+\frac{8}{K\sqrt{1-\sigma_{2}(W)}}\right)\left(R_{1}+\frac{R_{2}}{L}\right)^{2},$

and

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\left\|x_{(i)}^{K}-\alpha(\mathbf{x}^{K})\right\|^{2}\leq\frac{16\beta_{0}^{2}}{K^{2}M^{2}}\left(R_{1}+\frac{R_{2}}{L}\right)^{2}.$

Consider the simple problem of computing the average of
$x_{(1)},\cdots,x_{(m)}$. The accelerated averaged consensus [40] needs
$O\left(\frac{1}{\sqrt{1-\sigma_{2}(W)}}\log\frac{1}{\epsilon}\right)$
iterations to find an $\epsilon$-accurate solution. Thus, it is reasonable to
assume $K\geq\frac{1}{\sqrt{1-\sigma_{2}(W)}}$. Moreover, from the
$L$-smoothness of $f_{i}(x)$, we know $R_{2}$ is often of the order
$O(LR_{1})$. Thus, Theorem 3 establishes the
$O\left(\frac{\max\\{M,L\\}}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$
communication complexity and the
$\sum_{k=1}^{K}T_{k}=K^{2}(1-\sigma_{2}(W))=O\left(\frac{\max\\{M,L\\}^{2}}{\epsilon^{2}}\right)$
subgradient computation complexity such that (LABEL:cont14) holds for
nonsmooth distributed optimization.

In Theorem 3, we set $T_{k}$ and $\eta_{k}$ dependent on the number of outer
iterations. As explained in Section II-A, it is a unpractical parameter
setting and moreover, the large $T_{k}$ and $\frac{1}{\eta_{k}}$ make the
algorithm slow in practice. In the following corollary, we give a more
reasonable setting of the parameters at an expense of higher complexities by
the order of $\log\frac{1}{\epsilon}$, i.e., $\log K$.

###### Corollary 1

Under the settings in Theorem 3 but with
$T_{k}=\frac{1-\sigma_{2}(W)}{\theta_{k}}$ and
$\eta_{k}=\frac{\theta_{k}^{2}}{M\sqrt{1-\sigma_{2}(W)}}$, we have

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}F_{i}\left(\alpha(\mathbf{x}^{K})\right)-\frac{1}{m}\sum_{i=1}^{m}F_{i}(x^{*})$
$\displaystyle\leq$ $\displaystyle\frac{\beta_{0}\log
K}{K}\left(31+\frac{8}{K\sqrt{1-\sigma_{2}(W)}}\right)\left(R_{1}+\frac{R_{2}}{L}\right)^{2},$

and

$\displaystyle\frac{1}{m}\sum_{i=1}^{m}\left\|x_{(i)}^{K}-\alpha(\mathbf{x}^{K})\right\|^{2}\leq\frac{16\beta_{0}^{2}\log
K}{K^{2}M^{2}}\left(R_{1}+\frac{R_{2}}{L}\right)^{2}.$

When $f(\mathbf{x})$ is strongly convex, we can prove a faster
$O\left(\frac{1}{k^{2}}\right)$ convergence rate for Algorithm 2 with
$\theta_{k}=\frac{2}{k+2}$ and $\vartheta_{k}=\theta_{k}^{2}$. However, the
quickly diminishing step-size in step (11c) makes the algorithm slow in
practice. So we omit the discussion for the strongly convex case.

###  II-C Relations of APM-C and APM to the Existing Algorithm Frameworks

####  II-C1 Difference from the classical penalty method

To the best of our knowledge, most traditional work analyze the penalty method
with a fixed penalty parameter [45, 46]. Let’s discuss the disadvantage of the
large and fixed penalty parameter. Take problem (4) as an example. Let
$\\{\mathbf{x}^{*},\lambda^{*}\\}$ be a pari of KKT point of problem (4) and
$\hat{\mathbf{x}}^{*}$ be the minimizer of problem (5), from the proof in [45,
Proposition 10], we have

$\displaystyle\begin{aligned}
f(\mathbf{x}^{*})=f(\mathbf{x}^{*})+\frac{\beta}{2}\|\Pi\mathbf{x}^{*}\|_{F}^{2}\geq
f(\hat{\mathbf{x}}^{*})+\frac{\beta}{2}\|\Pi\hat{\mathbf{x}}^{*}\|_{F}^{2}.\end{aligned}$

So for any $\varepsilon$-accurate solution $\mathbf{x}$ of problem (5), we
have

$\displaystyle\begin{aligned}
&f(\mathbf{x})+\frac{\beta}{2}\|\Pi\mathbf{x}\|_{F}^{2}-f(\mathbf{x}^{*})\\\
\leq&f(\mathbf{x})+\frac{\beta}{2}\|\Pi\mathbf{x}\|_{F}^{2}-f(\hat{\mathbf{x}}^{*})-\frac{\beta}{2}\|\Pi\hat{\mathbf{x}}^{*}\|_{F}^{2}\leq\varepsilon.\end{aligned}$

On the other hand, since
$\mathbf{x}^{*}=\operatorname*{argmin}_{\mathbf{x}}f(\mathbf{x})+\left\langle\lambda^{*},\Pi\mathbf{x}\right\rangle$
and $\Pi\mathbf{x}^{*}=0$, we have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{*})=f(\mathbf{x}^{*})+\left\langle\lambda^{*},\Pi\mathbf{x}^{*}\right\rangle\leq
f(\mathbf{x})+\left\langle\lambda^{*},\Pi\mathbf{x}\right\rangle\\\
\Rightarrow&-\|\lambda^{*}\|_{F}\|\Pi\mathbf{x}\|_{F}\leq
f(\mathbf{x})-f(\mathbf{x}^{*}).\end{aligned}$

So
$\frac{\beta}{2}\|\Pi\mathbf{x}\|_{F}^{2}-\|\lambda^{*}\|_{F}\|\Pi\mathbf{x}\|_{F}\leq\varepsilon$,
which leads to

$\displaystyle\begin{aligned}
\|\Pi\mathbf{x}\|_{F}\leq\frac{2\|\lambda^{*}\|_{F}}{\beta}+\sqrt{\frac{2\varepsilon}{\beta}}=O(\epsilon+\sqrt{\epsilon\varepsilon})\end{aligned}$

and

$\displaystyle\begin{aligned}
|f(\mathbf{x})-f(\mathbf{x}^{*})|\leq\max\\{\varepsilon,\epsilon+\sqrt{\epsilon\varepsilon}\\}\end{aligned}$

by $\beta=\frac{1}{\epsilon}$. We can see that the accuracy is dominated by
$\max\\{\epsilon,\varepsilon\\}$, and more iterations with smaller
$\varepsilon$ will not produce a more accurate solution.

On the other hand, even if $\varepsilon=0$ and
$\mathbf{x}=\hat{\mathbf{x}}^{*}$ with infinite iterations, we have $\nabla
f(\mathbf{x})+\beta\Pi\mathbf{x}=0$, which only leads to
$\|\Pi\mathbf{x}\|_{F}=\epsilon\|\nabla f(\mathbf{x})\|_{F}=O(\epsilon)$ and
$|f(\mathbf{x})-f(\mathbf{x}^{*})|\leq\epsilon$, rather than
$\|\Pi\mathbf{x}\|_{F}=0$ and $|f(\mathbf{x})-f(\mathbf{x}^{*})|=0$.

####  II-C2 Difference from the classical accelerated first-order algorithms

We extend the classical accelerated gradient method [47, 48, 38, 49, 50] from
the unconstrained problems to the linearly constrained problems via the
perspective of the penalty method. However, since we use the increasing
penalty parameters at each iteration, i.e., the penalized objective varies at
different iterations, the conclusion in [38, 49, 50] for the unconstrained
problems cannot be directly used for procedures (7a)-(7c) and (11a)-(11c). The
increasing penalty parameters make the convergence analysis more challenging.

####  II-C3 Difference from the accelerated gradient sliding method

[9] combined Nesterov’s smoothing technique [51] with the accelerated gradient
sliding methods [42, 43, 44] to solve the nonsmooth problem (10) with
$f(\mathbf{x})=0$. In fact, when fixing the penalty parameter as a large one
of the order $O(1/\epsilon)$, Algorithm 2 is similar to the one in [9, Section
6.3]. However, our method adopts increasing penalty parameters such that it
avoids having to set a large inner iteration number $T_{k}$ and a small step-
size $\eta_{k}$ at the beginning of the outer loop, as shown in Corollary 1.
On the other hand, when $f(\mathbf{x})\neq 0$, as explained in Section II-B,
$\nabla f(\mathbf{y}^{k})$ is flooded if we set a large and fixed penalty
parameter.

####  II-C4 Difference from the D-NC and D-NG in [8]

Algorithm 1 can be seen as an improvement over the D-NC proposed in [8]. Both
Algorithm 1 and D-NC use Nesterov’s acceleration technique and multi-
consensus, and both attain the optimal computation complexity for the
nonstrongly convex problems. However, Algorithm 1 is motivated by a
constraint-penalty approach while D-NC is developed from the inexact
accelerated gradient method [49] directly. Moreover, Algorithm 1 can solve
both the strongly convex and nonstrongly convex problems while [8] only
studied the nonstrongly convex case.

As for Algorithm 2, consider the simple case with $h(\mathbf{x})=0$ and
$\frac{\beta_{0}}{\vartheta_{k}}=\frac{k+1}{c}$, then steps (11b) and (11c)
become

$\displaystyle\mathbf{x}^{k+1}=\frac{L\mathbf{y}^{k}+(k+1)W\mathbf{y}^{k}/c}{L+(k+1)/c}-\frac{\nabla
f(\mathbf{y}^{k})}{L+(k+1)/c}.$

Thus, when $(k+1)/c\gg L$, we have $\mathbf{x}^{k+1}\approx
W\mathbf{y}^{k}-\frac{c}{k+1}\nabla f(\mathbf{y}^{k})$ and it approximates the
D-NG in [8]. Algorithm 2 gives a different explanation of the D-NG, and it
improves the D-NG in the sense that it handles a possible nondifferentiable
function $h_{i}(\mathbf{x})$. The complexity of D-NG is
$O\left(\frac{1}{\epsilon(1-\sigma_{2}(W))^{1+\xi}}\log\frac{1}{\epsilon}\right)$,
where $\xi$ is a small constant. Our complexity, i.e.,
$O\left(\frac{1}{\epsilon\sqrt{1-\sigma_{2}(W)}}\right)$, is better because
theirs has the extra $\log\frac{1}{\epsilon}$ factor and is more sensitive to
$1-\sigma_{2}(W)$.

##  III Proof of Theorems

###  III-A Supporting Lemmas

Before providing a comprehensive convergence analysis for Algorithms 1 and 2,
we first present some useful technical lemmas. We first give the following
easy-to-identify identifies.

###### Lemma 1

For any $\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{w}\in\mathbb{R}^{m\times
n}$, we have the following two identities:

$\displaystyle\begin{aligned}
&2\left\langle\mathbf{x}-\mathbf{z},\mathbf{y}-\mathbf{z}\right\rangle=\|\mathbf{x}-\mathbf{z}\|_{F}^{2}+\|\mathbf{y}-\mathbf{z}\|_{F}^{2}-\|\mathbf{x}-\mathbf{y}\|_{F}^{2},\\\
&2\left\langle\mathbf{x}-\mathbf{z},\mathbf{y}-\mathbf{w}\right\rangle=\|\mathbf{y}-\mathbf{z}\|_{F}^{2}-\|\mathbf{w}-\mathbf{z}\|_{F}^{2}+\|\mathbf{x}-\mathbf{w}\|_{F}^{2}-\|\mathbf{x}-\mathbf{y}\|_{F}^{2}.\end{aligned}$

In the following Lemma, we bound the Lagrange multiplier, which is useful for
the complexity analysis in the distributed optimization community.

###### Lemma 2

Assume that Assumptions 1, 2 and 3 hold with $\mu\geq 0$. Then, we have the
following properties:

  1. 1.

There exists a pair of KKT points $(\mathbf{x}^{*},\lambda^{*})$ of saddle
point problem
$\min_{\mathbf{x}}\max_{\lambda}f(\mathbf{x})+\left\langle\lambda,\Pi\mathbf{x}\right\rangle$,
such that $\|\lambda^{*}\|_{F}\leq\|\nabla f(\mathbf{x}^{*})\|_{F}$.

  2. 2.

There exists a pair of KKT points $(\mathbf{x}^{*},\lambda^{*})$ of saddle
point problem
$\min_{\mathbf{x}}\max_{\lambda}f(\mathbf{x})+\left\langle\lambda,U\mathbf{x}\right\rangle$,
such that $\|\lambda^{*}\|_{F}\leq\frac{\|\nabla
f(\mathbf{x}^{*})\|_{F}}{\sqrt{1-\sigma_{2}(W)}}$.

  3. 3.

There exists a pair of KKT points $(\mathbf{x}^{*},\lambda^{*})$ of saddle
point problem
$\min_{\mathbf{x}}\max_{\lambda}F(\mathbf{x})+\left\langle\lambda,U\mathbf{x}\right\rangle$,
such that $\|\lambda^{*}\|_{F}\leq\frac{\sqrt{m}M+\|\nabla
f(\mathbf{x}^{*})\|_{F}}{\sqrt{1-\sigma_{2}(W)}}$.

The proof can be found in [25, Theorem 2]. The following lemma is a corollary
of the saddle point property.

###### Lemma 3

[52] If $f(\mathbf{x})$ is convex and $(\mathbf{x}^{*},\lambda^{*})$ is a pair
of KKT points of saddle point problem
$\min_{\mathbf{x}}\max_{\lambda}f(\mathbf{x})+\left\langle\lambda,A\mathbf{x}\right\rangle$,
then we have
$f(\mathbf{x})-f(\mathbf{x}^{*})+\left\langle\lambda^{*},A\mathbf{x}\right\rangle\geq
0$ for all $\mathbf{x}$.

The following lemma bounds the consensus violation of $\|\Pi\mathbf{x}\|_{F}$
from $\|U\mathbf{x}\|_{F}$.

###### Lemma 4

Assume that Assumption 3 holds. Then, we have
$\|\Pi\mathbf{x}\|_{F}\leq\frac{1}{\sqrt{1-\sigma_{2}(W)}}\|U\mathbf{x}\|_{F}$.

###### Proof 1

From Assumption 3, we know $U\mathbf{1}=0$, $U=U^{T}$, and
$\mbox{rank}(U)=m-1$. For any $\mathbf{x}\in\mathbb{R}^{m\times n}$, denote
$\overline{\mathbf{x}}=\Pi\mathbf{x}=\mathbf{x}-\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\mathbf{x}$.
Since $\mathbf{1}^{T}\overline{\mathbf{x}}=0$, we know $\overline{\mathbf{x}}$
is orthogonal to the null space of $U$, and thus it belongs to the row (i.e.,
column) space of $U$. Let $V\Sigma V^{T}=U$ be its economical SVD with
$V\in\mathbb{R}^{m\times(m-1)}$. Then we have

$\displaystyle\begin{aligned}
&\|U\mathbf{x}\|_{F}^{2}=\|U\overline{\mathbf{x}}\|_{F}^{2}=\sum_{i=1}^{n}\overline{\mathbf{x}}_{i}^{T}U^{2}\overline{\mathbf{x}}_{i}=\sum_{i=1}^{n}(V^{T}\overline{\mathbf{x}}_{i})^{T}\Sigma^{2}(V^{T}\overline{\mathbf{x}}_{i})\\\
&\geq(1-\sigma_{2}(W))\sum_{i=1}^{n}\|V^{T}\overline{\mathbf{x}}_{i}\|_{F}^{2}=(1-\sigma_{2}(W))\|V^{T}\overline{\mathbf{x}}\|_{F}^{2}\\\
&\overset{a}{=}(1-\sigma_{2}(W))\|\overline{\mathbf{x}}\|_{F}^{2}=(1-\sigma_{2}(W))\|\Pi\mathbf{x}\|_{F}^{2},\end{aligned}$

where we denote $\mathbf{x}_{i}$ to be the $i$th column of $\mathbf{x}$, and
$\overset{a}{=}$ follows from the fact that $\overline{\mathbf{x}}$ belongs to
the column space of $U$, i.e., there exists $\alpha\in\mathbb{R}^{(m-1)\times
n}$ such tht $\overline{\mathbf{x}}=V\alpha$. $\Box$

At last, we present the following lemma, which can be used to analyze the
algorithms with inexact subproblem computation.

###### Lemma 5

[50] Assume that $(s_{k})$ is a sequence with increasing scalars and
$(v_{k})$, $(\alpha_{i})$ are sequences with nonnegative scalars,
$v_{0}^{2}\leq s_{0}$. If $v_{k}^{2}\leq s_{k}+\sum_{i=1}^{k}\alpha_{i}v_{i}$,
then we have
$v_{k}\leq\frac{1}{2}\sum_{i=1}^{k}\alpha_{i}+\sqrt{\left(\frac{1}{2}\sum_{i=1}^{k}\alpha_{i}\right)^{2}+s_{k}}$.

###  III-B Complexity Analysis for Algorithm 1

####  III-B1 Inner Loop

Before proving the convergence of procedure (7a)-(7c), we first establish the
required precision to approximate $\alpha(\mathbf{z}^{k})$ for an
$\varepsilon_{k}$-accurate solution of the subproblem in (7c).

###### Lemma 6

Let $\mathbf{z}^{k,T_{k}}$ be obtained by (8) and
$\mathbf{x}^{k+1}=\frac{L\vartheta_{k}\mathbf{z}^{k}+\beta_{0}\mathbf{z}^{k,T_{k}}}{L\vartheta_{k}+\beta_{0}}$.
If
$\|\mathbf{z}^{k,T_{k}}-\mathbf{1}\alpha(\mathbf{z}^{k})^{T}\|_{F}^{2}\leq\frac{2\vartheta_{k}\varepsilon_{k}}{\beta_{0}}$,
then we have

$\displaystyle\qquad\begin{aligned}
&\frac{L}{2}\left\|\mathbf{x}^{k+1}-\mathbf{z}^{k}\right\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}^{k+1}\|_{F}^{2}\\\
\leq&\min_{\mathbf{x}\in\mathbb{R}^{m\times
n}}\frac{L}{2}\left\|\mathbf{x}-\mathbf{z}^{k}\right\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}\|_{F}^{2}+\varepsilon_{k}.\end{aligned}$
(14)

###### Proof 2

Define
$\mathbf{x}^{k,*}=\operatorname*{argmin}_{\mathbf{x}}\frac{L}{2}\|\mathbf{x}-\mathbf{z}^{k}\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}\|_{F}^{2}$,
$\widetilde{\mathbf{x}}^{k,*}=\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\mathbf{x}^{k,*}$,
and
$\widetilde{\mathbf{z}}^{k}=\frac{1}{m}\mathbf{1}\mathbf{1}^{T}\mathbf{z}^{k}$.
From the optimality condition of $\mathbf{x}^{k,*}$, we have

$\displaystyle
0=L(\mathbf{x}^{k,*}-\mathbf{z}^{k})+\frac{\beta_{0}}{\vartheta_{k}}\Pi^{2}\mathbf{x}^{k,*}.$
(15)

From $\Pi=\Pi^{2}$ and its definition, we have
$0=L(\mathbf{x}^{k,*}-\mathbf{z}^{k})+\frac{\beta_{0}}{\vartheta_{k}}(\mathbf{x}^{k,*}-\widetilde{\mathbf{x}}^{k,*})$,
which leads to
$\mathbf{x}^{k,*}=\frac{L\vartheta_{k}\mathbf{z}^{k}+\beta_{0}\widetilde{\mathbf{x}}^{k,*}}{L\vartheta_{k}+\beta_{0}}$.
Multiplying both sides of (15) by $\frac{1}{m}\mathbf{1}\mathbf{1}^{T}$, and
using $\mathbf{1}^{T}\Pi=0$, we have
$\widetilde{\mathbf{x}}^{k,*}=\widetilde{\mathbf{z}}^{k}$, which further gives
$\mathbf{x}^{k,*}=\frac{L\vartheta_{k}\mathbf{z}^{k}+\beta_{0}\widetilde{\mathbf{z}}^{k}}{L\vartheta_{k}+\beta_{0}}$.
On the other hand, we have

$\displaystyle\begin{aligned}
&\frac{L}{2}\left\|\mathbf{x}^{k+1}-\mathbf{z}^{k}\right\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}^{k+1}\|_{F}^{2}\\\
&-\frac{L}{2}\left\|\mathbf{x}^{k,*}-\mathbf{z}^{k}\right\|_{F}^{2}-\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi\mathbf{x}^{k,*}\|_{F}^{2}\\\
\overset{a}{=}&L\left\langle\mathbf{x}^{k,*}-\mathbf{z}^{k},\mathbf{x}^{k+1}-\mathbf{x}^{k,*}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k,*}\|_{F}^{2}\\\
&+\frac{\beta_{0}}{\vartheta_{k}}\left\langle\Pi^{2}\mathbf{x}^{k,*},\mathbf{x}^{k+1}-\mathbf{x}^{k,*}\right\rangle+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi(\mathbf{x}^{k+1}-\mathbf{x}^{k,*})\|_{F}^{2}\\\
\overset{b}{=}&\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{x}^{k,*}\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi(\mathbf{x}^{k+1}-\mathbf{x}^{k,*})\|_{F}^{2}\\\
\overset{c}{=}&\frac{\beta_{0}^{2}}{(L\vartheta_{k}+\beta_{0})^{2}}\left(\frac{L}{2}\|\mathbf{z}^{k,T_{k}}-\widetilde{\mathbf{z}}^{k}\|_{F}^{2}+\frac{\beta_{0}}{2\vartheta_{k}}\|\Pi(\mathbf{z}^{k,T_{k}}-\widetilde{\mathbf{z}}^{k})\|_{F}^{2}\right)\\\
\overset{d}{\leq}&\frac{\beta_{0}^{2}}{2\vartheta_{k}(L\vartheta_{k}+\beta_{0})}\|\mathbf{z}^{k,T_{k}}-\widetilde{\mathbf{z}}^{k}\|_{F}^{2}\leq\frac{\beta_{0}}{2\vartheta_{k}}\|\mathbf{z}^{k,T_{k}}-\widetilde{\mathbf{z}}^{k}\|_{F}^{2}.\end{aligned}$
(16)

where we use Lemma 1 in $\overset{a}{=}$, (15) in $\overset{b}{=}$, the
definition of $\mathbf{x}^{k+1}$ and
$\mathbf{x}^{k,*}=\frac{L\vartheta_{k}\mathbf{z}^{k}+\beta_{0}\widetilde{\mathbf{z}}^{k}}{L\vartheta_{k}+\beta_{0}}$
in $\overset{c}{=}$, and $\|\Pi\mathbf{z}\|_{F}\leq\|\mathbf{z}\|_{F}$ in
$\overset{d}{\leq}$. $\Box$

Now we consider the iteration number of the accelerated average consensus in
(8) to solve the subproblem in (7c) such that (LABEL:inexact_assumption) is
satisfied. From [40, Proposition 3], we have

$\displaystyle\|\mathbf{z}^{k,T_{k}}-\mathbf{1}\alpha(\mathbf{z}^{k})^{T}\|_{F}\leq\left(\frac{\sigma_{2}(W)}{1+\sqrt{1-\sigma_{2}^{2}(W)}}\right)^{T_{k}}\|\Pi\mathbf{z}^{k}\|_{F}$
(17)
$\displaystyle\leq\left(\frac{\sigma_{2}(W)}{1+\sqrt{1-\sigma_{2}(W)}}\right)^{T_{k}}\|\Pi\mathbf{z}^{k}\|_{F}=\left(1-\sqrt{1-\sigma_{2}(W)}\right)^{T_{k}}\|\Pi\mathbf{z}^{k}\|_{F}.$

Thus, from Lemma 6, we only need

$T_{k}=\frac{1}{-2\log\left(1-\sqrt{1-\sigma_{2}(W)}\right)}\log\frac{\beta_{0}\|\Pi\mathbf{z}^{k}\|_{F}^{2}}{2\vartheta_{k}\varepsilon_{k}}$
(18)

such that (LABEL:inexact_assumption) is satisfied.

At last, we study the property when the proximal mapping in (7c) is inexactly
computed. When it is computed exactly, i.e., $\varepsilon_{k}=0$ in
(LABEL:inexact_assumption), we have
$L(\mathbf{x}^{k+1}-\mathbf{z}^{k})+\frac{\beta_{0}}{\vartheta_{k}}\Pi^{2}\mathbf{x}^{k+1}=0$.
However, when it is computed inexactly, we should modify the conclusion
accordingly. Specifically, we give the following lemma.

###### Lemma 7

Assume that (LABEL:inexact_assumption) holds. Then, there exists $\delta^{k}$
with $\|\delta^{k}\|_{F}\leq\sqrt{\frac{2\varepsilon_{k}}{L}}$ and
$\frac{\beta_{0}}{\vartheta_{k}}\|\Pi\delta^{k}\|_{F}^{2}\leq
2\varepsilon_{k}$ such that

$\displaystyle\begin{aligned}
L(\mathbf{x}^{k+1}-\mathbf{z}^{k}+\delta^{k})+\frac{\beta_{0}}{\vartheta_{k}}\Pi^{2}(\mathbf{x}^{k+1}+\delta^{k})=0.\end{aligned}$
(19)

###### Proof 3

Define $\delta^{k}=\mathbf{x}^{k,*}-\mathbf{x}^{k+1}$. From
(LABEL:inexact_assumption) and equation $\overset{b}{=}$ in (LABEL:cont4), we
have $\|\delta^{k}\|_{F}\leq\sqrt{\frac{2\varepsilon_{k}}{L}}$ and
$\frac{\beta_{0}}{\vartheta_{k}}\|\Pi\delta^{k}\|_{F}^{2}\leq
2\varepsilon_{k}$. From (15) and the definition of $\delta^{k}$, we have (19).
$\Box$

####  III-B2 Outer Loop

Now we are ready to analyze procedure (7a)-(7c). Define

$\mathbf{w}^{k+1}\equiv\frac{\mathbf{x}^{k+1}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}\mbox{
for any }k\geq 0\mbox{ and }\mathbf{w}^{0}=\mathbf{x}^{0}.$

From the definition of $\mathbf{y}^{k}$ in (7a), we can give the following
easy-to-identify identities.

###### Lemma 8

For procedure (7a)-(7c), we have

$\displaystyle\begin{aligned}
&\mathbf{x}^{*}+\frac{(1-\theta_{k})L}{L\theta_{k}-\mu}\mathbf{x}^{k}-\frac{L-\mu}{L\theta_{k}-\mu}\mathbf{y}^{k}=\mathbf{x}^{*}-\mathbf{w}^{k},\\\
&\theta_{k}\mathbf{x}^{*}+(1-\theta_{k})\mathbf{x}^{k}-\mathbf{x}^{k+1}=\theta_{k}\left(\mathbf{x}^{*}-\mathbf{w}^{k+1}\right).\end{aligned}$

Let $(\mathbf{x}^{*},\lambda^{*})$ be a pair of KKT points of saddle point
problem
$\min_{\mathbf{x}}\max_{\lambda}f(\mathbf{x})+\left\langle\lambda,\Pi\mathbf{x}\right\rangle$
satisfying Lemma 2. Define

$\rho_{k+1}=f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})+\left\langle\lambda^{*},\Pi\mathbf{x}^{k+1}\right\rangle.$
(20)

From Lemma 3, we know $\rho_{k+1}\geq 0$.

We first give the following lemma, which describes a progress in one iteration
of procedure (7a)-(7c).

###### Lemma 9

Assume that Assumption 1 holds with $\mu\geq 0$. Let sequences
$\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy
$\frac{1-\theta_{k}}{\vartheta_{k}}=\frac{1}{\vartheta_{k-1}}$ and
$\theta_{k}\geq\frac{\mu}{L}$. Then, under the assumption of
(LABEL:inexact_assumption), we have

$\displaystyle\begin{aligned}
&\rho_{k+1}+\frac{\vartheta_{k}}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}+\frac{L\theta_{k}^{2}}{2}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}\\\
\leq&(1-\theta_{k})\rho_{k}+\frac{\vartheta_{k}}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k-1}}\Pi\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}+\varepsilon_{k}\\\
&+\frac{(L\theta_{k}-\mu)\theta_{k}}{2}\left\|\mathbf{w}^{k}-\mathbf{x}^{*}\right\|_{F}^{2}+L\theta_{k}\sqrt{\frac{2\varepsilon_{k}}{L}}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}.\end{aligned}$
(21)

###### Proof 4

From the smoothness and convexity of $f(\mathbf{x})$, 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}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
=&f(\mathbf{y}^{k})+\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}-\mathbf{y}^{k}\right\rangle+\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\mathbf{x}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
\leq&f(\mathbf{x})-\frac{\mu}{2}\|\mathbf{x}-\mathbf{y}^{k}\|_{F}^{2}+\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\mathbf{x}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}.\end{aligned}$
(22)

Plugging $\mathbf{z}^{k}=\mathbf{y}^{k}-\frac{1}{L}\nabla f(\mathbf{y}^{k})$
and (19) into the above inequality, we have

$\displaystyle\begin{aligned} &f(\mathbf{x}^{k+1})-f(\mathbf{x})\\\
\leq&\frac{\beta_{0}}{\vartheta_{k}}\left\langle\Pi\mathbf{x}^{k+1}+\Pi\delta^{k},\Pi\mathbf{x}-\Pi\mathbf{x}^{k+1}\right\rangle+L\left\langle\mathbf{x}^{k+1}-\mathbf{y}^{k},\mathbf{x}-\mathbf{y}^{k}\right\rangle\\\
&+L\left\langle\delta^{k},\mathbf{x}-\mathbf{x}^{k+1}\right\rangle-\frac{\mu}{2}\|\mathbf{x}-\mathbf{y}^{k}\|_{F}^{2}-\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\end{aligned}$

When we apply (LABEL:cont6) first with $\mathbf{x}=\mathbf{x}^{k}$ and then
with $\mathbf{x}=\mathbf{x}^{*}$, we obtain two inequalities. Multiplying the
first inequality by $(1-\theta_{k})$, multiplying the second by $\theta_{k}$,
adding them together with
$\left\langle\lambda^{*},\Pi\mathbf{x}^{k+1}-(1-\theta_{k})\Pi\mathbf{x}^{k}\right\rangle$
to both sides, and using $\Pi\mathbf{x}^{*}=0$, we have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{k+1})-(1-\theta_{k})f(\mathbf{x}^{k})-\theta_{k}f(\mathbf{x}^{*})\\\
&+\left\langle\lambda^{*},\Pi\mathbf{x}^{k+1}-(1-\theta_{k})\Pi\mathbf{x}^{k}\right\rangle\end{aligned}$
$\displaystyle\begin{aligned}
\leq&\left\langle\frac{\beta_{0}}{\vartheta_{k}}(\Pi\mathbf{x}^{k+1}+\Pi\delta^{k})-\lambda^{*},(1-\theta_{k})\Pi\mathbf{x}^{k}-\Pi\mathbf{x}^{k+1}\right\rangle\\\
&+L\left\langle\mathbf{x}^{k+1}-\mathbf{y}^{k},(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{y}^{k}\right\rangle\\\
&+L\left\langle\delta^{k},(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{x}^{k+1}\right\rangle\\\
&-\frac{\mu\theta_{k}}{2}\|\mathbf{x}^{*}-\mathbf{y}^{k}\|_{F}^{2}-\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
\overset{a}{=}&\frac{\vartheta_{k}}{\beta_{0}}\left\langle\frac{\beta_{0}}{\vartheta_{k}}(\Pi\mathbf{x}^{k+1}+\Pi\delta^{k})-\lambda^{*},\frac{\beta_{0}}{\vartheta_{k-1}}\Pi\mathbf{x}^{k}-\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}\right\rangle\\\
&+L\left\langle\mathbf{x}^{k+1}-\mathbf{y}^{k},(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{y}^{k}\right\rangle\\\
&+L\left\langle\delta^{k},(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{x}^{k+1}\right\rangle\\\
&-\frac{\mu\theta_{k}}{2}\|\mathbf{x}^{*}-\mathbf{y}^{k}\|_{F}^{2}-\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2},\end{aligned}$

where we use $\frac{1-\theta_{k}}{\vartheta_{k}}=\frac{1}{\vartheta_{k-1}}$ in
$\overset{a}{=}$. Applying the identities in Lemma 1 to the two inner
products, we have

$\displaystyle\begin{aligned} &\rho_{k+1}-(1-\theta_{k})\rho_{k}\\\
\leq&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}\Pi\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}+\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\frac{\beta_{0}}{\vartheta_{k}}(\Pi\mathbf{x}^{k+1}+\Pi\delta^{k})\right\|_{F}^{2}\right.\\\
&\left.-\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k-1}}\Pi\mathbf{x}^{k}-\frac{\beta_{0}}{\vartheta_{k}}(\Pi\mathbf{x}^{k+1}+\Pi\delta^{k})\right\|_{F}^{2}\right]\\\
&+\frac{L}{2}\left[\|(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{y}^{k}\|_{F}^{2}-\|(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{x}^{k+1}\|_{F}^{2}\right]\\\
&+L\left\langle\delta^{k},(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}-\mathbf{x}^{k+1}\right\rangle-\frac{\mu\theta_{k}}{2}\|\mathbf{x}^{*}-\mathbf{y}^{k}\|_{F}^{2}\\\
\overset{b}{\leq}&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}\Pi\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}+\frac{\beta_{0}^{2}}{\vartheta_{k}^{2}}\|\Pi\delta^{k}\|_{F}^{2}\right]\\\
&+\frac{L\theta_{k}^{2}}{2}\left[\left\|\frac{\mathbf{y}^{k}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}-\mathbf{x}^{*}\right\|_{F}^{2}-\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&-L\theta_{k}\left\langle\delta^{k},\mathbf{w}^{k+1}-\mathbf{x}^{*}\right\rangle-\frac{\mu\theta_{k}}{2}\|\mathbf{x}^{*}-\mathbf{y}^{k}\|_{F}^{2}.\end{aligned}$

where $\overset{b}{\leq}$ follows from the second identity in Lemma 8. By
reorganizing the terms in
$\frac{\mathbf{y}^{k}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}-\mathbf{x}^{*}$
carefully, we have

$\displaystyle\begin{aligned}
&\frac{L\theta_{k}^{2}}{2}\left\|\frac{\mathbf{y}^{k}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}-\mathbf{x}^{*}\right\|_{F}^{2}\\\
=&\frac{L\theta_{k}^{2}}{2}\left\|\frac{\mu}{L\theta_{k}}\left(\mathbf{y}^{k}-\mathbf{x}^{*}\right)+\left(1-\frac{\mu}{L\theta_{k}}\right)\left(\frac{L-\mu}{L\theta_{k}-\mu}\mathbf{y}^{k}-\frac{(1-\theta_{k})L}{L\theta_{k}-\mu}\mathbf{x}^{k}-\mathbf{x}^{*}\right)\right\|_{F}^{2}\\\
\overset{c}{\leq}&\frac{\mu\theta_{k}}{2}\|\mathbf{y}^{k}-\mathbf{x}^{*}\|_{F}^{2}+\frac{(L\theta_{k}-\mu)\theta_{k}}{2}\left\|\frac{L-\mu}{L\theta_{k}-\mu}\mathbf{y}^{k}-\frac{(1-\theta_{k})L}{L\theta_{k}-\mu}\mathbf{x}^{k}-\mathbf{x}^{*}\right\|_{F}^{2}\\\
\overset{d}{=}&\frac{\mu\theta_{k}}{2}\|\mathbf{y}^{k}-\mathbf{x}^{*}\|_{F}^{2}+\frac{(L\theta_{k}-\mu)\theta_{k}}{2}\left\|\mathbf{w}^{k}-\mathbf{x}^{*}\right\|_{F}^{2},\end{aligned}$

where we let $\frac{\mu}{L\theta_{k}}\leq 1$, and use Jensen’s inequality for
$\|\cdot\|_{F}^{2}$ in $\overset{c}{\leq}$, and the first identify in Lemma 8
in $\overset{d}{=}$. Plugging it into the above inequality and using the
bounds for $\|\delta^{k}\|_{F}$ and $\|\Pi\delta^{k}\|_{F}$ in Lemma 7, we get
(LABEL:lemma_nc). $\Box$

Due to the term $\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}$ on the right hand
side of (LABEL:lemma_nc), recursion (LABEL:lemma_nc) cannot be directly
telescoped unless we assume the boundness of
$\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}$. Lemma 5 can be used to avoid such
boundness assumption. Now, we use Lemmas 9 and 5 to analyze procedure
(7a)-(7c). The following theorem shows the convergence for strongly convex
problems.

###### Theorem 4

Assume that Assumptions 1, 3 and (LABEL:inexact_assumption) hold with $\mu>0$,
and $\varepsilon_{k}\leq(1-(1+\tau)\theta)^{k+1}$ holds for all $k\leq K$,
where $1>\tau>0$ can be any small constant. Let sequences $\\{\theta_{k}\\}$
and $\\{\vartheta_{k}\\}$ satisfy $\theta_{k}=\theta=\sqrt{\frac{\mu}{L}}$ for
all $k$, and $\vartheta_{k}=(1-\theta)^{k+1}$. Then, we have

$\displaystyle\begin{aligned} &f(\mathbf{x}^{K+1})-f(\mathbf{x}^{*})\leq
C_{2}(1-\theta)^{K+1},\\\ &\|\Pi\mathbf{x}^{K+1}\|_{F}\leq
C_{3}(1-\theta)^{K+1},\\\ &\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}^{2}\leq
C_{4}(1-\theta)^{K+1},\\\
&f\left(\alpha(\mathbf{x}^{K+1})\right)-f(\mathbf{x}^{*})\leq
C_{5}(1-\theta)^{K+1}+\frac{LC_{3}^{2}}{2}(1-\theta)^{2K+2},\end{aligned}$

where $C_{2}=C_{6}+\|\lambda^{*}\|_{F}C_{3}$,
$C_{3}=\frac{\sqrt{2\beta_{0}C_{6}}+\|\lambda^{*}\|_{F}}{\beta_{0}}$,
$C_{4}=\frac{2C_{6}}{\mu}$, $C_{5}=(\|\nabla
f(\mathbf{x}^{*})\|_{F}+L\sqrt{C_{4}})C_{3}+C_{2}$ and
$C_{6}=\frac{18}{\tau^{2}\theta^{2}}+2\left(f(\mathbf{x}^{0})-f(\mathbf{x}^{*})+\left\langle\lambda^{*},\Pi\mathbf{x}^{0}\right\rangle\right)+\frac{1}{\beta_{0}}\|\beta_{0}\Pi\mathbf{x}^{0}-\lambda^{*}\|_{F}^{2}+\mu\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}^{2}$.

###### Proof 5

The setting of $\theta=\sqrt{\frac{\mu}{L}}$ satisfies

$(L\theta-\mu)\theta=L\theta^{2}(1-\theta).$ (23)

Sequences $\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy the requirement
in Lemma 9. Define the Lyapunov function $\ell_{k+1}$ as follows:

$\displaystyle\begin{aligned}
\ell_{k+1}^{2}=\frac{\rho_{k+1}+\frac{\vartheta_{k}}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}+\frac{L\theta^{2}}{2}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}}{(1-\theta)^{k+1}},\end{aligned}$

where $\rho_{k}$ is defined in (20). Dividing both sides of (LABEL:lemma_nc)
by $(1-\theta)^{k+1}$, and using (23) and
$\vartheta_{k}=(1-\theta)\vartheta_{k-1}$, we have

$\displaystyle\begin{aligned}
\ell_{k+1}^{2}-\ell_{k}^{2}\leq\frac{\varepsilon_{k}}{(1-\theta)^{k+1}}+\frac{L\theta}{(1-\theta)^{k+1}}\sqrt{\frac{2\varepsilon_{k}}{L}}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}.\end{aligned}$

Summing over $k=0,1,\cdots,K$, we have

$\displaystyle\begin{aligned} &\ell_{K+1}^{2}-\ell_{0}^{2}\\\
\leq&\sum_{k=0}^{K}\frac{\varepsilon_{k}}{(1-\theta)^{k+1}}+\sum_{k=0}^{K}\frac{L\theta}{(1-\theta)^{k+1}}\sqrt{\frac{2\varepsilon_{k}}{L}}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}\\\
=&\sum_{k=0}^{K}\frac{\varepsilon_{k}}{(1-\theta)^{k+1}}+\sum_{k=1}^{K+1}\frac{2\sqrt{\varepsilon_{k-1}}}{(1-\theta)^{k/2}}\sqrt{\frac{L\theta^{2}}{2(1-\theta)^{k}}}\|\mathbf{w}^{k}-\mathbf{x}^{*}\|_{F}\\\
\overset{a}{\leq}&\sum_{k=0}^{K}\frac{\varepsilon_{k}}{(1-\theta)^{k+1}}+\sum_{k=1}^{K+1}\frac{2\sqrt{\varepsilon_{k-1}}}{(1-\theta)^{k/2}}\ell_{k},\end{aligned}$

where we use the definition of $\ell_{k}$ and $\rho_{k}\geq 0$ in
$\overset{a}{\leq}$. Letting
$s_{k+1}=\sum_{t=0}^{k}\frac{\varepsilon_{t}}{(1-\theta)^{t+1}}+\ell_{0}^{2}$
and $\alpha_{k}=\frac{2\sqrt{\varepsilon_{k-1}}}{(1-\theta)^{k/2}}$, then we
have $\ell_{k+1}^{2}\leq s_{k+1}+\sum_{i=1}^{k+1}\alpha_{i}\ell_{i}$ and
$\ell_{0}^{2}=s_{0}$. From Lemma 5, we have
$\ell_{k+1}\leq\frac{1}{2}\sum_{i=1}^{k+1}\alpha_{i}+\sqrt{\left(\frac{1}{2}\sum_{i=1}^{k+1}\alpha_{i}\right)^{2}+s_{k+1}}$.
Letting $\varepsilon_{k}\leq(1-(1+\tau)\theta)^{k+1}$, and after some simple
computing, we obtain

$\displaystyle\begin{aligned}
\ell_{K+1}^{2}\leq&\left(\sum_{k=1}^{K+1}\frac{2\sqrt{\varepsilon_{k-1}}}{(1-\theta)^{k/2}}\right)^{2}+\sum_{k=0}^{K}\frac{2\varepsilon_{k}}{(1-\theta)^{k+1}}+2\ell_{0}^{2}\\\
\leq&\frac{18}{\tau^{2}\theta^{2}}+2\ell_{0}^{2}\equiv C_{6}.\end{aligned}$

From the definition of $\ell_{K+1}$ and $\rho_{k}\geq 0$, we get the second
conclusion. From the definition of $\rho_{k+1}$, we have
$f(\mathbf{x}^{k+1})-f(\mathbf{x}^{*})\leq\rho_{k+1}+\|\lambda^{*}\|_{F}\|\Pi\mathbf{x}^{k+1}\|_{F}$,
which further leads to the first conclusion. Since
$f(\mathbf{x})+\left\langle\lambda^{*},\Pi\mathbf{x}\right\rangle$ is
$\mu$-strongly convex over $\mathbf{x}$ and
$\mathbf{x}^{*}=\operatorname*{argmin}_{\mathbf{x}}f(\mathbf{x})+\left\langle\lambda^{*},\Pi\mathbf{x}\right\rangle$,
we have $\frac{\mu}{2}\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}^{2}\leq
f(\mathbf{x}^{K+1})+\left\langle\lambda^{*},\Pi\mathbf{x}^{K+1}\right\rangle-f(\mathbf{x}^{*})-\left\langle\lambda^{*},\Pi\mathbf{x}^{*}\right\rangle=\rho_{K+1}\leq
C_{6}(1-\theta)^{K+1}$, i.e., the third conclusion. For the fourth conclusion,
we have

$\displaystyle\begin{aligned}
&f\left(\alpha(\mathbf{x}^{K+1}\right)-f(\mathbf{x}^{*})\\\
=&f\left(\alpha(\mathbf{x}^{K+1}\right)-f(\mathbf{x}^{K+1})+f(\mathbf{x}^{K+1})-f(\mathbf{x}^{*})\\\
\overset{b}{\leq}&\left\langle\nabla
f(\mathbf{x}^{K+1}),-\Pi\mathbf{x}^{K+1}\right\rangle+\frac{L}{2}\left\|\Pi\mathbf{x}^{K+1}\right\|_{F}^{2}+f(\mathbf{x}^{K+1})-f(\mathbf{x}^{*})\\\
\overset{c}{\leq}&\left(\|\nabla
f(\mathbf{x}^{*})\|_{F}+L\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}\right)\|\Pi\mathbf{x}^{K+1}\|_{F}+\frac{L}{2}\|\Pi\mathbf{x}^{K+1}\|_{F}^{2}\\\
&+f(\mathbf{x}^{K+1})-f(\mathbf{x}^{*}),\end{aligned}$ (24)

where we use the smoothness of $f(\mathbf{x})$ and the definition of $\Pi$ in
$\overset{b}{\leq}$ and $\overset{c}{\leq}$. $\Box$

In the following theorem, we consider the case that $f(\mathbf{x})$ is
nonstrongly convex.

###### Theorem 5

Assume that Assumptions 1, 3 and (LABEL:inexact_assumption) hold with $\mu=0$
and $\varepsilon_{k}\leq\frac{1}{(k+1)^{6}}$ for all $k\leq K$. Let sequences
$\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy $\theta_{0}=1$,
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$, and
$\vartheta_{k}=\theta_{k}^{2}$. Then, we have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{K+1})-f(\mathbf{x}^{*})\leq\frac{C_{7}}{(K+2)^{2}},\\\
&\|\Pi\mathbf{x}^{K+1}\|_{F}\leq\frac{C_{8}}{(K+2)^{2}},\\\
&\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}^{2}\leq C_{9},\\\
&f\left(\alpha(\mathbf{x}^{K+1})\right)-f(\mathbf{x}^{*})\leq\frac{C_{10}}{(K+2)^{2}}+\frac{LC_{8}^{2}}{2(K+2)^{4}},\end{aligned}$

where $C_{7}=4C_{11}+\|\nabla f(\mathbf{x}^{*})\|_{F}C_{8}$,
$C_{8}=\frac{4\sqrt{2\beta_{0}C_{11}}+4\|\nabla
f(\mathbf{x}^{*})\|_{F}}{\beta_{0}}$, $C_{9}=\frac{2C_{11}}{L}$,
$C_{10}=(\|\nabla f(\mathbf{x}^{*})\|_{F}+L\sqrt{C_{9}})C_{8}+C_{7}$, and
$C_{11}=5+\frac{\|\nabla
f(\mathbf{x}^{*})\|_{F}^{2}}{\beta_{0}}+L\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}^{2}$.

###### Proof 6

Define the following Lyapunov function $\ell_{k+1}$

$\displaystyle\begin{aligned}
&\ell_{k+1}^{2}=\frac{\rho_{k+1}}{\theta_{k}^{2}}+\frac{1}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}\Pi\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}+\frac{L}{2}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}.\\\
\end{aligned}$

Dividing both sides of (LABEL:lemma_nc) by $\theta_{k}^{2}$, using
$\vartheta_{k}=\theta_{k}^{2}$ and
$\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$, we have

$\displaystyle\begin{aligned}
\ell_{k+1}^{2}-\ell_{k}^{2}\leq\frac{\varepsilon_{k}}{\theta_{k}^{2}}+\frac{L}{\theta_{k}}\sqrt{\frac{2\varepsilon_{k}}{L}}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}.\end{aligned}$

Similar to the proof of Theorem 4, we obtain

$\displaystyle\begin{aligned}
\ell_{K+1}^{2}-\ell_{0}^{2}\leq\sum_{k=0}^{K}\frac{\varepsilon_{k}}{\theta_{k}^{2}}+\sum_{k=1}^{K+1}\frac{2\sqrt{\varepsilon_{k-1}}}{\theta_{k-1}}\ell_{k}.\end{aligned}$

From Lemma 5 and a similar induction to Theorem 4, we have

$\displaystyle\begin{aligned} &\ell_{K+1}^{2}\\\
\leq&\left(\sum_{k=1}^{K+1}\frac{2\sqrt{\varepsilon_{k-1}}}{\theta_{k-1}}\right)^{2}+\sum_{k=0}^{K}\frac{2\varepsilon_{k}}{\theta_{k}^{2}}+2\ell_{0}^{2}\\\
\overset{a}{\leq}&\left(\sum_{k=1}^{K+1}2k\sqrt{\varepsilon_{k-1}}\right)^{2}+\sum_{k=0}^{K}2\varepsilon_{k}(k+1)^{2}+\frac{\|\lambda^{*}\|_{F}^{2}}{\beta_{0}}+L\|\mathbf{w}^{0}-\mathbf{x}^{*}\|_{F}^{2},\end{aligned}$

where we use $\frac{1}{k+1}\leq\theta_{k}\leq\frac{2}{k+2}$ and
$\frac{1}{\theta_{-1}^{2}}=0$ in $\overset{a}{\leq}$, which can be derived
from $\frac{1-\theta_{k}}{\theta_{k}^{2}}=\frac{1}{\theta_{k-1}^{2}}$ and
$\theta_{0}=1$. Letting $\varepsilon_{k}\leq\frac{1}{(k+1)^{4+2\tau}}$, then
we have $\sum_{k=0}^{K}2\varepsilon_{k}(k+1)^{2}\leq\frac{2}{1+2\tau}$ and
$\sum_{k=1}^{K+1}2k\sqrt{\varepsilon_{k-1}}\leq\frac{2}{\tau}$. So

$\displaystyle\begin{aligned}
\ell_{K+1}^{2}\leq\frac{4}{\tau^{2}}+\frac{4}{1+2\tau}+\frac{\|\lambda^{*}\|_{F}^{2}}{\beta_{0}}+L\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}^{2}\equiv
C_{11},\end{aligned}$

where we let $\tau=1$ for simplicity and use Lemma 2. From the definition of
$\mathbf{w}^{k+1}=\frac{\mathbf{x}^{k+1}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}$,
we have
$\|\mathbf{x}^{k+1}-\mathbf{x}^{*}\|_{F}=\|\theta_{k}\mathbf{w}^{k+1}+(1-\theta_{k})\mathbf{x}^{k}-\mathbf{x}^{*}\|_{F}\leq\theta_{k}\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}+(1-\theta_{k})\|\mathbf{x}^{k}-\mathbf{x}^{*}\|_{F}$.
By induction, we can prove
$\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}^{2}\leq\frac{2C_{11}}{L}$ for any
$k$. Similar to the proof of Theorem 4 and using Lemma 2, we have the
remaining conclusions. $\Box$

####  III-B3 Total Numbers of Communications and Computations

Based on Theorems 4 and 5, and the inner loop iteration number given in (18),
we can establish the gradient computation and communication complexities for
Algorithm 1. We first consider the strongly convex case and prove Theorem 1.

###### Proof 7

$\|\Pi\mathbf{z}^{k}\|_{F}$ appears in (18). We first prove that
$\|\Pi\mathbf{z}^{k}\|_{F}$ is bounded for any $k$ given
$T_{k}=\frac{1}{-2\log\left(1-\sqrt{1-\sigma_{2}(W)}\right)}\log\left(\frac{\beta_{0}}{2\vartheta_{k}\varepsilon_{k}}\left(\frac{1}{L}\|\nabla
f(\mathbf{x}^{*})\|_{F}+6\sqrt{C_{4}}\right)^{2}\right)$, where $C_{4}$ is
defined in Theorem 4. We prove
$\|\Pi\mathbf{z}^{k}\|_{F}\leq\frac{1}{L}\|\nabla
f(\mathbf{x}^{*})\|_{F}+6\sqrt{C_{4}}$ by induction. The case for $k=0$ can be
easily verified since
$\|\Pi\mathbf{z}^{0}\|_{F}=\|\Pi\mathbf{x}^{0}-\Pi\mathbf{x}^{*}\|_{F}\leq\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}$.
Assume that the conclusion holds for all $k\leq K$. Then from (18) we know
that (LABEL:inexact_assumption) holds for $k\leq K$. From Theorem 4, we have
$\|\mathbf{x}^{K}-\mathbf{x}^{*}\|_{F}\leq\sqrt{C_{4}}$ and
$\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}\leq\sqrt{C_{4}}$. Thus,

$\displaystyle\begin{aligned} &\|\Pi\mathbf{z}^{K+1}\|_{F}\\\
\overset{a}{\leq}&\|\Pi\mathbf{y}^{K+1}\|_{F}+\frac{1}{L}\|\nabla
f(\mathbf{y}^{K+1})\|_{F}\\\
\overset{b}{\leq}&\|\Pi(\mathbf{y}^{K+1}-\mathbf{x}^{*})\|_{F}+\frac{1}{L}\left(\|\nabla
f(\mathbf{x}^{*})\|_{F}+L\|\mathbf{y}^{K+1}-\mathbf{x}^{*}\|_{F}\right)\\\
\leq&\frac{1}{L}\|\nabla
f(\mathbf{x}^{*})\|_{F}+2\|\mathbf{y}^{K+1}-\mathbf{x}^{*}\|_{F}\\\
\overset{c}{\leq}&\frac{1}{L}\|\nabla
f(\mathbf{x}^{*})\|_{F}+4\|\mathbf{x}^{K+1}-\mathbf{x}^{*}\|_{F}+2\|\mathbf{x}^{K}-\mathbf{x}^{*}\|_{F}\\\
\leq&\frac{1}{L}\|\nabla f(\mathbf{x}^{*})\|_{F}+6\sqrt{C_{4}},\end{aligned}$

where we use (7b) in $\overset{a}{\leq}$, the smoothness of $f(\mathbf{x})$
and $\Pi\mathbf{x}^{*}=0$ in $\overset{b}{\leq}$, and
$\mathbf{y}^{k}=\mathbf{x}^{k}+\frac{\sqrt{L}-\sqrt{\mu}}{\sqrt{L}+\sqrt{\mu}}(\mathbf{x}^{k}-\mathbf{x}^{k-1})$
in $\overset{c}{\leq}$, which is equivalent to (7a) with the special setting
of $\theta_{k}$. So we get the conclusion.

From Theorem 4, to find a solution satisfying (LABEL:cont14), we know that the
number of gradient computations, i.e., the number of outer iterations, is
$O\left(\sqrt{\frac{L}{\mu}}\log\frac{1}{\epsilon}\right)$. From (18), we have

$\displaystyle\begin{aligned}
T_{k}=&O\left(\frac{1}{-\log\left(1-\sqrt{1-\sigma_{2}(W)}\right)}\log\frac{1}{(1-\theta)^{2(k+1)}}\right)\\\
=&O\left(\frac{k\log\left(1-\sqrt{\mu/L}\right)}{\log\left(1-\sqrt{1-\sigma_{2}(W)}\right)}\right)\overset{c}{=}O\left(\frac{k\sqrt{\mu/L}}{\sqrt{1-\sigma_{2}(W)}}\right),\end{aligned}$

where we use
$\log\left((1-\sqrt{1-\sigma_{2}(W)})\right)\approx-\sqrt{1-\sigma_{2}(W)}$
and $\log\left(1-\sqrt{\mu/L}\right)\approx-\sqrt{\mu/L}$ in $\overset{c}{=}$
from Taylor expansion when $\sqrt{1-\sigma_{2}(W)}$ and $\sqrt{\mu/L}$ are
small. Thus, the total number of communications, i.e., the total number of
inner iterations, is

$\sum_{k=0}^{\sqrt{L/\mu}\log\frac{1}{\epsilon}}O\left(k\sqrt{\frac{\mu}{L(1-\sigma_{2}(W))}}\right)=O\left(\sqrt{\frac{L}{\mu(1-\sigma_{2}(W))}}\log^{2}\frac{1}{\epsilon}\right).$

The proof is complete. $\Box$

Similar to the proof of Theorem 1, we can also prove Theorem 2 for the
nonstrongly case.

###### Proof 8

Similar to the above proof of Theorem 1 and given the similar $T_{k}$
replacing $C_{4}$ by $C_{9}$, we know that $\|\Pi\mathbf{z}^{k}\|_{F}$ is also
bounded for all $k$. Let $\beta_{0}\geq L+L\|\nabla
f(\mathbf{x}^{*})\|_{F}^{2}$, and assume $L\geq 1$ and $\|\nabla
f(\mathbf{x}^{*})\|_{F}\geq 1$ for simplicity. Using the constants in (13), we
know $C_{7}=O(mLR_{1}^{2})$, $C_{8}=O(\sqrt{m}R_{1})$, $C_{9}=O(mR_{1}^{2})$,
and $C_{10}=O(mLR_{1}^{2})$. Let $\epsilon=\frac{LR_{1}^{2}}{(K+2)^{2}}$. From
Theorem 5, we know that Algorithm 1 needs
$O\left(\sqrt{\frac{L}{\epsilon}}\right)$ gradient computations such that
$\frac{1}{m}\left(f\left(\alpha(\mathbf{x}^{K+1})\right)-f(\mathbf{x}^{*})\right)\leq\epsilon$
and $\frac{1}{m}\|\Pi\mathbf{x}^{K+1}\|_{F}^{2}\leq\epsilon^{2}$, i.e.,
(LABEL:cont14) holds. From (18), we have

$T_{k}=O\left(\frac{\log(k+1)^{8}}{-\log\left(1-\sqrt{1-\sigma_{2}(W)}\right)}\right)=O\left(\frac{\log
k}{\sqrt{1-\sigma_{2}(W)}}\right),$

Thus, the total number of communications is

$\sum_{k=0}^{K}T_{k}=\sum_{k=0}^{\sqrt{L/\epsilon}}O\left(\frac{\log
k}{\sqrt{1-\sigma_{2}(W)}}\right)=O\left(\sqrt{\frac{L}{\epsilon(1-\sigma_{2}(W))}}\log\frac{1}{\epsilon}\right).$

The proof is complete. $\Box$

###  III-C Complexity Analysis for Algorithm 2

Now we prove Theorem 3. Similar to Section III-B, we define

$\rho_{k+1}=F(\mathbf{x}^{k+1})-F(\mathbf{x}^{*})+\left\langle\lambda^{*},U\mathbf{x}^{k+1}\right\rangle,$

where $(\mathbf{x}^{*},\lambda^{*})$ is a pair of KKT points of saddle point
problem
$\min_{\mathbf{x}}\max_{\lambda}F(\mathbf{x})+\left\langle\lambda,U\mathbf{x}\right\rangle$
satisfying Lemma 2. Define

$\mathbf{w}^{k+1}\equiv\frac{\mathbf{x}^{k+1}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}\mbox{
for any }k\geq 0\mbox{ and }\mathbf{w}^{0}=\mathbf{x}^{0}.$

From the definitions of $\mathbf{w}^{k+1}$ and $\mathbf{y}^{k}$ in (11a), we
have the following easy-to-identify identities.

###### Lemma 10

For procedure (11a)-(11c), we have

$\displaystyle\begin{aligned}
&\theta_{k}\mathbf{x}^{*}+(1-\theta_{k})\mathbf{x}^{k}-\mathbf{y}^{k}=\theta_{k}\left(\mathbf{x}^{*}-\mathbf{w}^{k}\right),\\\
&\theta_{k}\mathbf{x}^{*}+(1-\theta_{k})\mathbf{x}^{k}-\mathbf{x}^{k+1}=\theta_{k}\left(\mathbf{x}^{*}-\mathbf{w}^{k+1}\right).\end{aligned}$
(25)

We use the same notations of $\rho_{k+1}$ and $\mathbf{w}^{k}$ with Section
III-B for easy analogy. Different from Section III-B, we define a new variable

$\mathbf{v}^{k,t}\equiv\frac{\mathbf{z}^{k,t}}{\theta_{k}}-\frac{1-\theta_{k}}{\theta_{k}}\mathbf{x}^{k}.$
(26)

The proof of Theorem 3 is based on the following Lyapunov function

$\displaystyle\begin{aligned}
&\ell_{k+1}=\frac{\rho_{k+1}}{\theta_{k}}+\frac{1}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}\\\
&+\left(\frac{L\theta_{k+1}}{2}+\frac{\beta_{0}}{2}\right)\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}+\frac{M}{2\sqrt{1-\sigma_{2}(W)}}\|\mathbf{v}^{k+1,0}-\mathbf{x}^{*}\|_{F}^{2}.\end{aligned}$

Analogy to Lemma 9, we give the following lemma, which describes a progress in
one iteration of Algorithm 2.

###### Lemma 11

Assume that Assumptions 1, 2 and 3 hold with $\mu=0$. Let sequences
$\\{\theta_{k}\\}$ and $\\{\vartheta_{k}\\}$ satisfy $\theta_{0}=1$,
$\frac{1-\theta_{k}}{\theta_{k}}=\frac{1}{\theta_{k-1}}$, and
$\vartheta_{k}=\theta_{k}$. Assume the following equation holds

$\frac{\theta_{k}}{\eta_{k}T_{k}}=\frac{M}{\sqrt{1-\sigma_{2}(W)}}.$ (27)

Then, for Algorithm 2, we have

$\ell_{k+1}\leq\ell_{k}+\frac{mM^{2}\eta_{k}}{2\theta_{k}}.$ (28)

The proof of Lemma 11 is based on the following lemma.

###### Lemma 12

Assume that Assumptions 1 and 3 hold. Define
$\widetilde{\mathbf{x}}^{k,*}=(1-\theta_{k})\mathbf{x}^{k}+\theta_{k}\mathbf{x}^{*}$.
Then, for Algorithm 2, we have

$\displaystyle\begin{aligned} &\rho_{k+1}-(1-\theta_{k})\rho_{k}\\\
\leq&\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
&+h(\mathbf{x}^{k+1})-h(\widetilde{\mathbf{x}}^{k,*})+\left\langle\lambda^{*},U\mathbf{x}^{k+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle.\end{aligned}$

###### Proof 9

From (LABEL:cont5) with $\mu=0$, we have

$\displaystyle\begin{aligned} &f(\mathbf{x}^{k+1})\leq
f(\mathbf{x})+\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\mathbf{x}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}.\end{aligned}$

Firstly let $\mathbf{x}=\mathbf{x}^{k}$ and then $\mathbf{x}=\mathbf{x}^{*}$,
we obtain two inequalities. Multiplying the first inequality by
$(1-\theta_{k})$, multiplying the second by $\theta_{k}$, and adding them
together, we have

$\displaystyle\begin{aligned}
&f(\mathbf{x}^{k+1})-(1-\theta_{k})f(\mathbf{x}^{k})-\theta_{k}f(\mathbf{x}^{*})\\\
\leq&\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}.\end{aligned}$

Adding
$h(\mathbf{x}^{k+1})-(1-\theta_{k})h(\mathbf{x}^{k})-\theta_{k}h(\mathbf{x}^{*})+\left\langle\lambda^{*},U\mathbf{x}^{k+1}-(1-\theta_{k})U\mathbf{x}^{k}\right\rangle$
to both sides, and using the definition of $\rho_{k}$, we have

$\displaystyle\begin{aligned} &\rho_{k+1}-(1-\theta_{k})\rho_{k}\\\
=&F(\mathbf{x}^{k+1})-(1-\theta_{k})F(\mathbf{x}^{k})-\theta_{k}F(\mathbf{x}^{*})\\\
&+\left\langle\lambda^{*},U\mathbf{x}^{k+1}-(1-\theta_{k})U\mathbf{x}^{k}\right\rangle\\\
\leq&\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
&+h(\mathbf{x}^{k+1})-(1-\theta_{k})h(\mathbf{x}^{k})-\theta_{k}h(\mathbf{x}^{*})\\\
&+\left\langle\lambda^{*},U\mathbf{x}^{k+1}-(1-\theta_{k})U\mathbf{x}^{k}\right\rangle.\end{aligned}$
(29)

From the definition of $\widetilde{\mathbf{x}}^{k,*}$, $U\mathbf{x}^{*}=0$,
and the convexity of $h(\mathbf{x})$, we have

$\displaystyle\begin{aligned}
&\mathbf{x}^{k+1}-\widetilde{\mathbf{x}}^{k,*}=\mathbf{x}^{k+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*},\\\
&U\mathbf{x}^{k+1}-U\widetilde{\mathbf{x}}^{k,*}=U\mathbf{x}^{k+1}-(1-\theta_{k})U\mathbf{x}^{k},\\\
&h(\widetilde{\mathbf{x}}^{k,*})\leq(1-\theta_{k})h(\mathbf{x}^{k})+\theta_{k}h(\mathbf{x}^{*}).\end{aligned}$

Plugging them into (LABEL:cont7), we have the conclusion. $\Box$

Now, we give the proof of Lemma 11.

###### Proof 10

From the fact that $h(\mathbf{x})$ is $(\sqrt{m}M)$-Lipchitz continuous
derived by Assumption 2, similar to the induction in (LABEL:cont5), we have

$\displaystyle\begin{aligned} &h(\mathbf{z}^{k,t+1})\\\
\leq&h(\mathbf{z}^{k,t})+\left\langle\hat{\nabla}h(\mathbf{z}^{k,t}),\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\right\rangle+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}\\\
=&h(\mathbf{z}^{k,t})+\left\langle\hat{\nabla}h(\mathbf{z}^{k,t}),\widetilde{\mathbf{x}}^{k,*}-\mathbf{z}^{k,t}\right\rangle\\\
&+\left\langle\hat{\nabla}h(\mathbf{z}^{k,t}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}\\\
\leq&h(\widetilde{\mathbf{x}}^{k,*})+\left\langle\hat{\nabla}h(\mathbf{z}^{k,t}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F},\end{aligned}$
(30)

where $\widetilde{\mathbf{x}}^{k,*}$ is defined in Lemma 12 and
$\hat{\nabla}h(\mathbf{z}^{k,t})\in\partial h(\mathbf{z}^{k,t})$. On the other
hand, from the update role of $\mathbf{z}^{k,t+1}$ in Algorithm 2, we have

$\displaystyle\begin{aligned} 0=&\hat{\nabla}h(\mathbf{z}^{k,t})+\nabla
f(\mathbf{y}^{k})+\frac{\beta_{0}}{\vartheta_{k}}U^{2}\mathbf{y}^{k}\\\
&+\left(L+\frac{\beta_{0}}{\vartheta_{k}}\right)(\mathbf{z}^{k,t+1}-\mathbf{y}^{k})+\frac{1}{\eta_{k}}(\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}).\end{aligned}$
(31)

Thus, we have

$\displaystyle\begin{aligned} &\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\frac{L}{2}\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
&+h(\mathbf{z}^{k,t+1})-h(\widetilde{\mathbf{x}}^{k,*})+\left\langle\lambda^{*},U\mathbf{z}^{k,t+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
\overset{a}{\leq}&\left\langle\nabla
f(\mathbf{y}^{k})+\hat{\nabla}h(\mathbf{z}^{k,t}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\left\langle\lambda^{*},U\mathbf{z}^{k,t+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
&+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}+\frac{L}{2}\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
\overset{b}{=}&-\left\langle\frac{\beta_{0}}{\vartheta_{k}}U^{2}\mathbf{y}^{k}+\left(L+\frac{\beta_{0}}{\vartheta_{k}}\right)(\mathbf{z}^{k,t+1}-\mathbf{y}^{k})\right.\\\
&\hskip
55.48277pt\left.+\frac{1}{\eta_{k}}(\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
&+\left\langle\lambda^{*},U\mathbf{z}^{k,t+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}\\\
&+\frac{L}{2}\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
=&-\left\langle\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{y}^{k}-\lambda^{*},U\mathbf{z}^{k,t+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
&-\left(L+\frac{\beta_{0}}{\vartheta_{k}}\right)\left\langle\mathbf{z}^{k,t+1}-\mathbf{y}^{k},\mathbf{y}^{k}-\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
&-\frac{1}{\eta_{k}}\left\langle\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t},\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
&+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}-\left(\frac{L}{2}+\frac{\beta_{0}}{\vartheta_{k}}\right)\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
\overset{c}{=}&-\frac{\vartheta_{k}}{\beta_{0}}\left\langle\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{y}^{k}-\lambda^{*},\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{z}^{k,t+1}-\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}\right\rangle\\\
&-\left(L+\frac{\beta_{0}}{\vartheta_{k}}\right)\left\langle\mathbf{z}^{k,t+1}-\mathbf{y}^{k},\mathbf{y}^{k}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\right\rangle\\\
&-\frac{1}{\eta_{k}}\left\langle\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t},\mathbf{z}^{k,t+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\right\rangle\\\
&+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}-\left(\frac{L}{2}+\frac{\beta_{0}}{\vartheta_{k}}\right)\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2},\end{aligned}$

where we use (LABEL:cont8) in $\overset{a}{\leq}$, (31) in $\overset{b}{=}$,
$\frac{1}{\vartheta_{k-1}}=\frac{1-\theta_{k}}{\vartheta_{k}}$, and the
definition of $\widetilde{\mathbf{x}}^{k,*}$ in $\overset{c}{=}$. Applying the
identities in Lemma 1 to the two inner products, using
$\frac{\vartheta_{k}}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{y}^{k}-\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{z}^{k,t+1}\right\|_{F}^{2}\leq\frac{\beta_{0}}{2\vartheta_{k}}\|\mathbf{y}^{k}-\mathbf{z}^{k,t+1}\|_{F}^{2}$
and dropping the negative term
$-\frac{\vartheta_{k}}{2\beta_{0}}\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{y}^{k}-\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}\right\|_{F}^{2}$,
we have

$\displaystyle\begin{aligned} &\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{z}^{k,t+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\frac{L}{2}\|\mathbf{z}^{k,t+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
&+h(\mathbf{z}^{k,t+1})-h(\widetilde{\mathbf{x}}^{k,*})+\left\langle\lambda^{*},U\mathbf{z}^{k,t+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
\leq&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{z}^{k,t+1}-\lambda^{*}\right\|_{F}^{2}\right]\\\
&+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\left[\|\mathbf{y}^{k}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
71.13188pt\left.-\|\mathbf{z}^{k,t+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&+\frac{1}{2\eta_{k}}\left[\|\mathbf{z}^{k,t}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
34.14322pt\left.-\|\mathbf{z}^{k,t+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&+\sqrt{m}M\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}-\frac{1}{2\eta_{k}}\|\mathbf{z}^{k,t+1}-\mathbf{z}^{k,t}\|_{F}^{2}\\\
\overset{d}{\leq}&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{z}^{k,t+1}-\lambda^{*}\right\|_{F}^{2}\right]\\\
&+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\left[\|\mathbf{y}^{k}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
71.13188pt\left.-\|\mathbf{z}^{k,t+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&+\frac{1}{2\eta_{k}}\left[\|\mathbf{z}^{k,t}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
34.14322pt\left.-\|\mathbf{z}^{k,t+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]+\frac{mM^{2}\eta_{k}}{2},\end{aligned}$

where we use $-\frac{a}{2}t^{2}+bt\leq\frac{b^{2}}{2a}$ for any $a>0$ in
$\overset{d}{\leq}$. Summing over $t=0,\cdots,T_{k}-1$ and dividing both sides
by $T_{k}$, letting
$\mathbf{x}^{k+1}=\frac{\sum_{t=0}^{T_{k}-1}\mathbf{z}^{k,t+1}}{T_{k}}$, and
from the convexity of $h(\mathbf{x})$ and $\|\cdot\|_{F}^{2}$, we have

$\displaystyle\begin{aligned} &\left\langle\nabla
f(\mathbf{y}^{k}),\mathbf{x}^{k+1}-\widetilde{\mathbf{x}}^{k,*}\right\rangle+\frac{L}{2}\|\mathbf{x}^{k+1}-\mathbf{y}^{k}\|_{F}^{2}\\\
&+h(\mathbf{x}^{k+1})-h(\widetilde{\mathbf{x}}^{k,*})+\left\langle\lambda^{*},U\mathbf{x}^{k+1}-U\widetilde{\mathbf{x}}^{k,*}\right\rangle\\\
\leq&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}\right]\\\
&+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\left[\|\mathbf{y}^{k}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
71.13188pt\left.-\|\mathbf{x}^{k+1}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&+\frac{1}{2\eta_{k}T_{k}}\left[\|\mathbf{z}^{k,0}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right.\\\
&\hskip
42.67912pt\left.-\|\mathbf{z}^{k,T_{k}}-(1-\theta_{k})\mathbf{x}^{k}-\theta_{k}\mathbf{x}^{*}\|_{F}^{2}\right]+\frac{mM^{2}\eta_{k}}{2}\\\
\overset{e}{=}&\frac{\vartheta_{k}}{2\beta_{0}}\left[\left\|\frac{\beta_{0}}{\vartheta_{k-1}}U\mathbf{x}^{k}-\lambda^{*}\right\|_{F}^{2}-\left\|\frac{\beta_{0}}{\vartheta_{k}}U\mathbf{x}^{k+1}-\lambda^{*}\right\|_{F}^{2}\right]\\\
&+\left(\frac{L}{2}+\frac{\beta_{0}}{2\vartheta_{k}}\right)\theta_{k}^{2}\left[\|\mathbf{w}^{k}-\mathbf{x}^{*}\|_{F}^{2}-\|\mathbf{w}^{k+1}-\mathbf{x}^{*}\|_{F}^{2}\right]\\\
&+\frac{\theta_{k}^{2}}{2\eta_{k}T_{k}}\left[\|\mathbf{v}^{k,0}-\mathbf{x}^{*}\|_{F}^{2}-\|\mathbf{v}^{k+1,0}-\mathbf{x}^{*}\|_{F}^{2}\right]+\frac{mM^{2}\eta_{k}}{2},\end{aligned}$

where $\overset{e}{=}$ follows from the identities in Lemma LABEL:iden_dng,
the definition of $\mathbf{v}^{k,t}$ in (26), and
$\mathbf{z}^{k+1,0}=\mathbf{z}^{k,T_{k}}$. Dividing both sides by $\theta_{k}$
and letting $\vartheta_{k}=\theta_{k}$, from Lemma 12,
$\frac{1}{\theta_{k-1}}=\frac{1-\theta_{k}}{\theta_{k}}$,
$\frac{\theta_{k}}{2\eta_{k}T_{k}}=\frac{M}{2\sqrt{1-\sigma_{2}(W)}}$,
$\theta_{k+1}\leq\theta_{k}$, and the definition of $\ell_{k}$, we have the
conclusion. $\Box$

Based on Lemma 11, we can prove Theorem 3.

###### Proof 11

The settings of $T_{k}=K(1-\sigma_{2}(W))$ and
$\eta_{k}=\frac{\theta_{k}}{KM\sqrt{1-\sigma_{2}(W)}}$ satisfy (27). Plugging
them into (28), we have

$\ell_{k+1}\leq\ell_{k}+\frac{mM}{2K\sqrt{1-\sigma_{2}(W)}}.$

Summing over $k=0,\cdots,K-1$, we have

$\displaystyle\begin{aligned}
\ell_{K}\leq&\ell_{0}+\frac{mM}{2\sqrt{1-\sigma_{2}(W)}}\\\
=&\frac{1}{2\beta_{0}}\|\lambda^{*}\|_{F}^{2}+\frac{L+\beta_{0}}{2}\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}^{2}\\\
&+\frac{M}{2\sqrt{1-\sigma_{2}(W)}}\|\mathbf{x}^{0}-\mathbf{x}^{*}\|_{F}^{2}+\frac{mM}{2\sqrt{1-\sigma_{2}(W)}}\\\
\equiv&C_{12},\end{aligned}$

where we use $\theta_{0}=1$,
$\frac{1}{\theta_{-1}}=\frac{1-\theta_{0}}{\theta_{0}}=0$,
$\mathbf{w}^{0}=\mathbf{x}^{0}$, and $\mathbf{v}^{0,0}=\mathbf{x}^{0}$.
Similar to the proofs of Theorems 4 and 5, from the definition of $\ell_{k}$
and $\theta_{k-1}=\frac{1}{k}$, we have

$\displaystyle\begin{aligned}
&\|U\mathbf{x}^{K}\|_{F}\leq\frac{1}{\beta_{0}K}\left(\sqrt{2\beta_{0}C_{12}}+\|\lambda^{*}\|_{F}\right),\\\
&F(\mathbf{x}^{K})-F(\mathbf{x}^{*})\leq\frac{C_{12}}{K}+\|\lambda^{*}\|_{F}\|U\mathbf{x}^{K}\|_{F}\end{aligned}$

and $\|\mathbf{x}^{K}-\mathbf{x}^{*}\|_{F}^{2}\leq\frac{2C_{12}}{\beta_{0}}$.
Similar to (LABEL:cont13), we also have

$\displaystyle\begin{aligned}
&F\left(\alpha(\mathbf{x}^{K})\right)-F(\mathbf{x}^{*})\\\
\overset{a}{\leq}&\left(\|\nabla
f(\mathbf{x}^{*})\|+L\sqrt{\frac{2C_{12}}{\beta_{0}}}\right)\|\Pi\mathbf{x}^{K}\|_{F}+\frac{L}{2}\|\Pi\mathbf{x}^{K}\|_{F}^{2}\\\
&+2\sqrt{m}M\|\Pi\mathbf{x}^{K}\|_{F}+F(\mathbf{x}^{K})-F(\mathbf{x}^{*}),\end{aligned}$

where we use the fact that $h(\mathbf{x})$ is $(\sqrt{m}M)$-Lipchitz
continuous in $\overset{a}{\leq}$, i.e,
$\|\widetilde{\nabla}h(\mathbf{x})\|_{F}\leq\sqrt{m}M,\forall\widetilde{\nabla}h(\mathbf{x})\in\partial
h(\mathbf{x})$. From Lemma 4, we can further bound $\|\Pi\mathbf{x}^{K}\|_{F}$
by $\frac{\|U\mathbf{x}^{K}\|_{F}}{\sqrt{1-\sigma_{2}(W)}}$. From Lemma 2, we
know $\|\lambda^{*}\|_{F}\leq\frac{\sqrt{m}M+\|\nabla
f(\mathbf{x}^{*})\|_{F}}{\sqrt{1-\sigma_{2}(W)}}\equiv\frac{1}{\chi}$. From
the setting of $\beta_{0}$, we have
$\beta_{0}\geq\frac{L}{\sqrt{1-\sigma_{2}(W)}}\geq L$ and
$\beta_{0}\geq\frac{M}{\sqrt{1-\sigma_{2}(W)}}$. Combing with (13) and
$R_{1}\geq 1$, we have
$\frac{1}{\chi}\leq\sqrt{m}\beta_{0}\left(R_{1}+\frac{R_{2}}{L}\right)$ and

$\displaystyle\begin{aligned}
&C_{12}\leq\frac{1}{2\beta_{0}\chi^{2}}+\frac{3\beta_{0}mR_{1}^{2}}{2}+\frac{\beta_{0}m}{2}\leq
2.5\beta_{0}m\left(R_{1}+\frac{R_{2}}{L}\right)^{2},\\\
&\|U\mathbf{x}^{K}\|_{F}\leq\frac{1}{K}\left(\sqrt{5m}\left(R_{1}+\frac{R_{2}}{L}\right)+\frac{1}{\chi\beta_{0}}\right)\leq\frac{4\sqrt{m}}{K}\left(R_{1}+\frac{R_{2}}{L}\right),\\\
&\|\Pi\mathbf{x}^{K}\|_{F}\leq\frac{4\beta_{0}\sqrt{m}}{KL}\left(R_{1}+\frac{R_{2}}{L}\right),\|\Pi\mathbf{x}^{K}\|_{F}\leq\frac{4\beta_{0}\sqrt{m}}{KM}\left(R_{1}+\frac{R_{2}}{L}\right),\\\
&F(\mathbf{x}^{K})-F(\mathbf{x}^{*})\leq\frac{7\beta_{0}m}{K}\left(R_{1}+\frac{R_{2}}{L}\right)^{2}.\end{aligned}$

Thus, we further have

$\displaystyle\begin{aligned}
&F\left(\alpha(\mathbf{x}^{K})\right)-F(\mathbf{x}^{*})\\\
\leq&\left(\sqrt{m}R_{2}+L\left(R_{1}+\frac{R_{2}}{L}\right)\sqrt{5m}\right)\frac{4\beta_{0}\sqrt{m}}{KL}\left(R_{1}+\frac{R_{2}}{L}\right)\\\
&+\frac{8\beta_{0}m}{K^{2}\sqrt{1-\sigma_{2}(W)}}\left(R_{1}+\frac{R_{2}}{L}\right)^{2}+2\sqrt{m}\frac{4\beta_{0}\sqrt{m}}{K}\left(R_{1}+\frac{R_{2}}{L}\right)\\\
&+\frac{7\beta_{0}m}{K}\left(R_{1}+\frac{R_{2}}{L}\right)^{2}\\\
\leq&\left(\frac{31\beta_{0}m}{K}+\frac{8\beta_{0}m}{K^{2}\sqrt{1-\sigma_{2}(W)}}\right)\left(R_{1}+\frac{R_{2}}{L}\right)^{2}.\end{aligned}$

The proof is complete. $\Box$

Similar to the proof of Theorem 3, in the following, we give the proof of
Corollary 1.

###### Proof 12

The settings of $T_{k}=\frac{1-\sigma_{2}(W)}{\theta_{k}}$ and
$\eta_{k}=\frac{\theta_{k}^{2}}{M\sqrt{1-\sigma_{2}(W)}}$ satisfy (27).
Plugging them into (28) and using $\theta_{k}=\frac{1}{k+1}$, we have

$\ell_{k+1}\leq\ell_{k}+\frac{mM}{2(k+1)\sqrt{1-\sigma_{2}(W)}}.$

Summing over $k=0,\cdots,K-1$, we have

$\ell_{K}\leq\ell_{0}+\frac{mM(\log K+1)}{\sqrt{1-\sigma_{2}(W)}}.$

Similar to the proof of Theorem 3, we have the conclusion. $\Box$

##  IV Numerical Experiments

###  IV-A Smooth Problem

We test the performance of the proposed algorithms on the following least
square regression problem

$\displaystyle\min_{x\in\mathbb{R}^{n}}\sum_{i=1}^{m}f_{i}(x)\quad\mbox{with}\quad
f_{i}(x)\equiv\frac{1}{2}\|A_{i}^{T}x-b_{i}\|^{2}+\frac{\mu}{2}\|x\|^{2}.$
(32)

We generate $A_{i}\in\mathbb{R}^{n\times N/m}$ from the uniform distribution
with each entry in $[0,1]$ and normalize each column of $A_{i}$ to be 1, where
$N$ is the sample size. We set $N=1000$, $n=500$, $m=100$, and
$b_{i}=A_{i}^{T}x$ with some $x$ generated from the Gaussian distribution. We
consider both the strongly convex objective ($\mu>0$) and nonstrongly convex
objective ($\mu=0$).

|
---|---
Figure 1: Comparisons on the strongly convex problem (32) and Erdős$-$Rényi random network with $p=0.5$ (left two), $p=0.1$ (middle two), and $p=0.05$ (right two). |
---|---
Figure 2: Comparisons on the nonstrongly convex problem (32) and Erdős$-$Rényi
random network with $p=0.5$ (left two), $p=0.1$ (middle two), and $p=0.05$
(right two).

We consider the Erdős$-$Rényi random graph where each pair of agents has a
connection with the probability of $p$. Almost all Erdős$-$Rényi random graph
with $p=\frac{2\log m}{m}$ is connected and $\frac{1}{1-\sigma_{2}(W)}=O(1)$
[34, Proposition 5]. We test the performance with $p=0.5$, $p=0.1$, and
$p=0.05$, and observe that $1-\sigma_{2}(W)=0.33$, $1-\sigma_{2}(W)=0.13$, and
$1-\sigma_{2}(W)=0.04$, respectively. We set $W=\frac{I+M}{2}$, where $M$ is
the Metropolis weight matrix [53].

For the strongly convex objective, we compare APM-C with the accelerated dual
ascent (ADA) [12], distributed Nesterov’s gradient descent (DNGD) [7], EXTRA
[20], and NEAR-DGD+ [22]. NEAR-DGD+ can be seen as a counterpart of APM-C
without Nesterov’s acceleration scheme and accelerated average consensus. We
set $\mu=0.0001$ and leave the test on different condition numbers in our
supplementary material. We set the inner iteration number $T_{k}$ as
$\lceil\frac{k\sqrt{\mu/L}}{3\sqrt{1-\sigma_{2}(W)}}\rceil$, $\beta_{0}=100$
and the stepsize as $\frac{1}{L}$ for APM-C, where $\lceil\cdot\rceil$ means
the top integral function. For ADA, we follow the theory in [9] to set the
inner iteration number as $\lceil\sqrt{\frac{L}{\mu}}\log\frac{L}{\mu}\rceil$
(we leave the test on the impact of smaller inner iteration numbers in our
supplementary material) and the stepsize as $\mu$. We tune the best stepsize
as $\frac{1}{L}$ and $\frac{0.5}{L}$ for EXTRA and DNGD, respectively. We
follow [22] to set $T_{k}=k$ for NEAR-DGD+. We initialize $\mathbf{x}^{0}$ at
$0$ for all the compared methods.

Figure 1 plots the comparisons. We can see that APM-C has the lowest
computation cost and ADA has the lowest communication cost, which match the
theory. Thus, APM-C is more suited to the environment where computation is the
bottleneck of the overall performance. Due to the large $T_{k}$ for ADA, it
only performs several outer iterations after $3000$ gradient computations and
thus has almost no decreasing in the first, third and fifth plots of Figure 1.
APM-C has a higher communication cost than DNGD but a lower computation cost
for $p=0.1$ and $p=0.5$. APM-C performs better than NEAR-DGD+ and it verifies
that Nesterov’s acceleration scheme is critical to improve the performance.
From Figure 1, we observe that APM-C is more suited to the network with small
$\frac{1}{\sqrt{1-\sigma_{2}(W)}}$, otherwise, the communication costs will be
high, e.g., see the right two plots in Figure 1. In fact, when
$\frac{1}{\sqrt{1-\sigma_{2}(W)}}$ is small,
$\frac{\sqrt{\mu/L}}{\sqrt{1-\sigma_{2}(W)}}$ will also be small, e.g., $0.01$
in our experiment with $p=0.1$. Thus the required $T_{k}$ is small, e.g.,
$T_{3000}=11$ in our experiment. As a comparison, NEAR-DGD+ suggests $T_{k}=k$
and thus it increases quickly, which leads to almost no decreasing in the
second, fourth and sixth plots of Figure 1. In practice, we can use the
expander graph [54] which satisfies $\frac{1}{1-\sigma_{2}(W)}=O(1)$ [34]. The
Erdős$-$Rényi random graph is a special case of the expander graph and can be
easily implemented.

For the nonstrongly convex objective, we test the performance of APM, APM-C,
D-NG [8], D-NC [8], DNGD [7], EXTRA [20] and ADA [9]. We set $T_{k}$ as
$\lceil\frac{\log(k+1)}{5\sqrt{1-\sigma_{2}(W)}}\rceil$ and
$\lceil\frac{\log(k+1)}{-5\log\sigma_{2}(W)}\rceil$ for APM-C and D-NC,
respectively. We set the stepsize as $\frac{1}{L}$ for the two algorithms and
$\beta_{0}=100$ for APM-C. We set
$\frac{\beta_{0}}{\vartheta_{k}}=\frac{k+1}{c}$ with $c=50$ for APM and tune
the best $c=1$ for D-NG. Larger $c$ makes D-NG diverge. We tune the best
stepsize as $\frac{1}{L}$ for EXTRA, $\frac{0.05}{L}$ for DNGD with $p=0.05$,
$\frac{0.1}{L}$ for DNGD with $p=0.1$, and $\frac{0.2}{L}$ for DNGD with
$p=0.5$, respectively. For ADA, we follow [9] to add a small regularizer of
$\frac{\epsilon}{2}\|\mathbf{x}\|^{2}$ to each $f_{i}(\mathbf{x})$ and solve a
regularized problem with $\epsilon=10^{-7}$. We set the inner iteration number
as $T_{k}=\lceil\sqrt{\frac{L}{\epsilon}}\log\frac{L}{\epsilon}\rceil$.

|
---|---
Figure 3: Comparisons on the nonsmooth problem (33) and Erdős$-$Rényi random
network with $p=0.5$ (left two), $p=0.1$ (middle two), and $p=0.05$ (right
two).

From figure 2, we can see that APM-C also has the lowest computation cost. APM
performs better than D-NG because APM allows to use a larger stepsize in
practice, which can reduce the negative impacts from the diminishing stepsize.
APM is more suited to the environment where high precision is not required,
otherwise, the diminishing stepsize makes the algorithm slow. ADA has the
lowest communication cost. However, ADA needs to predefine $\epsilon$ to set
the algorithm parameter and thus it only achieves an approximate optimal
solution in the precision of $\epsilon$ due to the weakness of the
regularization trick. From Figure 2, we can see that the value of
$\frac{1}{\sqrt{1-\sigma_{2}(W)}}$ has less impact on the performance of APM-C
than that in the strongly convex setting.

###  IV-B Non-smooth Problem

In this section, we follow [25] to test Algorithm 2 on the following
decentralized linear Support Vector Machine (SVM) model

$\displaystyle\min_{x\in\mathbb{R}^{n}}\sum_{i=1}^{m}f_{i}(x)\quad\mbox{with}\quad
f_{i}(x)\equiv\max\\{0,1-b_{i}A_{i}^{T}x\\}.$ (33)

The problem setting is similar to Section IV-A and the only difference is that
we set $b_{i}=\mbox{Sign}(A_{i}^{T}x)$ for some $\mathbf{x}$ generated from
the Gaussian distribution. We also consider the Erdős$-$Rényi random graph
with $p=0.05$, $p=0.1$, and $p=0.5$, respectively. We compare APM with the
primal-dual method [11]. We test two different parameter settings for APM. For
the first one, we follow Corollary 1 to set
$\beta_{0}=\frac{0.01}{\sqrt{1-\sigma_{2}(W)}}$, $T_{k}=\lceil
k(1-\sigma_{2}(W))\rceil$, and
$\eta_{k}=\frac{5000}{k^{2}\sqrt{1-\sigma_{2}(W)}}$, and name it APM with
adaptive parameters (APM-adp). For the second one, we follow Theorem 3 to set
$\beta_{0}=\frac{0.01}{\sqrt{1-\sigma_{2}(W)}}$, $T_{k}=\lceil
K(1-\sigma_{2}(W))\rceil$, and
$\eta_{k}=\frac{5000}{kK\sqrt{1-\sigma_{2}(W)}}$ with $K=300$ and name it APM
with fix parameters (APM-fix). For the primal-dual method, we set the number
of inner iterations as $\lceil K(1-\sigma_{2}(W))\rceil$ and tune the best
parameters of $\sigma=1$ and $\eta=0.5$ in [11, Alg 3]. Figure 3 plots the
result. We can see that APM performs better than the primal-dual method, and
APM-adp needs less communications and subgradient computations than APM-adp.

##  V Conclusion

In this paper, we study the distributed accelerated gradient methods from the
perspective of the accelerated penalty method with increasing penalty
parameters. Two algorithms are proposed. The first algorithm achieves the
optimal gradient computation complexities and near optimal communication
complexities for both strongly convex and nonstrongly convex smooth
distributed optimization. Our communication complexities are only worse by a
factor of $\log\frac{1}{\epsilon}$ than the lower bounds. Our second algorithm
obtains both the optimal subgradient computation and communication
complexities for nonsmooth distributed optimization. Our APM-C is not suited
to the network with large $\frac{1}{\sqrt{1-\sigma_{2}(W)}}$ for strongly
convex problems, in which case the communication cost is high.

## References

  * [1] J. Bazerque and G. Giannakis, “Distributed spectrum for cognitive radio networks by exploiting sparsity,” IEEE transactions on Signal Processing, vol. 58, no. 3, pp. 1847–1862, 2010.
  * [2] S. Ram, V. Veeravalli, and A. Nedic, “Distributed non-autonomous power control through distributed convex optimization,” in International Conference on Computer Communications (INFOCOM), pp. 3001–3005, 2009.
  * [3] W. Ren, “Consensus based formation control strategies for multi-vehicle systems,” in American Control Conference (ACC), pp. 4237–4242, 2006.
  * [4] O. Dekel, R. Gilad-Bachrach, O. Shamir, and L. Xiao, “Optimal distributed online prediction using mini-batches,” Journal of Machine Learning Research, vol. 13, pp. 165–202, 2012.
  * [5] P. Forero, A. Cano, and G. Giannakis, “Consensus-based distributed support vector machines,” Journal of Machine Learning Research, vol. 59, pp. 1663–1707, 2010.
  * [6] A. Agarwal and J. Duchi, “Distributed delayed stochastic optimization,” in Advances in Neural Information Processing Systems (NIPS), pp. 873–881, 2011\.
  * [7] G. Qu and N. Li, “Accelerated distributed Nesterov gradient descent,” IEEE Transactions on Automatic Control, vol. 65, no. 6, pp. 2566–2581, 2020\.
  * [8] D. Jakovetić, J. Xavier, and J. M. F. Moura, “Fast distributed gradient methods,” IEEE Transactions on Automatic Control, vol. 59, no. 5, pp. 1131–1146, 2014.
  * [9] C. A. Uribe, S. Lee, A. Gasnikov, and A. Nedić, “A dual approach for optimal algorithms in distributed optimization over networks,” arXiv:1809.00710, 2018.
  * [10] Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course.  Kluwer Academic, Boston, 2004.
  * [11] K. Scaman, F. Bach, S. Bubeck, Y. Lee, and L. Massoulié, “Optimal convergence rates for convex distributed optimization in networks,” Journal of Machine Learning Research, vol. 20, pp. 1–31, 2019.
  * [12] K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié, “Optimal algorithms for smooth and strongly convex distributed optimization in networks,” in International Conference on Machine Learning (ICML), pp. 3027–3036, 2017.
  * [13] K. Scaman, F. Bach, S. Bubeck, Y. T. Lee, and L. Massoulié, “Optimal algorithms for non-smooth distributed optimization in networks,” in Advances in Neural Information Processing Systems (NeurIPS), pp. 2740–2749, 2018\.
  * [14] A. Nedić and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
  * [15] A. Nedić, “Asynchronous broadcast-based convex optimization over a network,” IEEE Transactions on Automatic Control, vol. 56, no. 6, pp. 1337–1351, 2011.
  * [16] S. Ram, A. Nedic̀, and V. V. Veeravalli, “Distributed stochastic subgradient projection algorithms for convex optimization,” Journal of Optimization Theory and Applications, vol. 147, pp. 516–545, 2010.
  * [17] J. Xu, S. Zhu, Y. C. Soh, and L. Xie, “Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes,” in IEEE Conference on Decision and Control (CDC), pp. 2055–2060, 2015.
  * [18] G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2018.
  * [19] A. Nedić, A. Olshevsky, and W. Shi, “Achieving geometric convergence for distributed optimization over time-varying graphs,” SIAM Journal on Optimization, vol. 27, no. 4, pp. 2597–2633, 2017.
  * [20] W. Shi, Q. Ling, G. Wu, and W. Yin, “EXREA: An exact first-order algorithm for decentralized consensus optimization,” SIAM Journal Optimization, vol. 25, no. 2, pp. 944–966, 2015.
  * [21] W. Shi, Q. Ling, G. Wu, and W. Yin, “A proximal gradient algorithm for decentralized composite optimization,” IEEE Transactions on Signal Processing, vol. 63, no. 23, pp. 6013–6023, 2015.
  * [22] A. Berahas, R. Bollapragada, N. Keskar, and E. Wei, “Balancing communication and computation in distributed optimization,” IEEE Transactions on Automatic Control, vol. 64, no. 8, pp. 3141–3155, 2019.
  * [23] H. Terelius, U. Topcu, and R. Murray, “Decentralized multi-agent optimization via dual decomposition,” IFAC proceedings volumes, vol. 44, no. 1, pp. 11245–11251, 2011.
  * [24] H. Yu and M. Neely, “On the convergence time of dual subgradient methdos for strongly convex programs,” IEEE Transactions on Automatic Control, vol. 63, no. 4, pp. 1105–1112, 2018.
  * [25] G. Lan, S. Lee, and Y. Zhou, “Communication-efficient algorithms for decentralized and stochastic optimization,” Mathematical Programming, vol. 180, pp. 237–284, 2020.
  * [26] T. Erseghe, D. Zennaro, E. Dall’Anese, and L. Vangelista, “Fast consensus by the alternating direction multipliers method,” IEEE Transactions on Signal Processing, vol. 59, no. 11, pp. 5523–5537, 2011.
  * [27] W. Shi, Q. Ling, G. Wu, and W. Yin, “On the linear convergence of the ADMM in decentralized consensus optimization,” IEEE Transactions on Signal Processing, vol. 62, no. 2, pp. 1750–1761, 2014.
  * [28] E. Wei and A. Ozdaglar, “On the $o(1/k)$ convergence of asynchronous distributed alternating direction method of multipliers,” in IEEE Global Conference on Signal and Information Processing (GlobalSIP), pp. 551–554, 2013.
  * [29] F. Iutzeler, P. Bianchi, P. Ciblat, and W. Hachem, “Explicit convergence rate of a distributed alternating direction method of multipliers,” IEEE Transactions on Automatic Control, vol. 61, no. 4, pp. 892–904, 2016.
  * [30] A. Makhdoumi and A. Ozdaglar, “Convergence rate of distributed ADMM over networks,” IEEE Transactions on Automatic Control, vol. 62, no. 10, pp. 5082–5095, 2017.
  * [31] N. Aybat, Z. Wang, T. Lin, and S. Ma, “Distributed linearized alternating direction method of multipliers for composite convex consensus optimization,” IEEE Transactions on Automatic Control, vol. 63, no. 1, pp. 5–20, 2018.
  * [32] A. Chambolle and T. Pock, “A first-order primal-dual algorithm for convex problems with applications to imaging,” Journal of Mathematical Imaging and Vision, vol. 40, pp. 120–145, 2011.
  * [33] M. Arioli and J. Scott, “Chebyshev acceleration of iterative refinement,” Numerical Algorithms, vol. 66, no. 3, pp. 591–608, 2014.
  * [34] A. Nedić, A. Olshevsky, and M. Rabbat, “Network topology and communication-computation tradeoffs in decentralized optimization,” Proceedings of the IEEE, vol. 106, no. 5, pp. 953–976, 2018.
  * [35] M. Hong, D. Hajinezhad, and M.-M. Zhao, “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.
  * [36] D. Jakovetić, “A unification and generatliztion of exact distributed first order methods,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 1, pp. 31–46, 2019.
  * [37] K. Yuan, Q. Ling, and W. Yin, “On the convergence of decentralized gradient descent,” SIAM Journal Optimization, vol. 26, no. 3, pp. 1835–1854, 2016\.
  * [38] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM Journal on Imaging Sciences, vol. 2, no. 1, pp. 183–202, 2009.
  * [39] L. Xiao and S. Boyd, “Fast linear iterations for distributed averaging,” Systems and Control Letters, vol. 53, no. 1, pp. 65–78, 2004.
  * [40] J. Liu and A. S. Morse, “Accelerated linear iterations for distributed averaging,” Annual Reviews in Control, vol. 35, no. 2, pp. 160–165, 2011\.
  * [41] T. Zhang and H. Yu, “Average consensus for directed networks of multi-agent with time-varying delay,” in International Conference in Swarm Intelligence (ICSI), pp. 723–730, 2010.
  * [42] G. Lan, “Gradient sliding for composite optimization,” Mathematical Programming, vol. 159, pp. 201–235, 2016.
  * [43] G. Lan and Y. Ouyang, “Accelerated gradient sliding for structured convex optimization,” preprint arXiv:1609.04905, 2016.
  * [44] G. Lan and Y. Zhou, “Conditional gradient sliding for convex optimization,” SIAM Journal on Optimization, vol. 26, no. 2, pp. 1379–1409, 2016.
  * [45] G. Lan and R. D. Monteiro, “Iteration-complexity of first-order penalty methods for convex programming,” Mathematical Programming, vol. 138, pp. 115–139, 2013.
  * [46] I. Necoara, A. Patrascu, and F. Glineur, “Complexity of first-order inexact Lagrangian and penalty methods for conic convex programming,” Optimization Methods and Software, vol. 34, no. 2, pp. 305–335, 2019.
  * [47] Y. Nesterov, “A method for unconstrained convex minimization problem with the rate of convergence ${O}(1/k^{2})$,” Doklady AN SSSR, vol. 269, pp. 543–547, 1983.
  * [48] Y. Nesterov, “On an approach to the construction of optimal methods of minimization of smooth convex functions,” Èkonomika I Mateaticheskie Metody, vol. 24, pp. 509–517, 1988.
  * [49] O. Devolder, F. Glineur, and Y. Nesterov, “First-order methods of smooth convex optimization with inexact oracle,” Mathematical Programming, vol. 146, pp. 37–75, 2014.
  * [50] M. Schmidt, N. L. Roux, and F. R. Bach, “Convergence rates of inexact proximal-gradient methods for convex optimization,” in Advances in Neural Information Processing Systems (NIPS), pp. 1458–1466, 2011.
  * [51] Y. Nesterov, “Smooth minimization of non-smooth functions,” Mathematical Programming, vol. 103, pp. 127–152, 2005.
  * [52] H. Li and Z. Lin, “Accelerated alternating direction method of multipliers: an optimal ${O}(1/{K})$ nonergodic analysis,” Journal of Scientific Computing, vol. 79, pp. 671–699, 2019.
  * [53] S. Boyd, P. Diaconis, and L. Xiao, “Fastest mixing markov chain on a graph,” SIAM Review, vol. 46, no. 4, pp. 667–689, 2004.
  * [54] Y. Chow, W. Shi, T. Wu, and W. Yin, “Expander graph and communication-efficient decentralized optimization,” in Asilomar Conference on Signals, Systems and Computers (ACSSC), pp. 1715–1720, 2016.