$\displaystyle\leq{\textstyle\sqrt{\frac{\Phi^{0}-\underline{\Phi}}{r}}}\bigg{(}\frac{1}{\beta\sqrt{C_{3}}}+\frac{\sigma_{2}\sqrt{a_{2}}\lambda_{\max}}{\sqrt{C_{2}}}+\frac{\sigma_{2}\sqrt{a_{4}}}{\sqrt{\alpha}}\bigg{)},$
(K.79)

where $\underline{\Phi}$ is the lower bound of $\sum_{r=0}^{T}\Phi^{r+1}$ for
any iteration $T$, $\lambda_{\max}$ is the largest eigenvalue of
${\bm{L}}^{+}$, $\sigma_{2}$ and $a_{2}$ are defined in Lemma 4 and Lemma 5
respectively, and $C_{2}$ and $C_{3}$ are in Lemma 8 of the revised
manuscript.

Since $C_{2}\geq\frac{\rho}{2}$ shown in the proof of Lemma 8(a), the second
term of the above upper bound can be simplified as
$\frac{\sigma_{2}\sqrt{a_{2}}\lambda_{\max}}{\sqrt{C_{2}}}\leq\frac{\sqrt{2\rho
a_{2}}\sigma_{2}\lambda_{\max}}{\rho}$. Further inserting values of $C_{3}$,
$\sigma_{2}$, $a_{2},a_{4}$ defined in Lemmas 8, 4, 5, and 7, respectively, we
obtain

$\displaystyle\|{\bm{z}}^{t}-{\bm{x}}({\bm{z}}^{t})\|$
$\displaystyle\leq{\textstyle\sqrt{\frac{\Phi^{0}-\underline{\Phi}}{r}}}\bigg{\\{}\frac{1}{\beta\sqrt{p\left(-\frac{1}{2}+\frac{1}{\beta}-\frac{20p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho}-\frac{\rho(\sigma_{1}^{2}+2\sigma_{2}^{2}a_{3})}{10p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}\right)}}\bigg{.}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\bigg{.}+\frac{\sqrt{2\rho}}{\rho}\cdot\frac{B_{\max}(p+\gamma^{+}+1)}{p+\gamma^{-}}\cdot\theta_{1}\sqrt{\frac{\theta_{1}^{2}}{\rho^{2}}\left(\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\right)^{2}+2}\cdot\lambda_{\max}\bigg{.}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\bigg{.}+\frac{B_{\max}(p+\gamma^{+}+1)}{p+\gamma^{-}}\cdot\theta_{3}\sqrt{\frac{1}{2}\left[\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\right]^{2}\theta_{3}^{2}+\frac{1}{\rho^{2}}}\cdot\frac{1}{\sqrt{\alpha}}\bigg{\\}}.$
(K.80)

    * a)

_Choose parameter $\beta,p,\rho,\alpha$._

Let

$\displaystyle\beta=\frac{1}{2\left(\frac{1}{2}+\frac{20p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho}+\frac{\rho(\sigma_{1}^{2}+2\sigma_{2}^{2}a_{3})}{10p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}\right)},$
(K.81) $\displaystyle p=\rho=-2\gamma^{-},$ (K.82)
$\displaystyle\alpha=\min\left\\{\frac{\rho}{5},\frac{\rho}{8a_{1}\lambda_{\max}^{2}}\right\\}.$
(K.83)

    * b)

_Inserting $p,\rho,\alpha$ into ((1))_ followed by making square, we have

$\displaystyle\|{\bm{z}}^{t}-{\bm{x}}({\bm{z}}^{t})\|^{2}$
$\displaystyle\leq\frac{\Phi^{0}-\underline{\Phi}}{r}\left\\{D_{1}B_{\max}\lambda_{\max}\sqrt{D_{2}\theta_{1}^{4}+D_{3}\theta_{1}^{2}}\right.$
$\displaystyle~{}~{}~{}\left.+\sqrt{D_{4}+B_{\max}^{2}\lambda_{\max}^{2}(D_{5}\theta_{1}^{4}+D_{6}\theta_{1}^{2})+\frac{D_{7}+D_{8}B_{\max}^{2}\theta_{2}^{2}}{B_{\max}^{2}\lambda_{\max}^{2}(D_{9}\theta_{1}^{4}+D_{10}\theta_{1}^{2})}}\right.$
$\displaystyle~{}~{}~{}\left.+D_{11}B_{\max}\theta_{3}\sqrt{D_{12}\theta_{3}^{2}+D_{13}}\cdot\max\\{D_{14},\lambda_{\max}\sqrt{D_{15}\theta_{1}^{2}+D_{16}}\\}\right\\}^{2},$
(K.84)

where $D_{1}$-$D_{16}$ are positive constants related to
$\gamma^{+},\gamma^{-}$.

  * (2)

Determine $\theta_{1},\theta_{2},\theta_{3}$ by Hoffman bound:

Notation: For a matrix $\bar{{\bf M}}$, define $\sigma_{\max}(\bar{{\bf M}})$
to be the largest singular value of $\bar{{\bf M}}$ and define
$\sigma_{\min}(\bar{{\bf M}})$ to be the smallest nonzero singular value of
$\bar{{\bf M}}$.

We can give an upper bound of the Hoffman constant
$\theta_{1},\theta_{2},\theta_{3}$. Specializing Lemma 3.2.3 in [54] to the
case where the linear system is defined only by linear equality, we have the
following Lemma:

###### Lemma 14

Let $S=\\{{\bm{x}}\in\mathbb{R}^{n}\mid{\bf M}{\bm{x}}={\bm{v}}\\}$ be a
linear system. Then for any $\bar{{\bm{x}}}\in\mathbb{R}^{n}$, the distance
from $\bar{{\bm{x}}}$ to the set $S$ is bounded as:

$\mathrm{dist}(\bar{{\bm{x}}},S)\leq\frac{\sigma_{\max}(\bar{{\bf
M}})}{\sigma^{2}_{\min}(\bar{{\bf M}})}\|{\bf M}\bar{{\bm{x}}}-{\bm{v}}\|,$

where $\bar{{\bf M}}$ is any submatrix whose rows span the row space of ${\bf
M}$. $\blacksquare$

Recall in the proof of Lemma 5 that KKT conditions (F.51)-(F.52) form a linear
system of $\rho\bar{{\bm{y}}}^{r}$, with fixed
$\\{{\bm{x}}_{i}(\bar{{\bm{y}}}_{i}^{r},{\bm{z}}_{i}^{r})\\}_{i=1}^{N}$ as
follows

$\displaystyle\underbrace{\begin{bmatrix}{\bm{L}}^{-}\\\
{\bm{B}}^{T}_{\mathrm{diag}}\end{bmatrix}}_{\triangleq{\bf
M}_{1}}\rho\bar{{\bm{y}}}^{r}={\bm{u}}_{1},$ (K.85)

where ${\bm{u}}_{1}$ is the corresponding vector defined by (F.51)-(F.52) and
${\bm{B}}_{\mathrm{diag}}\triangleq\mathrm{diag}({\bm{B}}_{1},\cdots,{\bm{B}}_{N})$.
Then, by Lemma 14, we have $\theta_{1}$ in Lemma 5 is $\theta_{1}=\theta({\bf
M}_{1})=\sigma_{\max}({\bf M}_{1})/\sigma_{\min}^{2}({\bf M}_{1})$. Moreover,
since the proof of Lemma 6 is based on the same linear system, we obtain
$\theta_{1}=\theta_{2}$.

Similarly, to prove Lemma 7, KKT conditions (H.65)-(H.67) can be viewed as a
linear system of variables $\rho\bar{{\bm{y}}}^{r}$ and ${\bm{\mu}}^{r+1}$

$\displaystyle\underbrace{\begin{bmatrix}{\bm{A}}^{\top}&{\bm{L}}^{-}\\\
\mathbf{0}&{\bm{A}}\\\
\mathbf{0}&{\bm{B}}^{T}_{\mathrm{diag}}\end{bmatrix}}_{\triangleq{\bf
M}_{2}}\begin{bmatrix}{\bm{\mu}}^{r+1}\\\
\rho\bar{{\bm{y}}}^{r}\end{bmatrix}={\bm{u}}_{2},$ (K.86)

where ${\bm{u}}_{2}$ is the corresponding vector defined by (H.65)-(H.67).
Therefore, we obtain $\theta_{3}=\theta({\bf M}_{2})=\sigma_{\max}({\bf
M}_{2})/\sigma_{\min}^{2}({\bf M}_{2})$.

Notice that ${\bf M}_{1}$ and ${\bf M}_{2}$ are related to the network
topology and the data matrix ${\bm{B}}$. In general, we cannot write
$\theta_{1},\theta_{2},\theta_{3}$ in terms of the eigenvalues of
${\bm{L}}^{-}$. However, if ${\bm{B}}=[{\bm{B}}_{1},\cdots,{\bm{B}}_{N}]$ is
of full row rank, we can write $\theta_{1},\theta_{2},\theta_{3}$ concerning
the singular values of ${\bm{L}}^{-}$.

Next, for ${\bf M}_{1}$ and ${\bf M}_{2}$, we obtain their lower bound of
$\sigma_{\min}$ and the upper bound of $\sigma_{\max}$, respectively by the
following two Lemmas.

###### Lemma 15

If ${\bm{B}}$ is of full row rank, we have

$\displaystyle\sigma_{\min}({\bf
M}_{1})\geq\max\left\\{\frac{\sigma_{\min}({\bm{L}}^{-})}{1+\zeta_{B}},\frac{\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{2(1+\zeta_{B})}\right\\}.$
(K.87) $\displaystyle\sigma_{\min}({\bf
M}_{2})\geq\frac{\max\left\\{\frac{\sqrt{\sigma_{\min}({\bm{L}}^{-})}}{1+\zeta_{B}},\frac{\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{2(1+\zeta_{B})}\right\\}}{3+\sqrt{\sigma_{\max}({\bm{L}}^{-})}},$
(K.88)

where
$\zeta_{B}\triangleq\frac{2\sqrt{N}\cdot\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{\sigma_{\min}({\bm{B}})}$.

Proof: See Appendix L. $\blacksquare$

###### Lemma 16

We have

$\displaystyle\sigma_{\max}({\bf
M}_{1})\leq\sigma_{\max}({\bm{L}}^{-})+\sigma_{\max}({\bm{B}}_{\mathrm{diag}}),$
(K.89) $\displaystyle\sigma_{\max}({\bf M}_{2})\leq
2\sqrt{\sigma_{\max}({\bm{L}}^{-})}+\sigma_{\max}({\bm{L}}^{-})+\sigma_{\max}({\bm{B}}_{\mathrm{diag}}).$
(K.90)

Proof: See Appendix N. $\blacksquare$

Thus, combining these bounds and Lemma 14 yields the desired bound for
$\theta_{1},\theta_{2}$ and $\theta_{3}$ as shown below

$\displaystyle\theta_{1}=\theta_{2}\leq\frac{\sigma_{\max}({\bm{L}}^{-})+\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{\max\left\\{\left(\frac{\sigma_{\min}({\bm{L}}^{-})}{1+\zeta_{B}}\right)^{2},\left(\frac{\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{2(1+\zeta_{B})}\right)^{2}\right\\}}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\overset{\mathrm{(i)}}{\leq}(1+\zeta_{B})^{2}\frac{\sigma_{\max}({\bm{L}}^{-})}{\sigma_{\min}^{2}({\bm{L}}^{-})}+\frac{4(1+\zeta_{B})^{2}}{\sigma_{\max}({\bm{B}}_{\mathrm{diag}})},$
(K.91)
$\displaystyle\theta_{3}\leq\frac{2\sqrt{\sigma_{\max}({\bm{L}}^{-})}+\sigma_{\max}({\bm{L}}^{-})+\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{\frac{\max\left\\{\frac{\sigma_{\min}({\bm{L}}^{-})}{(1+\zeta_{B})^{2}},\frac{\sigma_{\max}^{2}({\bm{B}}_{\mathrm{diag}})}{4(1+\zeta_{B})^{2}}\right\\}}{(3+\sqrt{\sigma_{\max}({\bm{L}}^{-})})^{2}}}$
$\displaystyle~{}~{}~{}\overset{\mathrm{(ii)}}{\leq}\frac{\left(2\sqrt{\sigma_{\max}({\bm{L}}^{-})}+\sigma_{\max}({\bm{L}}^{-})\right)(3+\sqrt{\sigma_{\max}({\bm{L}}^{-})})^{2}(1+\zeta_{B})^{2}}{\sigma_{\min}({\bm{L}}^{-})}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}+\frac{4(1+\zeta_{B})^{2}}{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}\left(3+\sqrt{\sigma_{\max}({\bm{L}}^{-})}\right)^{2}$ (K.92)

where $\zeta_{B}\triangleq\frac{2\sqrt{N}\cdot\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{\sigma_{\min}({\bm{B}})}$, $\mathrm{(i)}$ and $\mathrm{(ii)}$ are due
to the fact that $\frac{a+b}{\max\\{c,d\\}}\leq\frac{a}{c}+\frac{b}{d}$.

  * (3)

Determine the dependence on topology of convergence rate:

Combining (b)) , ((2)), ((2)), we obtain the result in Corollary 1.
$\blacksquare$

##  Appendix L Proof of Lemma 15

  * a)

_Solve the lower bound for $\sigma_{\min}({\bf M}_{1})$_

Let ${\bm{v}}\in\mathbb{R}^{NM}$ be a vector. We write
${\bm{v}}={\bm{v}}_{1}+{\bm{v}}_{2}$, where ${\bm{v}}_{1}$ is in the null
space of ${\bm{L}}^{-}$ and ${\bm{v}}_{2}$ is orthogonal to ${\bm{v}}_{1}$.
Then, ${\bm{L}}^{-}{\bm{v}}_{1}=\mathbf{0}$.

Recall
$\zeta_{B}\triangleq\frac{2\sqrt{N}\cdot\sigma_{\max}({\bm{B}}_{\mathrm{diag}})}{\sigma_{\min}({\bm{B}})}$.
Then, we can divide into it two cases to analyze the lower bound of
$\sigma_{\min}({\bf M}_{1})$.

Case 1. If $\|{\bm{v}}_{1}\|\leq\zeta_{B}\|{\bm{v}}_{2}\|$, we have

$\displaystyle\|{\bf M}_{1}{\bm{v}}\|$
$\displaystyle\geq\|{\bm{L}}^{-}{\bm{v}}\|\overset{\mathrm{(i)}}{=}\|{\bm{L}}^{-}{\bm{v}}_{2}\|\overset{\mathrm{(ii)}}{\geq}\sigma_{\min}({\bm{L}}^{-})\|{\bm{v}}_{2}\|\overset{\mathrm{(iii)}}{\geq}\frac{\sigma_{\min}({\bm{L}}^{-})\|{\bm{v}}\|}{1+\zeta_{B}},$
(L.93)

where $\mathrm{(i)}$ is because of ${\bm{L}}^{-}{\bm{v}}_{1}=\mathbf{0}$,
$\mathrm{(ii)}$ is due to the definition of the smallest singular value
$\sigma_{\min}$, and $\mathrm{(iii)}$ is obtained by triangle inequality and
the assumption $\|{\bm{v}}_{1}\|\leq\zeta_{B}\|{\bm{v}}_{2}\|$, i.e.,
$\|{\bm{v}}\|=\|{\bm{v}}_{1}+{\bm{v}}_{2}\|\leq\|{\bm{v}}_{1}\|+\|{\bm{v}}_{2}\|\leq(1+\zeta_{B})\|{\bm{v}}_{2}\|$.

Case 2. Suppose $\|{\bm{v}}_{1}\|\geq\zeta_{B}\|{\bm{v}}_{2}\|$. Notice that
${\bm{v}}_{1}=[{\bm{y}}^{\top},{\bm{y}}^{\top},\cdots,{\bm{y}}^{\top}]^{\top}\in\mathbb{R}^{NM}$
for some ${\bm{y}}\in\mathbb{R}^{M}$. We have

$\displaystyle\|{\bf M}_{1}{\bm{v}}\|$
$\displaystyle\geq\|{\bm{B}}^{\top}_{{\rm diag}}{\bm{v}}\|$
$\displaystyle=\|{\bm{B}}^{\top}_{{\rm
diag}}{\bm{v}}_{1}+{\bm{B}}^{\top}_{{\rm diag}}{\bm{v}}_{2}\|$
$\displaystyle\overset{\mathrm{(i)}}{\geq}\|{\bm{B}}^{\top}_{{\rm
diag}}{\bm{v}}_{1}\|-\|{\bm{B}}^{\top}_{{\rm diag}}{\bm{v}}_{2}\|$
$\displaystyle\geq\|{\bm{B}}^{\top}{\bm{y}}\|-\sigma_{\max}({\bm{B}}_{{\rm
diag}})\|{\bm{v}}_{2}\|$
$\displaystyle\overset{\mathrm{(ii)}}{\geq}\sigma_{\min}({\bm{B}})\|{\bm{y}}\|-\sigma_{\max}({\bm{B}}_{{\rm
diag}})\cdot\frac{1}{\zeta_{B}}\|{\bm{v}}_{1}\|$
$\displaystyle\overset{\mathrm{(iii)}}{=}\sigma_{\min}({\bm{B}})\frac{1}{\sqrt{N}}\|{\bm{v}}_{1}\|-\sigma_{\min}({\bm{B}})\frac{1}{2\sqrt{N}}\|{\bm{v}}_{1}\|$
$\displaystyle=\sigma_{\min}({\bm{B}})\frac{1}{\sqrt{N}}\|{\bm{v}}_{1}\|$
$\displaystyle\overset{\mathrm{(iv)}}{\geq}\frac{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{2\zeta_{B}}\|{\bm{v}}_{1}\|,$
$\displaystyle\overset{\mathrm{(v)}}{\geq}\frac{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{2(1+\zeta_{B})}\|{\bm{v}}\|,$ (L.94)

where $\mathrm{(i)}$ is by triangular inequality, $\mathrm{(ii)}$ is because
of assumption $\|{\bm{v}}_{1}\|\geq\zeta_{B}\|{\bm{v}}_{2}\|$,
$\mathrm{(iii)}$ and $\mathrm{(iv)}$ are both due to the definition of
$\zeta_{B}$, and $\mathrm{(v)}$ is obtained by triangle inequality and
assumption $\|{\bm{v}}_{1}\|\geq\zeta_{B}\|{\bm{v}}_{2}\|$, i.e.,
$\|{\bm{v}}\|=\|{\bm{v}}_{1}+{\bm{v}}_{2}\|\leq\|{\bm{v}}_{1}\|+\|{\bm{v}}_{2}\|\leq(1+1/\zeta_{B})\|{\bm{v}}_{1}\|$.

Thus, we have

$\displaystyle\sigma_{\min}({\bf
M}_{1})\geq\max\left\\{\frac{\sigma_{\min}({\bm{L}}^{-})}{1+\zeta_{B}},\frac{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{2(1+\zeta_{B})}\right\\}.$ (L.95)

  * b)

_Solve the lower bound for $\sigma_{\min}({\bf M}_{2})$_

Before solving $\sigma_{\min}({\bf M}_{2})$, we give the following lemmas.

###### Lemma 17

For block matrix
$\hat{{\bm{C}}}=[{\bm{C}}_{1}^{\top},{\bm{C}}_{2}^{\top}]^{\top}$ and
$\tilde{{\bm{C}}}=[{\bm{C}}_{3},{\bm{C}}_{4}]$, we have the following
conclusions.

$\displaystyle\sigma_{\max}(\hat{{\bm{C}}})\leq\sigma_{\max}({\bm{C}}_{1})+\sigma_{\max}({\bm{C}}_{2}).$
(L.96)
$\displaystyle\sigma_{\max}(\tilde{{\bm{C}}})\leq\sigma_{\max}({\bm{C}}_{3})+\sigma_{\max}({\bm{C}}_{4}).$
(L.97)

Proof: See Appendix M. $\blacksquare$

Let ${\bm{P}}=\begin{bmatrix}\mathbf{I}&-{\bm{A}}^{\top}&\mathbf{0}\\\
\mathbf{0}&\mathbf{I}&\mathbf{0}\\\
\mathbf{0}&\mathbf{0}&\mathbf{I}\end{bmatrix}$. Then ${\bm{P}}{\bf
M}_{2}=\begin{bmatrix}{\bm{A}}^{\top}&\mathbf{0}\\\ \mathbf{0}&{\bm{A}}\\\
\mathbf{0}&{\bm{B}}_{{\rm diag}}^{\top}\end{bmatrix}$. Since ${\bm{P}}$ is
nonsingular, the null space of ${\bf M}_{2}$ is equal to that of ${\bm{P}}{\bf
M}_{2}$. Therefore, any ${\bm{v}}$ orthogonal to the null space of ${\bf
M}_{2}$ is also orthogonal to the null space of ${\bm{P}}{\bf M}_{2}$.

Pick ${\bm{v}}$ satisfying $\|{\bf M}_{2}{\bm{v}}\|=\sigma_{\min}({\bf
M}_{2})\|{\bm{v}}\|$. We then have

$\displaystyle\sigma_{\min}({\bm{P}}{\bf M}_{2})\|{\bm{v}}\|\leq\|{\bm{P}}{\bf
M}_{2}{\bm{v}}\|\leq\sigma_{\max}({\bm{P}})\|{\bf
M}_{2}{\bm{v}}\|=\sigma_{\max}({\bm{P}})\sigma_{\min}({\bf
M}_{2})\|{\bm{v}}\|.$ (L.98)

Therefore,

$\displaystyle\sigma_{\min}({\bf M}_{2})\geq\frac{\sigma_{\min}({\bm{P}}{\bf
M}_{2})}{\sigma_{\max}({\bm{P}})}.$ (L.99)

By Lemma 17, we have $\sigma_{\max}({\bm{P}})\leq
3+\sqrt{\sigma_{\max}({\bm{L}}^{-})}$.

Moreover, by viewing ${\bm{P}}{\bf M}_{2}$ as a block diagonal matrix, it is
obvious that $\sigma_{\min}({\bm{P}}{\bf M}_{2})$
$=\min\\{\sigma_{\min}({\bm{A}}),$ $\sigma_{\min}({\bf M}_{3})\\}$, where
${\bf M}_{3}\triangleq[{\bm{A}}^{\top},{\bm{B}}_{{\rm diag}}]^{\top}$. Since
${\bm{L}}^{-}={\bm{A}}^{\top}{\bm{A}}$, then we can easily prove that
$\text{Null}({\bm{L}}^{-})=\text{Null}({\bm{A}})$. Then, the lower bound of
$\sigma_{\min}({\bm{P}}{\bf M}_{2})$ can be solved by following the similar
method to solve that of $\sigma_{\min}({\bf M}_{1})$. Thus, we have

$\displaystyle\sigma_{\min}({\bf
M}_{3})\geq\max\left\\{\frac{\sqrt{\sigma_{\min}({\bm{L}}^{-})}}{1+\zeta_{B}},\frac{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{2(1+\zeta_{B})}\right\\}.$ (L.100)

Then, by inserting (L.98) and (L.100) into (L.99), we have

$\displaystyle\sigma_{\min}({\bf M}_{2})$
$\displaystyle\geq\frac{\max\left\\{\frac{\sqrt{\sigma_{\min}({\bm{L}}^{-})}}{1+\zeta_{B}},\frac{\sigma_{\max}({\bm{B}}_{{\rm
diag}})}{2(1+\zeta_{B})}\right\\}}{3+\sqrt{\sigma_{\max}({\bm{L}}^{-})}}.$
(L.101)

$\blacksquare$

##  Appendix M Proof of Lemma 17

  * (a)

For any vector ${\bm{v}}$,

$\displaystyle\left\|\hat{{\bm{C}}}{\bm{v}}\right\|$
$\displaystyle=\left\|\begin{bmatrix}{\bm{C}}_{1}{\bm{v}}\\\
{\bm{C}}_{2}{\bm{v}}\end{bmatrix}\right\|\leq\|{\bm{C}}_{1}{\bm{v}}\|+\|{\bm{C}}_{1}{\bm{v}}\|\leq\left(\sigma_{\max}({\bm{C}}_{1})+\sigma_{\max}({\bm{C}}_{2})\right)\|{\bm{v}}\|.$
(M.102)

Therefore, we have
$\sigma_{\max}(\hat{{\bm{C}}})\leq\sigma_{\max}({\bm{C}}_{1})+\sigma_{\max}({\bm{C}}_{2})$.

  * (b)

Notice that
$\tilde{{\bm{C}}}=[{\bm{C}}_{3}^{\top},{\bm{C}}_{4}^{\top}]^{\top}$. Then
$\sigma_{\max}(\tilde{{\bm{C}}})=\sigma_{\max}([{\bm{C}}_{3}^{\top},{\bm{C}}_{4}^{\top}]^{\top})$
by the fact that $\sigma_{\max}({\bf E})=\sigma_{\max}({\bf E}^{\top})$ for
any ${\bf E}$. From (L.96), we have
$\sigma_{\max}([{\bm{C}}_{3}^{\top},{\bm{C}}_{4}^{\top}]^{\top})\leq\sigma_{\max}({\bm{C}}_{3})+\sigma_{\max}({\bm{C}}_{4})$.

Thus, we have
$\sigma_{\max}(\tilde{{\bm{C}}})\leq\sigma_{\max}({\bm{C}}_{3})+\sigma_{\max}({\bm{C}}_{4})$.
$\blacksquare$

##  Appendix N Proof of Lemma 16

The bounds for $\sigma_{\max}({\bf M}_{1})$ and $\sigma_{\max}({\bf M}_{2})$
can be easily obtained by applying Lemma 14. $\blacksquare$

##  Appendix O Proof of Corollary 2

Recalling the upper bound in (1),

$\displaystyle\|{\bm{z}}^{t}-{\bm{x}}({\bm{z}}^{t})\|^{2}$
$\displaystyle\leq\textstyle\frac{\Phi^{0}-\underline{\Phi}}{r}\textstyle\left(D_{1}B_{\max}^{2}\lambda_{\max}\sqrt{D_{2}\theta_{1}^{4}+D_{3}\theta_{1}^{2}}\right.$
$\displaystyle~{}~{}~{}\left.+\sqrt{D_{4}+\textstyle
B_{\max}^{2}\lambda_{\max}^{2}(D_{5}\theta_{1}^{4}+D_{6}\theta_{1}^{2})\textstyle+\textstyle\frac{D_{7}+D_{8}B_{\max}^{2}\theta_{2}^{2}}{B_{\max}^{2}\lambda_{\max}^{2}(D_{9}\theta_{1}^{4}+D_{10}\theta_{1}^{2})}}\right.$
$\displaystyle~{}~{}~{}\left.\textstyle+\textstyle
D_{11}B_{\max}\theta_{1}\sqrt{D_{12}\theta_{3}^{2}+D_{13}}\right.$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}\left.\times\max\bigg{\\{}D_{14},\sqrt{D_{15}\lambda_{\max}^{2}\theta_{1}^{2}+D_{16}}\bigg{\\}}\right)^{2},$
(O.103)

there are four terms to be analyzed, including $\lambda_{\max}$, $\theta_{1}$,
$\theta_{2}$ and $\theta_{3}$.

  * a)

$\lambda_{\max}$:  Notice that the degree of each node in the cycle graph is
always 2. Then, by [55, Theorem 4.6], we have $\lambda_{\max}\leq
2\max_{i\in[N]}d_{i}=4$, where $d_{i}$ denotes the degree of node $i$. It
means that the upper bound $\lambda_{\max}\leq 4$ is independent of network
size $N$ and connectivity.

  * b)

$\theta_{1}$, $\theta_{2}$, $\theta_{3}$:  By [56, Lemma 3.7.1], the
eigenvalues of ${\bm{L}}^{-}$ for the cycle graph are $2-2\cos(2\pi k/N)$ with
$k=0,1,\ldots,N/2$. Then, the largest eigenvalue is
$\sigma_{\max}({\bm{L}}^{-})=2$.

Since $2-2\cos(2\pi k/N)$ is an monotonically increasing function with respect
to $k$, then the smallest nonzero eigenvalue is attained at $k=1$. Therefore,
we have

$\displaystyle\sigma_{\min}({\bm{L}}^{-})=2-2\cos\left(\frac{2\pi}{N}\right)=2\left(\frac{\left(\frac{2\pi}{N}\right)^{2}}{2}+o\left(\left(\frac{2\pi}{N}\right)^{2}\right)\right)=\frac{4\pi^{2}}{N^{2}}+2\times
o\left(\frac{4\pi^{2}}{N^{2}}\right),$ (O.104)

where $o\left(\frac{4\pi^{2}}{N^{2}}\right)$ is the high-order infinitely
small quantities of $\frac{4\pi^{2}}{N^{2}}$. Then, when $N$ increases,
$\sigma_{\min}({\bm{L}}^{-})$ decreases.

Recall $\theta_{1}$, $\theta_{2}$, $\theta_{3}$ in (32) and (33),

$\displaystyle\textstyle\theta_{1}=\theta_{2}\leq\textstyle(1+\zeta_{B})^{2}\frac{\sigma_{\max}({\bm{L}}^{-})}{\sigma_{\min}^{2}({\bm{L}}^{-})}+\frac{4(1+\zeta_{B})^{2}}{\sigma_{\max}({\bm{B}}_{\mathrm{diag}})},$
$\displaystyle\textstyle\theta_{3}\leq\textstyle\frac{\left(2\sqrt{\sigma_{\max}({\bm{L}}^{-})}+\sigma_{\max}({\bm{L}}^{-})\right)(3+\sqrt{\sigma_{\max}({\bm{L}}^{-})})^{2}(1+\zeta_{B})^{2}}{\sigma_{\min}({\bm{L}}^{-})}$
$\displaystyle~{}~{}~{}~{}~{}~{}~{}~{}~{}+\textstyle\frac{4(1+\zeta_{B})^{2}}{\sigma_{\max}^{2}({\bm{B}}_{\mathrm{diag}})}\left(3+\sqrt{\sigma_{\max}({\bm{L}}^{-})}\right)^{2}.$

Obviously, after inserting $\sigma_{\max}({\bm{L}}^{-})=2$, the decreases of
$\sigma_{\min}({\bm{L}}^{-})$ leads to the rise of $\theta_{1}$, $\theta_{2}$,
and $\theta_{3}$. Therefore, $\theta_{1}$, $\theta_{2}$, and $\theta_{3}$
increases with $N$.

By further inserting $\lambda_{\max}\leq 4$, one can conclude that the right
hand side of (1) increases with $N$. Since for the cycle graph, the increase
of $N$ implies poorer connectivity, it implies that the convergence speed may
be degraded when the network connectivity decreases.

##  Appendix P Proof of Theorem 2

For the inexact case, since for agent $i$ the inexact solution
${\bm{x}}_{i}^{r+1}$ is not equal to
${\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r})$ anymore, then we have
different upper bounds for ${\mathcal{L}}_{\rho}$, $\tilde{G}$, and
perturbation of ${\bm{y}}$ from those in the exact PDC case.

###  P.1 Upper bound for ${\mathcal{L}}_{\rho}$

###### Lemma 18

For the AL function in (3.2),we have

$\displaystyle-{\mathcal{L}}_{\rho}({\bm{y}}^{r+1},{\bm{\mu}}^{r+1};{\bm{z}}^{r+1})+{\mathcal{L}}_{\rho}({\bm{y}}^{r},{\bm{\mu}}^{r};{\bm{z}}^{r})$
$\displaystyle\leq{\sf(A1)}-\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}_{\rho{\bm{L}}^{+}}-\frac{\rho}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}$
$\displaystyle~{}~{}~{}+{\sf(A2)}+\frac{B_{\max}^{2}}{2}\sum_{i=1}^{N}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r})\|^{2}+\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}.$
(P.105)

Proof of Lemma 18: For proving the descent of $-{\mathcal{L}}_{\rho}$, the
IPDC algorithm differs from its exact counterpart (Lemma 1) only in the update
of ${\bm{y}}$, as shown below.

Bound of
$-{\mathcal{L}}_{\rho}({\bm{y}}^{r+1},{\bm{\mu}}^{r+1};{\bm{z}}^{r})+{\mathcal{L}}_{\rho}({\bm{y}}^{r},{\bm{\mu}}^{r+1};{\bm{z}}^{r})$:
Rewrite (B.8) explicitly, we have

$\displaystyle\begin{bmatrix}{\bm{B}}_{1}{\bm{x}}_{1}({\bm{y}}_{1}^{r+1},{\bm{z}}_{i}^{r})\\\
\vdots,\\\
{\bm{B}}_{N}{\bm{x}}_{N}({\bm{y}}_{N}^{r+1},{\bm{z}}_{i}^{r})\end{bmatrix}-{\bm{q}}/N-{\bm{A}}^{\top}{\bm{\mu}}-\rho{\bm{A}}^{\top}{\bm{A}}{\bm{y}}-\rho{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})={\bm{0}}.$
(P.106)

Then, by the optimality condition of (19b) and applying (P.106), we have

$\displaystyle{\mathcal{L}}_{\rho}({\bm{y}}^{r},{\bm{\mu}}^{r+1};{\bm{z}}^{r})-\frac{1}{2}\|{\bm{y}}^{r}-{\bm{y}}^{r}\|_{\rho{\bm{L}}^{+}}^{2}$
$\displaystyle\leq\sum_{i=1}^{N}{\langle}{\bm{B}}_{i}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r})),{\bm{y}}_{i}^{r+1}-{\bm{y}}_{i}^{r}{\rangle}+{\mathcal{L}}_{\rho}({\bm{y}}^{r+1},{\bm{\mu}}^{r+1};{\bm{z}}^{r})-\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|_{\rho{\bm{L}}^{+}}^{2}$
$\displaystyle~{}~{}~{}-\frac{\rho}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}$
$\displaystyle\leq\frac{B_{\max}^{2}}{2}\sum_{i=1}^{N}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r})\|^{2}+\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}+{\mathcal{L}}_{\rho}({\bm{y}}^{r+1},{\bm{\mu}}^{r+1};{\bm{z}}^{r})-\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|_{\rho{\bm{L}}^{+}}^{2}$
$\displaystyle~{}~{}~{}-\frac{\rho}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}$
(P.107)

Summing (B.7), (P.107) and (B.11) leads to the desired result. $\blacksquare$

###  P.2 Upper bound for $\tilde{G}$

###### Lemma 19

We have

$\displaystyle\tilde{G}_{r+1}({\bm{x}}^{r+1},{\bm{y}}^{r+1},{\bm{\mu}}^{r+1};{\bm{z}}^{r+1})-\tilde{G}_{r}({\bm{x}}^{r},{\bm{y}}^{r},{\bm{\mu}}^{r};{\bm{z}}^{r})$
$\displaystyle\leq{-\frac{1}{\alpha}\|{\bm{\mu}}^{r+1}-{\bm{\mu}}^{r}\|^{2}}-\sum_{i=1}^{N}\frac{p+\gamma^{-}}{2}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|^{2}-\frac{1}{2}\|({\bm{y}}^{r}-{\bm{y}}^{r-1})-({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}_{\rho{\bm{L}}^{+}}$
$\displaystyle~{}~{}~{}-\bigg{(}\frac{\rho}{2}-\frac{\alpha}{2}\bigg{)}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}_{{\bm{L}}^{-}}+\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}_{\rho{\bm{L}}^{+}}+\frac{p}{2}(1-\frac{2}{\beta})\|{\bm{z}}^{r+1}-{\bm{z}}^{r}\|^{2}$
$\displaystyle~{}~{}~{}+\sum_{i=1}^{N}(-\frac{1}{\zeta}+\frac{p+\gamma^{+}}{2})\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|^{2}.$
(P.108)

Proof of Lemma 19: The only difference for proving the descent of $\tilde{G}$
between the PDC algorithm (Lemma 11) and the IPDC algorithm is the bound of
$G({\bm{x}}^{r+1},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})-G({\bm{x}}^{r},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})$:
Define

$H({\bm{x}},{\bm{y}}^{r},{\bm{\mu}};{\bm{z}})=\max_{{\bm{y}}}\bigg{(}G({\bm{x}},{\bm{y}},{\bm{\mu}};{\bm{z}})-\frac{\rho}{2}\|{\bm{y}}-{\bm{y}}^{r}\|^{2}_{{\bm{L}}^{+}}\bigg{)}.$

Thus, we have
$G({\bm{x}}^{r+1},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})-G({\bm{x}}^{r},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})$
to be bounded as

$\displaystyle
G({\bm{x}}^{r+1},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})-G({\bm{x}}^{r},{\bm{y}}^{r},{\bm{\mu}}^{r+1},{\bm{z}}^{r})$
$\displaystyle=\sum_{i=1}^{N}\bigg{(}f_{i}({\bm{x}}_{i}^{r+1})+\frac{p}{2}\|{\bm{x}}_{i}^{r+1}-{\bm{z}}_{i}^{r}\|^{2}-f_{i}({\bm{x}}_{i}^{r})-\frac{p}{2}\|{\bm{x}}_{i}^{r}-{\bm{z}}_{i}^{r}\|^{2}\bigg{)}+\sum_{i=1}^{N}{\langle}{\bm{y}}_{i}^{r},{\bm{B}}_{i}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}){\rangle}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}\sum_{i=1}^{N}\bigg{(}\big{(}\nabla
f_{i}({\bm{x}}_{i}^{r})+p({\bm{x}}_{i}^{r}-{\bm{z}}_{i}^{r})\big{)}^{\top}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r})+\frac{p+\gamma^{+}}{2}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|^{2}\bigg{)}+\sum_{i=1}^{N}{\langle}{\bm{y}}_{i}^{r},{\bm{B}}_{i}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}){\rangle}$
$\displaystyle=\sum_{i=1}^{N}\bigg{(}\nabla
H({\bm{x}}_{i}^{r})^{\top}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r})-{\langle}{\bm{B}}_{i}^{\top}{\bm{y}}_{i}^{r+1},{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}{\rangle}+\frac{p+\gamma^{+}}{2}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|^{2}\bigg{)}$
$\displaystyle~{}~{}~{}+\sum_{i=1}^{N}{\langle}{\bm{y}}_{i}^{r},{\bm{B}}_{i}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}){\rangle}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}\sum_{i=1}^{N}(-\frac{1}{\zeta}+\frac{p+\gamma^{+}}{2})\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|^{2}+\sum_{i=1}^{N}{\langle}{\bm{y}}_{i}^{r+1}-{\bm{y}}_{i}^{r},{\bm{B}}_{i}({\bm{x}}_{i}^{r}-{\bm{x}}_{i}^{r+1}){\rangle},$
(P.109)

where $\mathrm{(i)}$ is due to the Lipschitz continuity of $\nabla F_{i}$, and
$\mathrm{(ii)}$ is obtained by the updating step for ${\bm{x}}$ in (37) of the
IPDC algorithm. $\blacksquare$

###  P.3 Error bounds and perturbation bounds

The error bounds and perturbation bound in inexact case are analyzed in this
subsection.

###### Lemma 20

Given $\zeta<\frac{2}{p+\gamma^{+}}$, we consider the upper bound of the
solution difference between (3) and (37).

$\displaystyle\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r})\|\leq\sigma_{4}\|{\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}^{r}\|,$
(P.110)

where $\sigma_{4}=\bigg{(}1+\frac{3}{\zeta(p+\gamma^{-})}\bigg{)}$.

Proof of Lemma 20: The proof is similar to inequality (3.4) of Lemma 3.6 in
[17] hence is omitted. $\blacksquare$

###### Lemma 21

Consider (42) with $p>-\gamma^{-}$. Then for any
$\bar{}{\bm{y}}^{r}\in\mathcal{Y}({\bm{\mu}}^{r+1},{\bm{z}}^{r})$, we have

  1. (a)

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|_{{\bm{L}}^{-}}^{2}\leq{a_{1}}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+a_{5}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2},$
(P.111)

  2. (b)

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|^{2}\leq{a_{2}}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+a_{6}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}.$
(P.112)

Proof of Lemma 21(a): For any
$\bar{}{\bm{y}}^{r}\in\mathcal{Y}({\bm{\mu}}^{r+1},{\bm{z}}^{r})$, recall its
KKT conditions in (F.51) and (F.52).

Analogously, from (19b), we have KKT conditions for ${\bm{y}}^{r+1}$ as

$\displaystyle\begin{bmatrix}{\bm{B}}_{1}{\bm{x}}_{1}({\bm{y}}_{1}^{r+1},{\bm{z}}_{1}^{r})-\frac{{\bm{q}}}{N}+{\bm{B}}_{i}({\bm{x}}_{1}^{r+1}-{\bm{x}}_{1}({\bm{y}}_{1}^{r+1},{\bm{z}}_{1}^{r}))\\\
\vdots\\\
{\bm{B}}_{N}{\bm{x}}_{N}({\bm{y}}_{N}^{r+1},{\bm{z}}_{N}^{r})-\frac{{\bm{q}}}{N}+{\bm{B}}_{N}({\bm{x}}_{N}^{r+1}-{\bm{x}}_{N}({\bm{y}}_{N}^{r+1},{\bm{z}}_{N}^{r}))\end{bmatrix}-{\bm{A}}^{\top}{\bm{\mu}}^{r+1}-\rho{\bm{L}}^{-}{\bm{y}}^{r+1}-\rho{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})={\bm{0}},$
(P.113) $\displaystyle\nabla
F_{i}({\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r}))+{\bm{B}}_{i}^{\top}{\bm{y}}_{i}^{r+1}={\bm{0}},\forall
i\in[N].$ (P.114)

With fixed
$\\{{\bm{x}}_{i}\big{(}\bar{}{\bm{y}}_{i}^{r},{\bm{z}}_{i}^{r}\big{)}\\}_{i=1}^{N}$,
(F.51) and (F.52) forms a linear system of variable $\rho\bar{}{\bm{y}}^{r}$.
Then, by using the Hoffman bound in Lemma 13, the distance from
${\bm{y}}^{r+1}$ satisfying (P.113) and (P.114) to the set
$\mathcal{Y}({\bm{\mu}}^{r+1},{\bm{z}}^{r})$ can be bounded as

$\displaystyle\rho^{2}{\rm
dist}^{2}({\bm{y}}^{r+1},\mathcal{Y}({\bm{\mu}}^{r+1},{\bm{z}}^{r}))$
$\displaystyle\leq\theta_{1}^{2}\sum_{i=1}^{N}\|{\bm{B}}_{i}({\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r}))-{\bm{x}}_{i}(\bar{}{\bm{y}}_{i}^{r},{\bm{z}}_{i}^{r}))\|^{2}+\theta_{1}^{2}\rho^{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}$
$\displaystyle~{}~{}~{}+\theta_{1}^{2}\rho^{2}\sum_{i=1}^{N}\|\nabla
F_{i}({\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r}))-\nabla
F_{i}({\bm{x}}_{i}(\bar{}{\bm{y}}_{i}^{r},{\bm{z}}_{i}^{r}))\|^{2}+\theta_{1}^{2}\sum_{i=1}^{N}\|{\bm{B}}_{i}({\bm{x}}_{i}^{r+1}-{\bm{x}}_{i}({\bm{y}}_{i}^{r+1},{\bm{z}}_{i}^{r}))\|^{2}$
$\displaystyle\leq\frac{\theta_{1}^{2}}{2\eta_{1}}\bigg{(}\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\bigg{)}\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|^{2}+\bigg{[}\frac{\eta_{1}}{2}\bigg{(}\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\bigg{)}+1\bigg{]}\theta_{1}^{2}\rho^{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}$
$\displaystyle~{}~{}~{}-\bigg{(}\frac{\theta_{1}^{2}}{p+\gamma^{-}}+\theta_{1}^{2}\rho^{2}(p+\gamma^{+})\bigg{)}\rho\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|_{{\bm{L}}^{-}}^{2}+\theta_{1}^{2}B_{\max}^{2}\sigma_{4}^{2}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2},$
(P.115)

where the last inequality is due to (F) and (P.110).

Analogous to Lemma 5, choose
$\eta_{1}=\textstyle\frac{\theta_{1}^{2}}{\rho^{2}}\big{(}\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\big{)}$,
we can obtain

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|_{{\bm{L}}^{-}}^{2}\leq
a_{1}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+\underbrace{\frac{B_{\max}^{2}\sigma_{4}^{2}}{\left(\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\right)\rho}}_{\triangleq
a_{5}}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}.$ (P.116)

Proof of lemma 21(b): By lemma 5 and (P.115), we have

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|^{2}$ $\displaystyle\leq
a_{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+\underbrace{\frac{2\theta_{1}^{2}B_{\max}^{2}\sigma_{4}^{2}}{\rho^{2}}}_{\triangleq
a_{6}}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}.$ (P.117)

By taking the square root on both sides, we have

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|$
$\displaystyle\leq\sqrt{a_{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+a_{6}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}}$
$\displaystyle\leq\sqrt{a_{2}}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|+\sqrt{a_{6}}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|.$
(P.118)

$\blacksquare$

###### Lemma 22

Consider $p>\gamma^{-}$, based on Lemma 6 and Lemma 21, we have

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r+1}\|^{2}\leq
2a_{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+2a_{6}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}+2a_{3}\|{\bm{z}}^{r+1}-{\bm{z}}^{r}\|^{2}.$
(P.119)

Proof of Lemma 22: We have

$\displaystyle\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r+1}\|^{2}$
$\displaystyle=\|{\bm{y}}^{r+1}-{\bm{y}}({\bm{\mu}}^{r+1},{\bm{z}}^{r})+\bar{}{\bm{y}}^{r}-\bar{}{\bm{y}}^{r+1}\|^{2}$
$\displaystyle~{}~{}~{}\leq
2\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|^{2}+2\|\bar{}{\bm{y}}^{r}-\bar{}{\bm{y}}^{r+1}\|^{2}$
$\displaystyle~{}~{}~{}\leq
2a_{2}\|{\bm{L}}^{+}({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}+2a_{6}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}+2a_{3}\|{\bm{z}}^{r+1}-{\bm{z}}^{r}\|^{2},$
(P.120)

where the last inequality is due to (P.112) and Lemma 6.

$\blacksquare$

Then, we can bound the following differences.

###### Lemma 23

For any $\bar{}{\bm{y}}^{r}\in\mathcal{Y}({\bm{\mu}}^{r+1},{\bm{z}}^{r})$,
there exist ${\bm{y}}({\bm{z}}^{r})\in\mathcal{Y}({\bm{z}}^{r})$ and
${\bm{x}}({\bm{z}}^{r})$ such that

$\displaystyle\|{\bm{y}}^{r+1}-{\bm{y}}({\bm{z}}^{r})\|\leq\sqrt{a_{2}}\lambda_{\max}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|+\sqrt{a_{6}}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|+\sqrt{a_{4}}\|{\bm{A}}\bar{}{\bm{y}}^{r}\|,$
(P.121)
$\displaystyle\|{\bm{x}}^{r+1}-{\bm{x}}({\bm{z}}^{r})\|\leq\sigma_{2}\|{\bm{y}}^{r+1}-{\bm{y}}({\bm{z}}^{r})\|+\sigma_{4}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|.$
(P.122)

Proof of Lemma 23: Firstly,

$\displaystyle\|{\bm{y}}^{r+1}-{\bm{y}}({\bm{z}}^{r})\|$
$\displaystyle=\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}+\bar{}{\bm{y}}^{r}-{\bm{y}}({\bm{z}}^{r})\|$
$\displaystyle\leq\|{\bm{y}}^{r+1}-\bar{}{\bm{y}}^{r}\|+\|\bar{}{\bm{y}}^{r}-{\bm{y}}({\bm{z}}^{r})\|$
$\displaystyle{\leq}\sqrt{a_{2}}\lambda_{\max}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|+\sqrt{a_{6}}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|+\sqrt{a_{4}}\|{\bm{A}}\bar{}{\bm{y}}^{r}\|,$
(P.123)

where the last inequality is due to (P.117) and (57).

Secondly, we can have

$\displaystyle\|{\bm{x}}^{r+1}-{\bm{x}}({\bm{z}}^{r})\|$
$\displaystyle=\|{\bm{x}}^{r+1}-{\bm{x}}({\bm{y}}^{r+1},{\bm{z}}^{r})+{\bm{x}}({\bm{y}}^{r+1},{\bm{z}}^{r})-{\bm{x}}({\bm{z}}^{r})\|$
$\displaystyle\leq\|{\bm{x}}^{r+1}-{\bm{x}}({\bm{y}}^{r+1},{\bm{z}}^{r})\|+\|{\bm{x}}({\bm{y}}^{r+1},{\bm{z}}^{r})-{\bm{x}}({\bm{y}}({\bm{z}}^{r}),{\bm{z}}^{r})\|$
$\displaystyle\leq\sigma_{4}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|+\sigma_{2}\|{\bm{y}}^{r+1}-{\bm{y}}({\bm{z}}^{r})\|,$
(P.124)

where the last inequality is due to (49). $\blacksquare$

Similar to the PDC algorithm (Lemma 8), we also have the non-increasing
property of the potential function for the IPDC algorithm, which is given in
the following lemma.

###### Lemma 24

Let $\beta$ satisfies (63) in Lemma 8 and $\rho>1/2$. Then given $p$ meeting

$\displaystyle
p>\max\bigg{\\{}0,\gamma^{+}-2\gamma^{-},\frac{32(2\rho-1)B_{\max}^{2}}{5\lambda_{\max}^{2}\rho^{2}}-\gamma^{-},32B_{\max}^{2}-\gamma^{-},\frac{2\gamma^{+}-7\gamma^{-}}{5}\bigg{\\}},$
(P.125)

for sufficiently small $\zeta$ and $\alpha$ satisfying

$\displaystyle\frac{1}{p+\gamma^{-}}<\zeta<\min\bigg{\\{}\frac{5}{2(\gamma^{+}-\gamma^{-})},~{}\frac{2}{p+\gamma^{+}},~{}\frac{5a_{2}\lambda_{\max}^{2}\rho^{2}}{64(2\rho-1)\theta_{1}^{2}B_{\max}^{2}},~{}\frac{1}{32B_{\max}^{2}}\bigg{\\}},$
(P.126)
$\displaystyle\alpha<\min\bigg{\\{}\frac{\rho}{5},~{}\frac{2\rho-1}{16a_{1}\lambda_{\max}^{2}},~{}\frac{1}{8a_{5}\zeta}\bigg{\\}},$
(P.127)

and for any $r$,

  1. (a)

we have

$\displaystyle\Phi^{r+1}-\Phi^{r}$ $\displaystyle\leq-
C_{1}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}_{{\bm{L}}^{-}}-\frac{1}{2}\|({\bm{y}}^{r}-{\bm{y}}^{r-1})-({\bm{y}}^{r+1}-{\bm{y}}^{r})\|^{2}_{{\bm{L}}^{+}}-\alpha\|{\bm{A}}{\bm{y}}({\bm{\mu}}^{r+1},{\bm{z}}^{r})\|^{2}$
$\displaystyle~{}~{}~{}-\bigg{(}C_{2}-\frac{1}{2}\bigg{)}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}-C_{3}\|{\bm{z}}^{r+1}-{\bm{z}}^{r}\|^{2}-C_{4}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}.$
(P.128)

where $C_{1},C_{2},C_{3}$ is defined in Lemma 8, $C_{4}$ is

$\displaystyle
C_{4}\triangleq\frac{1}{\zeta}-\frac{\gamma^{+}-\gamma^{-}}{2}-2\alpha
a_{5}-\frac{4p\sigma_{2}^{2}a_{6}}{\delta}-\frac{B_{\max}^{2}\sigma_{4}^{2}}{2},$
(P.129)

and $C_{1},(C_{2}-1/2),C_{3},C_{4}>0$.

  2. (b)

The function $\Phi^{r}$ in (47) is lower bounded, i.e.,
$\sum_{r=0}^{T}\Phi^{r+1}>\underline{\Phi}>-\infty$ for some constant
$\underline{\Phi}$.

It implies that $\Phi^{r}$ is non-increasing with $r$.

Proof of Lemma 24(a): This proof is divided into the following three steps:

  * •

Step 1: Obtain the bound in (P.128);

  * •

Step 2: Solve sufficient conditions on $p$, $\rho$, $\beta$, $\zeta$, $\alpha$
for proving positiveness of $C_{1}-C_{4}$;

  * •

Step 3: Summarize all the conditions of the convergence for the IPDC
algorithm.

  1. Step 1:

Obtain (P.128): We can follow the same proof procedure of Lemma 8(a). Compared
with (64), there are two additional terms in (P.128) shown as follows.

    1. (1)

The first one is $-\frac{1}{2}\|{\bm{y}}^{r+1}-{\bm{y}}^{r}\|^{2}$, which is
obtained by (18) in Lemma 18.

    2. (2)

The second part $-C_{4}\|{\bm{x}}^{r+1}-{\bm{x}}^{r}\|^{2}$ consists of five
terms. Note that the first two term is obtained by the bound in Lemma 19, the
third term is by applying lemma 21(a) into (4.3)${\mathrm{(iii)}}$, the fourth
term is due to the use of Lemma 22 in (67)${\mathrm{(i)}}$, and the last term
is resulted from the bound in Lemma 18.

  2. Step 2:

Prove the positiveness of $C_{1}$-$C_{4}$ in (P.128):

    1. (1)

Prove $C_{1},C_{3}>0$: According to Lemma 8(a), we obtain that if
$\alpha<\frac{\rho}{5}$ and $\beta$ satisfies (63), then $C_{1}$ and $C_{3}$
in (4.3) are both positive.

    2. (2)

Prove $C_{2}>\frac{1}{2}$: As for $C_{2}$ in (4.3), we firstly assume
$\rho>\frac{1}{2}$. Different from the choice of $\delta$ in the proof of
Lemma 8(a), we choose
$\delta=\frac{{20}p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho-\frac{1}{2}}>\frac{16p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho-\frac{1}{2}}$,
i.e.,
$\frac{4p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\delta}<\frac{\rho-\frac{1}{2}}{4}$.
Then, as long as $\alpha<\frac{\rho-\frac{1}{2}}{8a_{1}\lambda_{\max}^{2}}$
and $\rho>\frac{1}{2}$, we can have
$C_{2}-\frac{1}{2}>\frac{\rho}{2}-\frac{1}{4}>0$ .

    3. (3)

Prove $C_{4}>0$: By inserting
$\delta=\frac{{20}p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho-1/2}$ into
(P.129), we have

$\displaystyle C_{4}=\frac{1}{\zeta}-\frac{\gamma^{+}-\gamma^{-}}{2}-2\alpha
a_{5}-\frac{(\rho-1/2)a_{6}}{5a_{2}\lambda_{\max}^{2}}-\frac{B_{\max}^{2}\sigma_{4}^{2}}{2}.$
(P.130)

To guarantee $C_{4}>0$, we have

$\displaystyle\alpha$
$\displaystyle<\frac{1}{2a_{5}}\bigg{[}\frac{10a_{2}\lambda_{\max}^{2}-(\gamma^{+}-\gamma^{-})5\zeta
a_{2}\lambda_{\max}^{2}-2(\rho-1/2)a_{6}\zeta-5B_{\max}^{2}\sigma_{4}^{2}\zeta
a_{2}\lambda_{\max}^{2}}{10\zeta a_{2}\lambda_{\max}^{2}}\bigg{]}$
$\displaystyle=\frac{10a_{2}\lambda_{\max}^{2}-(\gamma^{+}-\gamma^{-})5\zeta
a_{2}\lambda_{\max}^{2}-2(\rho-1/2)a_{6}\zeta-5B_{\max}^{2}\sigma_{4}^{2}\zeta
a_{2}\lambda_{\max}^{2}}{20\zeta a_{2}a_{5}\lambda_{\max}^{2}}$
$\displaystyle\triangleq\frac{D_{1}}{D_{2}}.$ (P.131)

Note that if $D_{1}>0$ and $\alpha<\frac{D_{1}}{D_{2}}$, then we can complete
the proof. To guarantee $D_{1}>0$, it suffices to show the following three
conditions

$\displaystyle(\gamma^{+}-\gamma^{-})\zeta
a_{2}\lambda_{\max}^{2}<\frac{5a_{2}\lambda_{\max}^{2}}{2},$ (P.132a)
$\displaystyle
2(\rho-\frac{1}{2})a_{6}\zeta<\frac{5a_{2}\lambda_{\max}^{2}}{2},$ (P.132b)
$\displaystyle B_{\max}^{2}\sigma_{4}^{2}\zeta
a_{2}\lambda_{\max}^{2}<\frac{a_{2}\lambda_{\max}^{2}}{2}.$ (P.132c)

Next, we prove these conditions one by one.

      1. 1)

To guarantee (P.132a) holds, i.e., $(\gamma^{+}-\gamma^{-})\zeta
a_{2}\lambda_{\max}^{2}<\frac{5a_{2}\lambda_{\max}^{2}}{2}$ we require an
upper bound on $\zeta$, i.e.,

$\displaystyle\zeta<\frac{5}{2(\gamma^{+}-\gamma^{-})}.$ (P.133)

      2. 2)

To guarantee (P.132b) holds, i.e.,
$2(\rho-\frac{1}{2})a_{6}\zeta<\frac{5a_{2}\lambda_{\max}^{2}}{2}$, we obtain
another bound on $\zeta$, i.e.,

$\displaystyle\zeta<\frac{5a_{2}\lambda_{\max}^{2}\rho^{2}}{8(\rho-\frac{1}{2})\theta_{1}^{2}B_{\max}^{2}\sigma_{4}^{2}}.$
(P.134)

Note that this bound is implicit, since $\sigma_{4}$ defined in Lemma 20 is a
function of $\zeta$.

To overcome this, we assume
$\frac{1}{p+\gamma^{-}}<\zeta<\frac{2}{p+\gamma^{+}}$ and
$p>\gamma^{+}-2\gamma^{-}$. Then, we have
$\sigma_{4}=\big{(}1+\frac{3}{\zeta(p+\gamma^{-})}\big{)}<4$. Therefore, we
obtain an explicit sufficient condition of (P.134), i.e.,

$\displaystyle\frac{1}{p+\gamma^{-}}<\zeta<\frac{5a_{2}\lambda_{\max}^{2}\rho^{2}}{128(\rho-\frac{1}{2})\theta_{1}^{2}B_{\max}^{2}}.$
(P.135)

Since $\zeta$ has a lower bound $\frac{1}{p+\gamma^{-}}$, we need to guarantee
that the solution set of $\zeta$ in (P.135) is non-empty. That is, the lower
bound is required to be smaller than the upper bound. Inserting $a_{2}$ of
(54) into (P.135), we have

$\displaystyle\frac{1}{p+\gamma^{-}}<\frac{5\lambda_{\max}^{2}\rho^{2}}{128(\rho-1/2)\theta_{1}^{2}B_{\max}^{2}\sigma_{4}^{2}}\bigg{[}\frac{\theta_{1}^{4}}{\rho^{2}}\bigg{(}\frac{1}{p+\gamma^{-}}+\rho^{2}(p+\gamma^{+})\bigg{)}^{2}+2\theta_{1}^{2}\bigg{]}$
$\displaystyle\Leftarrow$
$\displaystyle~{}5\lambda_{\max}^{2}\theta_{1}^{2}+5\lambda_{\max}^{2}\theta_{1}^{2}\rho^{4}(p+\gamma^{-})^{2}(p+\gamma^{+})^{2}+10\lambda_{\max}^{2}\theta_{1}^{2}\rho^{2}(p+\gamma^{-})(p+\gamma^{+})$
$\displaystyle~{}~{}~{}+10\lambda_{\max}^{2}\rho^{2}(p+\gamma^{-})^{2}-128(\rho-1/2)B_{\max}^{2}(p+\gamma^{-})>0$
$\displaystyle\Leftarrow$
$\displaystyle~{}10\lambda_{\max}^{2}\rho^{2}(p+\gamma^{-})^{2}-128(\rho-1/2)B_{\max}^{2}(p+\gamma^{-})>0$
$\displaystyle\Leftarrow$
$\displaystyle~{}p>\frac{32(2\rho-1)B_{\max}^{2}}{5\lambda_{\max}^{2}\rho^{2}}-\gamma^{-},$
(P.136)

which gives a sufficient condition for achieving (P.135).

      3. 3)

To guarantee (P.132c) holds, i.e., $B_{\max}^{2}\sigma_{4}^{2}\zeta
a_{2}\lambda_{\max}^{2}<\frac{a_{2}\lambda_{\max}^{2}}{2}$, we use the same
operation on $\sigma_{4}$ in $\mathrm{(ii)}$, we get

$\displaystyle\frac{1}{p+\gamma^{-}}<\zeta<\frac{1}{32B_{\max}^{2}}.$ (P.137)

It is obvious that when $p>32B_{\max}^{2}-\gamma^{-}$, (P.137) is feasible.

Note that for $\zeta<\frac{5}{2(\gamma^{+}-\gamma^{-})}$ in (P.133) to hold,
we also require $\frac{1}{p+\gamma^{-}}<\frac{5}{2(\gamma^{+}-\gamma^{-})}$, ,
which gives a condition of $p>\frac{2\gamma^{+}-7\gamma^{-}}{5}.$

  3. Step 3:

Thus, combining all the results above above for proving positiveness of
$C_{1}$-$C_{4}$, we have the following conditions on $\beta$, $\zeta$ and
$\alpha$

$\displaystyle\beta<\bigg{(}\frac{1}{2}+\frac{20p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}{\rho}+\frac{\rho(\sigma_{1}^{2}+2\sigma_{2}^{2}a_{3})}{10p\sigma_{2}^{2}a_{2}\lambda_{\max}^{2}}\bigg{)}^{-1}~{}~{}({\mathrm{Recall}}~{}\eqref{eqn:
beta condition}),$ (P.138)
$\displaystyle\frac{1}{p+\gamma^{-}}<\zeta<\min\bigg{\\{}\frac{5}{2(\gamma^{+}-\gamma^{-})},~{}\frac{2}{p+\gamma^{+}},~{}\frac{5a_{2}\lambda_{\max}^{2}\rho^{2}}{64(2\rho-1)\theta_{1}^{2}B_{\max}^{2}},~{}\frac{1}{32B_{\max}^{2}}\bigg{\\}}$
(P.139)
$\displaystyle\alpha<\min\bigg{\\{}\frac{\rho}{5},~{}\frac{2\rho-1}{16a_{1}\lambda_{\max}^{2}},~{}\frac{1}{8a_{5}\zeta}\bigg{\\}},$
(P.140)

provided that $\rho>\frac{1}{2}$ and $p$ satisfies

$\displaystyle
p>\max\bigg{\\{}0,\gamma^{+}-2\gamma^{-},\frac{32(2\rho-1)B_{\max}^{2}}{5\lambda_{\max}^{2}\rho^{2}}-\gamma^{-},32B_{\max}^{2}-\gamma^{-},\frac{2\gamma^{+}-7\gamma^{-}}{5}\bigg{\\}}.$
(P.141)

Therefore, given sufficiently large $p$ and $\rho>\frac{1}{2}$, for
sufficiently small $\beta$, $\zeta$, and $\alpha$, the IPDC algorithm can have
the same convergence properties as the PDC algorithm.

Proof of Lemma 24(b): The proof is similar to the proof of Lemma 8(b) (see
Appendix I) hence is omitted. $\blacksquare$

Similar to the proof of Theorem 1, we can also obtain that every limit point
of the iteration sequence $\\{({\bm{z}}^{r},{\bm{y}}^{r})\\}$ is a KKT
solution of problem (P). There exists a constant $\hat{C}>0$ and such that

$\displaystyle\|{\bm{z}}^{r}-{\bm{x}}({\bm{z}}^{r})\|^{2}\leq\frac{\hat{C}}{t},$
(P.142)

where
${\hat{C}}\triangleq(\Phi^{0}-\underline{\Phi})\left(\frac{1}{\beta\sqrt{C_{3}}}+\frac{\sigma_{2}\sqrt{a_{2}}\lambda_{\max}}{\sqrt{C_{2}}}+\frac{\sigma_{2}\sqrt{a_{6}}+\sigma_{4}}{\sqrt{C_{4}}}+\frac{\sigma_{2}\sqrt{a_{4}}}{\sqrt{\alpha}}\right)^{2}.$
$\blacksquare$

##  Appendix Q Additional Simulation Results

(a) $\beta=0.1$, $p=10$, $\rho=1$, $\zeta=0.1$, and various values of $\alpha$

(b) $\alpha=0.01$, $\rho=1$, $\zeta=0.1$, $p=10$, and various values of
$\beta$

Figure 6: Convergence curves of the IPDC algorithm different step-sizes.

In this section, besides of the results displayed in the main text, we show
the convergence results for the proposed IPDC algorithm with respect to the
parameter $\alpha$, $\beta$, $\zeta$, $p$ and $\rho$.

(a) $\alpha=0.01$, $p=10$, $\rho=1$, $\beta=0.1$, and various values of
$\zeta$

(b) $\alpha=0.01$, $\rho=1$, $\zeta=0.1$, $\beta=0.1$, and various values of
$p$

(c) $\alpha=0.01$, $p=10$, $\zeta=0.1$, $\beta=0.1$, and various values of
$\rho$

Figure 7: Convergence curves of the IPDC algorithm with respect to gradient
residue and infeasibility.

In Fig. 6(a), we set $\beta=0.1$, $p=10$, $\rho=1$, $\zeta=0.1$, and
$\alpha\in\\{10^{-4},10^{-3},10^{-2},10^{-1}\\}$. One can see that a larger
$\alpha$ may speed up the convergence of gradient residue (left figure), while
with distinct $\alpha$ the IPDC algorithm performs similar with respect to
infeasibility (right figure). In Fig. 6(b), we set $\alpha=0.01$, $\rho=1$,
$\zeta=0.1$, $p=10$, and $\beta\in\\{10^{-3},10^{-2},10^{-1},1\\}$. we can see
that $\beta$ influences the performance of the IPDC algorithm significantly.
Interestingly, though Theorem 1 indicates that $\beta$ should be less than one
and a small number, it is shown that the algorithm behaves well with
$\beta=1$. This phenomenon is similar to that shown in Fig. 4.

In Fig. 7(a), we set $\alpha=0.01$, $p=10$, $\rho=1$, $\beta=0.1$, and
$\zeta\in\\{10^{-4},10^{-3},10^{-2},10^{-1}\\}$. One can observe that a larger
step size $\zeta$ may speed up the convergence of gradient residue and
infeasibility. In Fig. 7(b), we set $\alpha=0.01$, $\rho=1$, $\zeta=0.1$,
$\beta=0.1$, and $p\in\\{1,10,100\\}$. One can observe that with a too small
$p=1$ or a too large $p=100$ the IPDC algorithm may not converge to a small
gradient residue. Moreover, it is expected that a larger $p$ may slow down the
convergence with respect to infeasibility, due to a more conservative convex
approximation. In Fig. 7(c), we set $\alpha=0.01$, $p=10$, $\zeta=0.1$,
$\beta=0.1$, and $\rho\in\\{10^{-2},10^{-1},1,10,100\\}$. One can see from
these two figures that a larger $\rho$ can fasten the convergence of gradient
residue, whereas a larger $\rho$ may slow down the speed satisfying the linear
constraints.

## References

  * [1] J. Zhang, S. Ge, T.-H. Chang, and Z.-Q. Luo, “A proximal dual consensus method for linearly coupled multi-agent non-convex optimization,” in Proc. ICASSP, pp. 5740–5744, 2020.
  * [2] G. B. Giannakis, Q. Ling, G. Mateos, I. D. Schizas, and H. Zhu, “Decentralized learning for wireless communications and networking,” in Splitting Methods in Communication, Imaging, Science, and Engineering, pp. 461–497, Springer, 2016.
  * [3] R. Bekkerman, M. Bilenko, and J. Langford, Scaling up Machine Learning- Parallel and Distributed Approaches.  Cambridge University Press, 2012.
  * [4] T.-H. Chang, M. Hong, H.-T. Wai, X. Zhang, and S. Lu, “Distributed learning in the nonconvex world: From batch data to streaming and beyond,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 26–38, 2020.
  * [5] G. Scutari and Y. Sun, “Parallel and distributed successive convex approximation methods for big-data optimization,” in Multi-agent Optimization, pp. 141–308, Springer, 2018.
  * [6] J. Konečnỳ, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon, “Federated learning: Strategies for improving communication efficiency,” arXiv preprint arXiv:1610.05492, 2016.
  * [7] T.-H. Chang, M. Hong, and X. Wang, “Multi-agent distributed optimization via inexact consensus ADMM,” IEEE Trans. Signal Process., vol. 63, no. 2, pp. 482–497, 2014.
  * [8] Y. Hu, P. Liu, L. Kong, and D. Niu, “Learning privately over distributed features: An ADMM sharing approach,” arXiv preprint arXiv:1907.07735, 2019.
  * [9] D. K. Molzahn, F. Dörfler, H. Sandberg, S. H. Low, S. Chakrabarti, R. Baldick, and J. Lavaei, “A survey of distributed optimization and control algorithms for electric power systems,” IEEE Trans. Smart Grid, vol. 8, no. 6, pp. 2941–2962, 2017.
  * [10] S.-C. Tsai, Y.-H. Tseng, and T.-H. Chang, “Communication-efficient distributed demand response: A randomized admm approach,” IEEE Transactions on Smart Grid, vol. 8, no. 3, pp. 1085–1095, 2017.
  * [11] C. Shen, T.-H. Chang, K.-Y. Wang, Z. Qiu, and C.-Y. Chi, “Distributed robust multicell coordianted beamforming with imperfect CSI: An ADMM approach,” IEEE Trans. Signal Process., vol. 60, no. 6, pp. 2988–3003, 2012.
  * [12] D. P. Palomar and M. Chiang, “Alternative distributed algorithms for network utility maximization: Framework and applications,” IEEE Transactions on Automatic Control, vol. 52, no. 12, pp. 2254–2269, 2007.
  * [13] W. Kong, J. G. Melo, and R. D. Monteiro, “Complexity of a quadratic penalty accelerated inexact proximal point method for solving linearly constrained nonconvex composite programs,” arXiv preprint arXiv:1802.03504, 2018.
  * [14] D. P. Bertsekas, Nonlinear Programming: 2nd Ed. Cambridge, Massachusetts: Athena Scientific, 2003.
  * [15] M. Hong, T.-H. Chang, X. Wang, M. Razaviyayn, S. Ma, and Z.-Q. Luo, “A block successive upper-bound minimization method of multipliers for linearly constrained convex optimization,” Mathematics of Operations Research, 2020\.
  * [16] Y. Wang, W. Yin, and J. Zeng, “Global convergence of admm in nonconvex nonsmooth optimization,” Journal of Scientific Computing, vol. 78, no. 1, pp. 29–63, 2019.
  * [17] J. Zhang and Z.-Q. Luo, “A proximal alternating direction method of multiplier for linearly constrained nonconvex minimization,” SIAM Journal on Optimization, vol. 30, no. 3, pp. 2272–2302, 2020.
  * [18] D. P. Palomar and M. Chiang, “A tutorial on decomposition methods for network utility maximization,” IEEE Journal on Selected Areas in Communications, vol. 24, no. 8, pp. 1439–1451, 2006.
  * [19] T.-H. Chang, “A proximal dual consensus ADMM method for multi-agent constrained optimization,” IEEE Trans. Signal Process., vol. 64, no. 14, pp. 3719–3734, 2016.
  * [20] I. Notarnicola, M. Franceschelli, and G. Notarstefano, “A duality-based approach for distributed min–max optimization,” IEEE Transactions on Automatic Control, vol. 64, no. 6, pp. 2559–2566, 2019.
  * [21] S. Liang, L. Y. Wang, and G. Yin, “Distributed smooth convex optimization with coupled constraints,” IEEE Transactions on Automatic Control, vol. 65, no. 1, pp. 347–353, 2020.
  * [22] S. A. Alghunaim, K. Yuan, and A. H. Sayed, “Dual coupled diffusion for distributed optimization with affine constraints,” in Proc. IEEE CDC, pp. 829–834, 2018.
  * [23] X. Li, L. Xie, and Y. Hong, “Distributed continuous-time nonsmooth convex optimization with coupled inequality constraints,” IEEE Transactions on Control of Network Systems, vol. 7, no. 1, pp. 74–84, 2020.
  * [24] M. Zhu and S. Martínez, “On distributed convex optimization under inequality and equality constraints,” IEEE Trans. Automatic Control, vol. 57, no. 1, pp. 151–164, 2011.
  * [25] T.-H. Chang, A. Nedić, and A. Scaglione, “Distributed constrained optimization by consensus-based primal-dual perturbation method,” IEEE Trans. Automatic Control, vol. 59, no. 6, pp. 1524–1538, 2014.
  * [26] A. Nedic, “Distributed gradient methods for convex machine learning problems in networks: Distributed optimization,” IEEE Signal Processing Magazine, vol. 37, no. 3, pp. 92–101, 2020.
  * [27] G. B. Giannakis, Q. Ling, G. Mateos, I. D. Schizas, and H. Zhu, Decentralized learning for wireless communications and networking.  Springer, 2016.
  * [28] H. Sun and M. Hong, “Distributed non-convex first-order optimization and information processing: Lower complexity bounds and rate optimal algorithms,” IEEE Transactions on Signal processing, vol. 67, no. 22, pp. 5912–5928, 2019.
  * [29] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, “Lower bounds for finding stationary points i,” Mathematical Programming, pp. 1–50, 2019.
  * [30] B. Ying, K. Yuan, and A. H. Sayed, “Supervised learning under distributed features,” IEEE Transactions on Signal Processing, vol. 67, no. 4, pp. 977–992, 2019.
  * [31] Y. Hu, D. Niu, J. Yang, and S. Zhou, “Fdml: A collaborative machine learning framework for distributed features,” in Proc. SIGKDD, pp. 2232–2240, 2019\.
  * [32] S. Boyd and L. Vandenberghe, Convex Optimization.  Cambridge, UK: Cambridge University Press, 2004.
  * [33] D. P. Bertsekas, “Nonlinear programming,” Journal of the Operational Research Society, vol. 48, no. 3, pp. 334–334, 1997.
  * [34] Y. Nesterov, “Smooth minimization of non-smooth functions,” Mathematical Programming, vol. 103, no. I, 2005.
  * [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 Proc. 34th Inter. Conf. Mach. Learn. (ICML), pp. 1529–1538, JMLR. org, 2017.
  * [36] J. Zhang, S. Ge, T.-H. Chang, and Z.-Q. Luo, “Decentralized non-convex learning with linearly coupled constraints,” arXiv preprint arXiv:2103.05378, 2021.
  * [37] S. Boyd, S. P. Boyd, and L. Vandenberghe, Convex optimization.  Cambridge university press, 2004.
  * [38] A. Antoniadis, I. Gijbels, and M. Nikolova, “Penalized likelihood regression for generalized linear models with non-quadratic penalties,” Annals of the Institute of Statistical Mathematics, vol. 63, no. 3, pp. 585–615, 2011\.
  * [39] M. E. Yildiz and A. Scaglione, “Coding with side information for rate-constrained consensus,” IEEE Trans. Signal Process., vol. 56, no. 8, pp. 3753–3764, 2008.
  * [40] A. Beck and M. Teboulle, “A fast iterative shrinkage-thresholding algorithm for linear inverse problems,” SIAM J. Imaging Sci., vol. 2, no. 1, pp. 183–202, 2009.
  * [41] I. Goodfellow, Y. Bengio, and A. Courville, Deep Learning.  MIT Press, 2016.  http://www.deeplearningbook.org.
  * [42] X. Lian, C. Zhang, H. Zhang, C.-J. Hsieh, W. Zhang, and J. Liu, “Can decentralized algorithms outperform centralized algorithms? A case study for decentralized parallel stochastic gradient descent,” in Proc. NeuIPS, (California, USA), p. 5336?5346, Dec. 4-9, 2017.
  * [43] R. Xin, U. A. Khan, and S. Kar, “A near-optimal stochastic gradient method for decentralized non-convex finite-sum optimization,” arXiv e-prints, pp. arXiv–2008, 2020.
  * [44] H. B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. Areas, “Communication-efficient learning of deep networks from decentralized data,” in Proc. ICML, (Sydney, Australia), pp. 1–10, Aug. 6-11, 2017.
  * [45] R. Xin, U. A. Khan, and S. Kar, “An improved convergence analysis for decentralized online stochastic non-convex optimization,” IEEE Transactions on Signal Processing, vol. 69, pp. 1842–1858, 2021.
  * [46] H. Tang, X. Lian, M. Yan, C. Zhang, and J. Liu, “$d2$: Decentralized training over decentralized data,” in International Conference on Machine Learning, pp. 4848–4856, PMLR, 2018.
  * [47] Q. Yang, Y. Liu, T. Chen, and Y. Tong, “Federated machine learning: Concept and applications,” ACM Transactions on Intelligent Systems and Technology, vol. 10, pp. 1–19, Jan. 2019.
  * [48] D. Zou, Y. Cao, D. Zhou, and Q. Gu, “Stochastic gradient descent optimizes over-parameterized deep relu networks,” arXiv preprint arXiv:1811.08888, 2018.
  * [49] X. Zhang, Y. Yu, L. Wang, and Q. Gu, “Learning one-hidden-layer relu networks via gradient descent,” in The 22nd international conference on artificial intelligence and statistics, pp. 1524–1534, PMLR, 2019.
  * [50] D. Bertsekas, A. Nedic, and A. Ozdaglar, Convex analysis and optimization, vol. 1.  Athena Scientific, 2003.
  * [51] J.-S. Pang, “A posteriori error bounds for the linearly-constrained variational inequality problem,” Mathematics of Operations Research, vol. 12, no. 3, pp. 474–484, 1987.
  * [52] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems.  Springer Science & Business Media, 2007.
  * [53] Y. Nesterov, Introductory lectures on convex optimization: A basic course, vol. 87.  Springer Science & Business Media, 2013.
  * [54] F. Facchinei and J.-S. Pang, Finite-dimensional variational inequalities and complementarity problems.  Springer, 2003.
  * [55] D. Cvetković, P. Rowlinson, and S. K. Simić, “Signless laplacians of finite graphs,” Linear Algebra and its applications, vol. 423, no. 1, pp. 155–171, 2007.
  * [56] Daniel A. Spielman, “Spectral graph theory, Fundamental Graphs,” 2018.  https://www.cs.yale.edu/homes/spielman/561/lect03-18.pdf.