text:
\section{Introduction}\label{sec:intro}

This paper focuses on the following decentralized optimization problem:
\begin{equation} \label{eq:F}
\Min\limits_{x\in\mathbb{R}^p}~\bar f(x):=\frac{1}{n}\sum\limits_{i=1}^n (s_i(x)+r_i(x)),
\end{equation}
where $s_i:\mathbb{R}^p\rightarrow \mathbb{R}$ and $r_i: \mathbb{R}^p\rightarrow \mathbb{R}\cup\{+\infty\}$ are two lower semi-continuous proper convex functions held privately by agent $i$ to encode the agent's objective function.
We assume that one function (e.g., without loss of generality, $s_i$) is differentiable with a Lipschitz continuous gradient with parameter $L>0$, and the other function $r_i$ is proximable, i.e., its proximal mapping
$$   \mathbf{prox}_{\lambda r_i}(x) = \argmin_{x\in \mathbb{R}^p}~\lambda r_i(x) + {1\over2}\|x-y\|^2,$$
has a closed-from solution or can be computed easily.
Examples of $s_i$ include linear functions, quadratic functions, and logistic functions, while $r_i$ could be the $\ell_1$ norm, total variation, or indicator functions of convex constraints.
In addition, we assume that the agents are connected through a fixed bi-directional communication network.
Every agent in the network wants to obtain an optimal solution of \eqref{eq:F} while it can only receive/send messages that are not sensitive\footnote{We believe that agent $i$'s instantaneous estimation on the optimal solution is not a piece of sensitive information but the functions $s_i$ and $r_i$ are.} from/to its immediate neighbors.

Specific problems of form~\eqref{eq:F} that require such a decentralized computing architecture have appeared in various areas including networked multi-vehicle coordination, distributed information processing, and decision making in sensor networks, as well as distributed estimation and learning.
Some examples include distributed average consensus~\cite{Xiao2007,Cai2014,Olshevsky2014}, distributed spectrum sensing~\cite{Bazerque2010}, information control~\cite{Ren2006,Olshevsky2010}, power systems control~\cite{Ram2009,Gan2013}, statistical inference and learning~\cite{Rabbat2004,Forero2010,Nedic2015_2}.
In general, decentralized optimization fits the scenarios where the data is collected and/or stored in a distributed network.
A fusion center is either inapplicable or unaffordable, and/or computing is required to be performed in a distributed but collaborative manner by multiple agents or network designers.

\subsection{Literature Review}
The study on distributed algorithms dates back to early 1980s~\cite{Bertsekas1983,Tsitsiklis1986}.
Since then, due to the emergence of large-scale networks, decentralized (optimization) algorithms, as a special type of distributed algorithms for solving problem~\eqref{eq:F}, have received significant attentions.
Many efforts have been made on star networks with one master agent and multiple slave agents~\cite{Boyd2011,Cevher2014}.
This scheme is ``centralized'' due to the use of a ``master'' agent and may suffer a single point of failure and violate the privacy requirement in certain applications.
In this paper, we focus on solving~\eqref{eq:F} in a decentralized fashion, where there is no ``master'' agent that is connected to all other agents.

The incremental algorithms \cite{Nedic2000,Nedic2001a,Nedic2001b,Ram2009_2,Bertsekas2011,WangB2013} can solve \eqref{eq:F} without the need of a ``master'' agent but requires that the network contains a ring structure.
To handle general (possibly time-varying) networks, the distributed sub-gradient algorithm was proposed in~\cite{Nedic2009}.
It and its variants~\cite{Ram2010,Nedic2011} are intuitive and simple but usually slow due to the diminishing step-size that is needed to obtain a consensual and optimal solution, even if the objective functions are differentiable and strongly convex.
With a fixed step-size, these distributed methods can be fast, but they only converge to a neighborhood of the solution set.
This phenomenon creates an exactness-speed dilemma.

A class of distributed approaches that bypasses this dilemma is based on introducing Lagrangian dual.
The resulting algorithms include distributed dual decomposition~\cite{Terelius2011} and decentralized alternating direction method of multipliers (ADMM)~\cite{Bertsekas1997}.
The decentralized ADMM and its proximal-gradient variant can employ a fixed step-size to achieve $O(1/k)$ rate under general convexity assumptions~\cite{Wei2013,Chang2014,Hong2015}.
Under the strong convexity assumption, the decentralized ADMM has been shown to have linear convergence for time-invariant undirected graphs~\cite{Shi2014}.
There exist some other distributed methods that do not (explicitly) use dual variables but can still converge to an exact consensual solution with fixed step-sizes.
In particular, works in~\cite{Chen2012_2,Jakovetic2014} employ multi-consensus inner loops, Nesterov's acceleration, and/or the adapt-then-combine (ATC) strategy. Under the assumption that the objectives have bounded and Lipschtiz gradients\footnote{This means that the nonsmooth terms $r_i$'s are absent. Such assumption is much stronger than the one used for achieving the $O(1/k^2)$ rate in Nesterov's optimal gradient method \cite{nesterov2013introductory}.}, the algorithm proposed in~\cite{Jakovetic2014} is shown to have $O\left(\ln(k)/k^2\right)$ rate.
References~\cite{Shi2015,shi2015proximal} use a difference structure to cancel the steady state error in decentralized gradient descent~\cite{Nedic2009,Kun2014}, thereby developing the algorithm EXTRA and its proximal-gradient variant PG-EXTRA.
It converges at an $O(1/k)$ rate when the objective function in~\eqref{eq:F} is convex, and it has a linear convergence rate when the objective function is strongly convex.

A number of recent works employed the so-called gradient tracking technique~\cite{Zhu2010} in distributed optimization to conquer different issues~\cite{Xu2015,Lorenzo2016,Qu2016,nedich2016achieving,nedic2016geometrically}.
To be specific, works~\cite{Xu2015,nedic2016geometrically} relax the step-size rule to allow uncoordinated step-sizes across agents.
Paper~\cite{Lorenzo2016} solves non-convex optimization problems.
Paper~\cite{nedich2016achieving} aims at achieving geometric convergence over time-varying graphs.
Work~\cite{Qu2016} improves the convergence rate over EXTRA, and its formulation is  the same as that in~\cite{nedic2016geometrically}.

Another topic of interest is decentralized optimization over directed graphs~\cite{Nedic2013,Xi2015,Zeng2015,sun2016distributed,nedich2016achieving}, which is beyond the scope of this paper.

\subsection{Proposed Algorithm}
By making a simple modification over PG-EXTRA~\cite{shi2015proximal}, our proposed algorithm brings a big improvement in the speed and the dependency of convergence over networks. To better expose this simple modification, let us compare our proposed algorithm with the EXTRA algorithm for the smooth case, i.e., $r_i(x)=0$.
\begin{subequations}\label{eq:compare1}
\begin{align}
(\textnormal{EXTRA})\quad&{\mathbf{x}}^{k+2} = ({\mathbf{I}}+{\mathbf{W}}) {\mathbf{x}}^{k+1} - {{\mathbf{I}}+{\mathbf{W}} \over 2}{\mathbf{x}}^k  - \alpha \nabla s({\mathbf{x}}^{k+1})+\alpha \nabla s({\mathbf{x}}^k),\\
(\textnormal{Proposed NIDS})\quad&{\mathbf{x}}^{k+2} =  ({\mathbf{I}}+{\mathbf{W}}){\mathbf{x}}^{k+1} - {{\mathbf{I}}+{\mathbf{W}} \over 2}({\mathbf{x}}^k  {+ \alpha \nabla s({\mathbf{x}}^{k+1})-\alpha \nabla s({\mathbf{x}}^k)}). \label{eq:compare1b}
\end{align}
\end{subequations}
Here in both algorithms\footnote{In the original EXTRA, two mixing matrices ${\mathbf{W}}$ and $\widetilde{{\mathbf{W}}}$ are used. For simplicity, we take $\widetilde{{\mathbf{W}}}=\frac{I+{\mathbf{W}}}{2}$ here.}, the doubly stochastic matrix ${\mathbf{W}}$ is the mixing matrix that is used to represent information exchange between neighboring agents. See Assumption~\ref{assu:1} for more details about setting this matrix. There is only a small difference between EXTRA and the proposed algorithm on what to communicate between the agents. In fact, the ATC strategy is applied on the successive difference of gradients.
Because of this small modification, the proposed algorithm can have \underline{N}etwork \underline{I}n\underline{D}ependent \underline{S}tep-sizes. Therefore we call our proposed algorithm NIDS in the following. For the nonsmooth case, more detailed comparison between PG-EXTRA and NIDS will be followed in Section~\ref{sec:alg}.

The proposed protocol works as long as each agent can estimate their local functional parameters.
There is no need for any agent to have any sense of the global situation including the number of agents in the whole network.
In other words, an agent in the network only needs to agree on the optimization framework and participate computation and information exchange at certain time/frequency with pure local knowledge.
There is no need for any agent to negotiate any system level parameters thus it is less likely to compromise privacy.

{\bf Large step-size of NIDS:}
All of the works mentioned above either employ pessimistic step-sizes or have network dependent bounds on step-sizes.
Furthermore, the step-sizes for the strongly convex case are more conservative.
For example, the linear convergence rate has been achieved by EXTRA in~\cite{Shi2015} with the step-size being in the order of $O(\mu/L^2)$, where $\mu$ is the strong convexity constant of the function $s(x)=\sum_i s_i(x)$.
This step-size has a loss of $\mu/L$ compared to $O(1/L)$ for the centralized gradient descent.
Though faster convergence is achieved in the ATC variant of DIGing~\cite{nedic2016geometrically}, its step-size is still very conservative compared to $O(1/L)$.
We will show that the step-size of NIDS can has the same order as that of the (centralized) gradient descent.
The achievable step-sizes of NIDS for $o(1/k)$ rate in the general convex case and the linear convergence rate in the strongly convex case are at  the order of $O(1/L)$.
Specifically, we can choose the step-size for agent $i$ as large as $2/L_i$ on any connected network.

{\bf Sublinear convergence rate of NIDS for the general case:}
Under the general convexity assumption, we show that NIDS has a convergence rate of $o(1/k)$, which is slightly better than the $O(1/k)$ rate of PG-EXTRA.
Because the step-size of NIDS does not depend on the network topology and is much larger than that of PG-EXTRA, NIDS can be much faster than PG-EXTRA, as shown in the numerical experiments.

{\bf Linear convergence rate of NIDS for the strongly convex case:}
For the case where the non-smooth terms are null and the functions $\{s_i\}_{i=1}^n$ are strongly convex, we show that NIDS achieves a linear convergence rate whose dependencies on the functions $\{s_i\}_{i=1}^n$ and the network topology are decoupled. To be specific, to reach $\epsilon$-accuracy, the number of iterations needed for NIDS is
\[O\left(\max\left(\frac{L}{\mu},\frac{1-\lambda_n({\mathbf{W}})}{1-\lambda_2({\mathbf{W}})}\right)\right)\log\frac{1}{\epsilon}.\]
Both $\frac{L}{\mu}$ and $\frac{1-\lambda_n({\mathbf{W}})}{1-\lambda_2({\mathbf{W}})}$ are typical in the literatures of optimization and average consensus, respectively. The scaling factor $\frac{L}{\mu}$, also called the condition number of the objective function, is aligned with the scalability for the standard gradient descent \cite{nesterov2013introductory}. The scaling factor $\frac{1-\lambda_n({\mathbf{W}})}{1-\lambda_2({\mathbf{W}})}=O(n^2)$, could also be understood as the condition number\footnote{When we heuristically choose ${\mathbf{W}}=I-\tau\textbf{\L}$ where $\textbf{\L}$ is the Laplacian of the underlying graph and $\tau$ is a positive tunable constant, we have $\frac{1-\lambda_n({\mathbf{W}})}{1-\lambda_2({\mathbf{W}})}=\frac{\lambda_1(\textbf{\L})}{\lambda_{n-1}(\textbf{\L})}$ which is the condition number of $\textbf{\L}$. Note that $\lambda_{n}(\textbf{\L})=0$.} of the network, is aligned with the scalability of the simplest linear iterations for distributed averaging \cite{nedic2009distributed}.

Separating the condition numbers of the objective function and the network provides a way to determine the bottleneck of NIDS for a specific problem and a given network.
Therefore, the system designer might be able to smartly apply preconditioning on $\{s_i\}_{i=1}^n$ or improve the connectivity of the network to cost-effectively obtain a better convergence.

Finally, we note that, references~\cite{yuan2017exact1,yuan2017exact2}, appearing simultaneously with this work, also proposed~\eqref{eq:compare1b} to enlarge the step-size and use column stochastic matrices rather than symmetric doubly stochastic matrices.
However, their algorithm only works for smooth problems, and their analysis seems to be restrictive and requires twice differentiability and strong convexity of $\{s_i\}_{i=1}^n$.

\subsection{Future Works}
The capability of our algorithm using purely locally determined parameters increases its potential to be extended to working over dynamic networks with time-varying number of nodes. Given such flexibility, we may use similar scheme to solve the decentralized empirical risk minimization problems. Furthermore, it also enhances the privacy of the agents through allowing each to perform their own optimization procedure without negotiation on any parameters.

By using Nesterov's acceleration technique, reference \cite{Olshevsky2014} shows that the scaling factor of a new average consensus protocol can be improved to $O(n)$; When the nonsmooth terms $r_i$'s are absent, reference \cite{scaman2017optimal} shows that the scaling factor of a new dual based accelerated distributed gradient method can be improved to $O(\sqrt{L/\mu})$. One of our future work would be exploring the convergence rates/scalability of the Nesterov's accelerated version of our algorithm.

\subsection{Paper Organization}
The rest of this paper is organized as follows.
To facilitate the description of the technical ideas, the algorithms, and the analysis, we introduce the notation in Subsection~\ref{sec:notation}.
In Section~\ref{sec:alg}, we introduce our algorithm NIDS and discuss its relation to some other existing algorithms.
In Section~\ref{sec:conv_analysis}, we first show that NIDS can be understood as an iterative algorithm for seeking a fixed point.
Following this, we establish that NIDS converges at an $o(1/k)$ rate for the general case and a linear rate for the strongly convex case.
Then, numerical simulations are given in Section~\ref{sec:num_exp} to corroborate our theoretical claims.
Final remarks are given in Section~\ref{sec:concl}.

\subsection{Notation}\label{sec:notation}

\input{Sec2}

\input{Sec3}

\section{Conclusion}\label{sec:concl}
In this paper, we proposed a novel decentralized consensus algorithm NIDS whose step-size does not depend on the network structure.
The connection between NIDS and PG-EXTRA is that NIDS applies the ATC strategy on the successive gradient.
In NIDS, the step-size depends {\it only} on the objective function, and it can be as large as $2/L$, where $L$ is the Lipschitz constant of the gradient of the smooth function.
We showed that NIDS converges at the $o(1/k)$ rate for the general convex case and at the linear rate for the strongly convex case.
For the strongly convex case, we separated the linear convergence rate's dependence on the objective function and the network.
The separated convergence rates match the typical rates for the general gradient descent and the consensus averaging.
Furthermore, every agent in the network can choose its own step-size independently by its own objective function.
Numerical experiments validated the theoretical results and demonstrated better performance of NIDS over the state-of-the-art algorithms.
Because the step-size of NIDS does not depend on the network structure, there are many possible future extensions.
One extension is to apply NIDS on dynamic networks where nodes can join and drop off.

\bibliographystyle{siam}

\section{Introduction}
Agent $i$ holds a local variable $x_i \in \mathbb{R}^{p}$, whose value at the $k$th iteration is denoted by $x_i^k$ . We introduce an objective function that sums all the local ones as
\begin{equation}
{f}({\mathbf{x}}):=\frac{1}{n}\sum_{i=1}^{n}(s_{i}(x_i)+r_i(x_i))
\end{equation}
where
\begin{equation}\label{eq:define_x}
{\mathbf{x}}:=
\begin{pmatrix}
	-& x_1^\top &- \\
-	& x_2^\top &- \\
	& \vdots & \\
	-& x_n^\top &-
\end{pmatrix}
\in \mathbb{R}^{n\times p}.
\end{equation}
If all local variables are identical, i.e., $x_{1}=\cdots=x_{n}$, we call that ${\mathbf{x}}$ is consensual.
In addition, we define
\begin{align}
{s}({\mathbf{x}}):=\frac{1}{n}\sum_{i=1}^{n}s_{i}(x_i), \quad
{r}({\mathbf{x}}):=\frac{1}{n}\sum_{i=1}^{n}r_{i}(x_i).
\end{align}
Therefore, $f({\mathbf{x}})=s({\mathbf{x}})+r({\mathbf{x}})$.
The gradient of $s$ at ${\mathbf{x}}$ is given in the same way as ${\mathbf{x}}$ in~\eqref{eq:define_x} by
\begin{equation}
\nabla s ({\mathbf{x}}):=
\begin{pmatrix}
-& \left(\nabla s_{1}(x_{1})\right)^{\top} &- \\
-	& \left(\nabla s_{2}(x_{2})\right)^{\top} &- \\
& \vdots & \\
-& \left(\nabla s_{n}(x_{n})\right)^{\top} &-
\end{pmatrix}
\in \mathbb{R}^{n\times p}.
\end{equation}
We use bold upper-case letters such as ${\mathbf{W}}$ to define matrix in $\mathbb{R}^{n\times n}$ and bold lower-case letter such as ${\mathbf{x}}$ and ${\mathbf{z}}$ to define matrix in $\mathbb{R}^{n\times p}$.
Let ${\mathbf{1}}$ and $\mathbf{0}$ be matrices with all ones and zeros, respectively, and their dimensions are provided when necessary.
For matrices ${\mathbf{x}}, {\mathbf{y}}\in\mathbb{R}^{n\times p}$, we define the inner product of ${\mathbf{x}}$ and ${\mathbf{y}}$ as $\langle {\mathbf{x}},{\mathbf{y}}\rangle={\tilde{r}}({\mathbf{x}}^\top{\mathbf{y}})$ and the induced norm as $\|{\mathbf{x}}\|=\sqrt{\langle {\mathbf{x}},{\mathbf{x}}\rangle}$.
Additionally, by an abuse of notation, we define $\langle {\mathbf{x}},{\mathbf{y}}\rangle_{\mathbf{Q}} = {\tilde{r}}({\mathbf{x}}^\top{\mathbf{Q}}{\mathbf{y}})$ and $\|{\mathbf{x}}\|_{\mathbf{Q}}^2=\langle {\mathbf{x}},{\mathbf{x}}\rangle_{\mathbf{Q}}$ for any given symmetric matrix ${\mathbf{Q}}\in\mathbb{R}^{n\times n}$.
Note that $\langle\cdot,\cdot\rangle_{\mathbf{Q}}$ is an inner product defined in $\mathbb{R}^{n\times p}$ if and only if ${\mathbf{Q}}$ is positive definite.
However, when ${\mathbf{Q}}$ is not positive definite, $\langle{\mathbf{x}},{\mathbf{y}}\rangle_{\mathbf{Q}}$ can still be an inner product defined in a subspace of $\mathbb{R}^{n\times p}$, see Lemma~\ref{lemma:equiv_norm} for more details.
We define the range of ${\mathbf{A}}\in \mathbb{R}^{n\times n}$ by $\range({\mathbf{A}}):=\{{\mathbf{x}}\in \mathbb{R}^{n\times p}:{\mathbf{x}}={\mathbf{A}}{\mathbf{y}},~{\mathbf{y}}\in\mathbb{R}^{n\times p}\}$.
Let $\lambda_i({\mathbf{A}})$ define the $i$th largest eigenvalue of a symmetric matrix ${\mathbf{A}}$.
The largest eigenvalue of a symmetric matrix ${\mathbf{A}}$ is also denoted as $\lambda_{\max}({\mathbf{A}})$.
For two symmetric matrices ${\mathbf{A}},{\mathbf{B}}\in\mathbb{R}^{n\times n}$, ${\mathbf{A}}\succ{\mathbf{B}}$ (or ${\mathbf{A}}\succcurlyeq{\mathbf{B}}$) means that ${\mathbf{A}}-{\mathbf{B}}$ is positive definite (or positive semidefinite).

\section{Proposed Algorithm NIDS}\label{sec:alg}
In this section, we describe our proposed NIDS in Algorithm~\ref{alg:alg1} for solving~\eqref{eq:F} in more detail and explain the connections between other related methods.
\begin{algorithm}
	\caption{NIDS}
	\begin{algorithmic}\label{alg:alg1}
		\STATE Set mixing matrix: ${\mathbf{W}} \in \mathbb{R}^{n\times n}$;
		\STATE Choose parameters: $\{\alpha_i\}_{i=1}^n$, $c$, and $\widetilde{\mathbf{W}}:=[\widetilde w_{ij}]\in\mathbb{R}^{n\times n}$;

		\STATE all agents $i=1,\cdots,n$ pick arbitrary initial $x_i^0 \in \mathbb{R}^{p}$ and do
			\begin{align*}
			z_i^{1} & = x_i^{0}-\alpha_i\nabla s_i\left(x_i^{0}\right), \\
			x_i^{1} & = \argmin\limits_{x\in\mathbb{R}^p}~\alpha_ir_i(x)+\frac{1}{2}\|x-z_i^{1}\|^{2}.
			\end{align*}
		\FOR {$k=1,2,3\ldots$}
		  \STATE all agents $i=1,\cdots,n$ do
			\begin{align*}
			z_i^{k+1} & =  z_i^{k}-x_i^k+\sum_{j=1}^{n}\widetilde w_{ij} \left(2x_j^{k}-x_j^{k-1}-\alpha_j\nabla s_j\left(x_j^{k}\right)+\alpha_j\nabla s_j\left(x_j^{k-1}\right)\right), \\
			x_i^{k+1} & = \argmin\limits_{x\in\mathbb{R}^p}~\alpha_i r_i(x)+\frac{1}{2}\|x-z_i^{k+1}\|^{2}.
			\end{align*}
		\ENDFOR

	\end{algorithmic}
\end{algorithm}

The mixing matrix satisfies the following assumption, which comes from~\cite{shi2015proximal,Shi2015}.
\begin{assumption}[Mixing matrix]\label{assu:1}
The connected network ${\mathcal{G}}=\{{\mathcal{V}},{\mathcal{E}}\}$ consists of a set of agents ${\mathcal{V}}=\{1,2,\cdots,n\}$ and a set of undirected edges ${\mathcal{E}}$.
An undirected edge $(i,j)\in{\mathcal{E}}$ means that there is a connection between agents $i$ and $j$ and both agents can exchange data.
The mixing matrix ${\mathbf{W}}=[w_{ij}]\in \mathbb{R}^{n\times n}$ satisfies:
\begin{enumerate}
\item \textnormal{(Decentralized property).} If $i\neq j$ and $(i,j)\notin {\mathcal{E}}$, then $w_{ij}=0$;
\item	\textnormal{(Symmetry).} ${\mathbf{W}} = {\mathbf{W}}^T$;
\item	\textnormal{(Null space property).} $\mathbf{Null}({\mathbf{I}}-{\mathbf{W}})=\mathbf{span}({\mathbf{1}}_{n\times 1})$;
\item \textnormal{(Spectral property).} $2{\mathbf{I}} \succcurlyeq {\mathbf{W}}+{\mathbf{I}}\succ \mathbf{0}_{n\times n}$.
\end{enumerate}
\end{assumption}

\begin{remark}\label{remark:W}
Assumption~\ref{assu:1} implies that the eigenvalues of ${\mathbf{W}}$ lie in $(-1,1]$ and the multiplicity of eigenvalue $1$ is one, i.e., $1=\lambda_1({\mathbf{W}})>\lambda_2({\mathbf{W}})\geq \cdots \geq \lambda_n({\mathbf{W}})>-1$.
Item 3 of Assumption~\ref{assu:1} shows that $({\mathbf{I}}-{\mathbf{W}}){\mathbf{1}}_{n\times 1} = \mathbf{0}$ and the orthogonal complement of $\mathbf{span}({\mathbf{1}}_{n\times 1})$ is the row space of ${\mathbf{I}}-{\mathbf{W}}$, which is also the column space of ${\mathbf{I}}-{\mathbf{W}}$ because of the symmetry of ${\mathbf{W}}$.
\end{remark}

The functions $\{s_i\}_{i=1}^n$ and $\{r_i\}_{i=1}^n$ satisfy the following assumption.
\begin{assumption} \label{lemma:cocoerciveness}
Functions $\{s_i(x)\}_{i=1}^n$ and $\{r_i(x)\}_{i=1}^n$ are lower semi-continuous proper convex, and $\{s_i(x)\}_{i=1}^n$ have Lipschitz continuous gradients with constants $\{L_i\}_{i=1}^n$, respectively. Thus, we have
\begin{equation}\label{for:cocoer}
\langle {\mathbf{x}}-{\mathbf{y}},\nabla s({\mathbf{x}})-\nabla s({\mathbf{y}})\rangle\geq \left\| \nabla s\left({\mathbf{x}}\right)-\nabla s\left({\mathbf{y}}\right)\right\|_{{\mathbf{L}}^{-1}}^{2},
\end{equation}
where ${\mathbf{L}}=\Diag(L_1,\cdots,L_n)$ is the diagonal matrix with the Lipschitz constants~\cite{nesterov2013introductory}.
\end{assumption}

Instead of using the same step-size for all the agents, we allow agent $i$ to choose its own step-size $\alpha_i$ and let $\Lambda=\Diag(\alpha_1,\cdots,\alpha_n)\in \mathbb{R}^{n\times n}$.
Then NIDS can be expressed as
\begin{subequations}\label{for:alg1}
	\begin{align}
	{\mathbf{z}}^{k+1} = & {\mathbf{z}}^{k}-{\mathbf{x}}^k +\widetilde {\mathbf{W}}(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1}-\Lambda\nabla s({\mathbf{x}}^k)+\Lambda\nabla s({\mathbf{x}}^{k-1})), \label{for:alg1_z}\\
	{\mathbf{x}}^{k+1} = & \argmin\limits_{{\mathbf{x}}\in\mathbb{R}^{n\times p}}~r({\mathbf{x}})+\frac{1}{2}\|{\mathbf{x}}-{\mathbf{z}}^{k+1}\|_{\Lambda^{-1}}^{2}, \label{for:alg1_x}
	\end{align}
\end{subequations}
where $\widetilde{\mathbf{W}} = {\mathbf{I}}-c\Lambda({\mathbf{I}}-{\mathbf{W}})$ and $c$ is chosen such that $\Lambda^{-1/2}\widetilde{\mathbf{W}}\Lambda^{1/2}={\mathbf{I}}-c\Lambda^{1/2}({\mathbf{I}}-{\mathbf{W}})\Lambda^{1/2}\succ \mathbf{0}$.

If all agents choose the same step-size, i.e., $\Lambda=\alpha{\mathbf{I}}$. We can choose $c=1/(2\alpha)$ from Assumption~\ref{assu:1}, and~\eqref{for:alg1} becomes
\begin{subequations}
	\begin{align}
	{\mathbf{z}}^{k+1} & = {\mathbf{z}}^{k}-{\mathbf{x}}^k+{{\mathbf{I}}+{\mathbf{W}}\over 2}(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1}-\alpha\nabla s({\mathbf{x}}^k)+\alpha\nabla s({\mathbf{x}}^{k-1})),\\
	{\mathbf{x}}^{k+1} & = \argmin\limits_{{\mathbf{x}}\in\mathbb{R}^{n\times p}}~r({\mathbf{x}})+\frac{1}{2\alpha}\|{\mathbf{x}}-{\mathbf{z}}^{k+1}\|^{2}.
	\end{align}
\end{subequations}

\begin{remark} When the mixing matrix $\widetilde{{\mathbf{W}}}$ in the PG-EXTRA algorithm is typically chosen as $\widetilde{{\mathbf{W}}}=\frac{I+{\mathbf{W}}}{2}$, the updates of PG-EXTRA algorithm are equivalent to
\begin{subequations}\label{pg-extra}
	\begin{align}
	{\mathbf{z}}^{k+1} & = {\mathbf{z}}^{k}-{\mathbf{x}}^k+{{\mathbf{I}}+{\mathbf{W}}\over 2}(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1})-\alpha\nabla s({\mathbf{x}}^k)+\alpha\nabla s({\mathbf{x}}^{k-1}),\\
	{\mathbf{x}}^{k+1} & = \argmin\limits_{{\mathbf{x}}\in\mathbb{R}^{n\times p}}~r({\mathbf{x}})+\frac{1}{2\alpha}\|{\mathbf{x}}-{\mathbf{z}}^{k+1}\|^{2}.
	\end{align}
\end{subequations}
The only difference between NIDS and PG-EXTRA is that the mixing operation is further applied to the successive difference of the gradients $-\alpha\nabla s({\mathbf{x}}^k)+\alpha\nabla s({\mathbf{x}}^{k-1})$ in NIDS.
\end{remark}

When there is no nonsmooth function $r({\mathbf{x}})$,~\eqref{for:alg1} becomes
\begin{align}
	{\mathbf{x}}^{k+1} = &\widetilde {\mathbf{W}}(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1}-\Lambda\nabla s({\mathbf{x}}^k)+\Lambda\nabla s({\mathbf{x}}^{k-1})),
\end{align}
and it reduces to~\eqref{eq:compare1b} when $\Lambda=\alpha{\mathbf{I}}$ and $c=1/(2\alpha)$.
Note that, though~\eqref{eq:compare1b} appears in~\cite{yuan2017exact1,yuan2017exact2}, its convergence still needs a small step-size that also depends on the network topology and the strongly convex constant.
In Theorem 1 of~\cite{yuan2017exact2}, the upper bound for the step-size is also $O(\mu/L^2)$, which is the same as that of PG-EXTRA.

\section{Convergence Analysis of NIDS}\label{sec:conv_analysis}
In order to show the convergence of NIDS, we also need the following assumption.
\begin{assumption}[Solution existence]
Problem~\eqref{eq:F} has at least one solution.
\end{assumption}

To simplify the analysis, we introduce a new sequence $\{{\mathbf{d}}^{k}\}_{k\geq0}$ which is defined as
\begin{align}\label{def:d}
{\mathbf{d}}^{k}:={\Lambda^{-1}}({\mathbf{x}}^{k-1}-{\mathbf{z}}^k)-\nabla s\left({\mathbf{x}}^{k-1}\right).
\end{align}
By using the sequence $\{{\mathbf{x}}^{k}\}_{k\geq0}$, we obtain a recursive  (update) relation for $\{{\mathbf{d}}^{k}\}_{k\geq0}$:
\begin{align*}
      {\mathbf{d}}^{k+1}
=		& {\Lambda^{-1}}({\mathbf{x}}^{k}-{\mathbf{z}}^{k+1})-\nabla s({\mathbf{x}}^{k}) \\
=		& {\Lambda^{-1}}({\mathbf{x}}^{k}-{\mathbf{z}}^k+{\mathbf{x}}^k)-\nabla s({\mathbf{x}}^k)\\
    & -{\Lambda^{-1}}\widetilde{\mathbf{W}}(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1}-\Lambda\nabla s({\mathbf{x}}^k)+\Lambda\nabla s({\mathbf{x}}^{k-1})) \\
=		& {\Lambda^{-1}}({\mathbf{x}}^{k}-{\mathbf{z}}^k+{\mathbf{x}}^k-2{\mathbf{x}}^k+{\mathbf{x}}^{k-1})-\nabla s({\mathbf{x}}^{k})+\nabla s({\mathbf{x}}^k)-\nabla s({\mathbf{x}}^{k-1}) \\
    & +c({\mathbf{I}}-{\mathbf{W}})(2{\mathbf{x}}^k-{\mathbf{x}}^{k-1}-\Lambda\nabla s({\mathbf{x}}^k)+\Lambda\nabla s({\mathbf{x}}^{k-1})) \\
=		& {\mathbf{d}}^k+c({\mathbf{I}}-{\mathbf{W}})(2{\mathbf{x}}^k-{\mathbf{z}}^{k}-\Lambda\nabla s({\mathbf{x}}^k)-\Lambda{\mathbf{d}}^k),
\end{align*}
where the second equality comes from the update of ${\mathbf{z}}^{k+1}$ in~\eqref{for:alg1_z} and the last one holds because of the definition of ${\mathbf{d}}^k$ in~\eqref{def:d}.
Therefore, the iteration~\eqref{for:alg1} is equivalent to, with the update order $({\mathbf{x}},{\mathbf{d}},{\mathbf{z}})$,
\begin{subequations}\label{for:alg2}
\begin{align}
{\mathbf{x}}^{k}   &  = \argmin\limits_{{\mathbf{x}}\in\mathbb{R}^{n\times p}}~r({\mathbf{x}})+\frac{1}{2 }\|{\mathbf{x}}-{\mathbf{z}}^{k}\|_{\Lambda^{-1}}^{2}, \label{for:alg2_x} \\
{\mathbf{d}}^{k+1} & ={\mathbf{d}}^k + c({\mathbf{I}}-{\mathbf{W}})\left(2{\mathbf{x}}^{k}-{\mathbf{z}}^{k}-\Lambda\nabla s\left({\mathbf{x}}^{k}\right)-\Lambda{\mathbf{d}}^k\right), \label{for:alg2_d}\\
{\mathbf{z}}^{k+1} & = {\mathbf{x}}^{k}-\Lambda\nabla s\left({\mathbf{x}}^{k}\right)-\Lambda{\mathbf{d}}^{k+1}, \label{for:alg2_z}
\end{align}
\end{subequations}
in the sense that both \eqref{for:alg1} and \eqref{for:alg2} generate the same $\{{\mathbf{x}}^k,{\mathbf{z}}^k\}_{k>0}$ sequence.

Because ${\mathbf{x}}^k$ is determined by ${\mathbf{z}}^k$ only and can be eliminated from the iteration, iteration~\eqref{for:alg2} is essentially an operator for $({\mathbf{d}},{\mathbf{z}})$.
Note that we have ${\mathbf{d}}^1={\Lambda^{-1}}({\mathbf{x}}^{0}-{\mathbf{z}}^1)-\nabla s\left({\mathbf{x}}^{0}\right)=\mathbf{0}$ from Algorithm~\ref{alg:alg1}.
Therefore, from the update of ${\mathbf{d}}^{k+1}$ in~\eqref{for:alg2_d}, ${\mathbf{d}}^k\in\range({\mathbf{I}}-{\mathbf{W}})$ for all $k$.
In fact, any ${\mathbf{z}}^1$ such that ${\mathbf{d}}^1\in\range({\mathbf{I}}-{\mathbf{W}})$ works for NIDS.
The following two lemmas show the relation between fixed points of~\eqref{for:alg2} and optimal solutions of~\eqref{eq:F}.

\begin{lemma}[Fixed point of~\eqref{for:alg2}]\label{lemma:fixedpoint}
$({\mathbf{d}}^*,{\mathbf{z}}^*)$ is a fixed point of~\eqref{for:alg2} if and only if there exists a subgradient ${\mathbf{q}}^*\in\partial r({\mathbf{x}}^*)$  such that:
\begin{subequations}
\begin{align}
&{\mathbf{d}}^* + \nabla s({\mathbf{x}}^*)+{\mathbf{q}}^* = \mathbf{0} ,\label{for:fpopt1}\\
&({\mathbf{I}}-{\mathbf{W}}){\mathbf{x}}^*=\mathbf{0} .\label{for:fpopt2}
\end{align}
\end{subequations}
and ${\mathbf{z}}^*={\mathbf{x}}^*+\Lambda{\mathbf{q}}^*$.
\end{lemma}

\begin{proof}
``$\Rightarrow$"
If $({\mathbf{d}}^*,{\mathbf{z}}^*)$ is a fixed point of~\eqref{for:alg2}, we have
\begin{align*}
\mathbf{0} =  c({\mathbf{I}}-{\mathbf{W}})\left(2{\mathbf{x}}^{*}-{\mathbf{z}}^{*}-\Lambda\nabla s\left({\mathbf{x}}^{*}\right)-\Lambda{\mathbf{d}}^*\right)=  c({\mathbf{I}}-{\mathbf{W}}){\mathbf{x}}^{*},
\end{align*}
where the two equalities come from~\eqref{for:alg2_d} and~\eqref{for:alg2_z}, respectively.
Combining~\eqref{for:alg2_z} and~\eqref{for:alg2_x} gives
\begin{align*}
\mathbf{0} = {\mathbf{z}}^* - {\mathbf{x}}^{*}+\Lambda\nabla s({\mathbf{x}}^{*})+\Lambda{\mathbf{d}}^{*} = \Lambda ({\mathbf{q}}^*+\nabla s({\mathbf{x}}^{*})+{\mathbf{d}}^*),
\end{align*}
where ${\mathbf{q}}^*\in\partial r({\mathbf{x}}^*)$.

``$\Leftarrow$"
In order to show that $({\mathbf{d}}^*,{\mathbf{z}}^*)$ is a fixed point of iteration~\eqref{for:alg2}, we just need to verify that $({\mathbf{d}}^{k+1},{\mathbf{z}}^{k+1})=({\mathbf{d}}^*,{\mathbf{z}}^*)$ if $({\mathbf{d}}^k,{\mathbf{z}}^k)=({\mathbf{d}}^*,{\mathbf{z}}^*)$.
From~\eqref{for:alg2_x}, we have ${\mathbf{x}}^k={\mathbf{x}}^*$, then
\begin{align*}
{\mathbf{d}}^{k+1} = & {\mathbf{d}}^* + c({\mathbf{I}}-{\mathbf{W}})\left(2{\mathbf{x}}^*-{\mathbf{z}}^*-\Lambda\nabla s\left({\mathbf{x}}^*\right)-\Lambda{\mathbf{d}}^*\right)=  {\mathbf{d}}^* + c({\mathbf{I}}-{\mathbf{W}}){\mathbf{x}}^*={\mathbf{d}}^*,\\
{\mathbf{z}}^{k+1} = & {\mathbf{x}}^*-\Lambda\nabla s\left({\mathbf{x}}^*\right)-\Lambda{\mathbf{d}}^{*} ={\mathbf{x}}^*+\Lambda{\mathbf{q}}^*={\mathbf{z}}^*.
\end{align*}
Therefore, we have $({\mathbf{d}}^*,{\mathbf{z}}^*)$ being a fixed point of iteration~\eqref{for:alg2}.
\end{proof}

\begin{lemma}[Optimality condition]\label{lemma:condition}
${\mathbf{x}}^*$ is consensual with $x^*_1=x^*_2=\cdots=x^*_n=x^*$ being an optimal solution of problem~\eqref{eq:F} if and only if there exists ${\mathbf{p}}^*$ and a subgradient ${\mathbf{q}}^*\in\partial r({\mathbf{x}}^*)$  such that:
\begin{subequations}
\begin{align}
&({\mathbf{I}}-{\mathbf{W}}){\mathbf{p}}^* + \nabla s({\mathbf{x}}^*)+{\mathbf{q}}^* = \mathbf{0} ,\label{for:opt1}\\
&({\mathbf{I}}-{\mathbf{W}}){\mathbf{x}}^*=\mathbf{0} .\label{for:opt2}
\end{align}
\end{subequations}
In addition, $({\mathbf{d}}^*=({\mathbf{I}}-{\mathbf{W}}){\mathbf{p}}^*, {\mathbf{z}}^*={\mathbf{x}}^*+\Lambda{\mathbf{q}}^*)$ is a fixed point of iteration~\eqref{for:alg2}.
\end{lemma}

\begin{proof}
``$\Rightarrow$"
Because ${\mathbf{x}}^*={\mathbf{1}}_{n\times 1} (x^*)^\top$,  we have $({\mathbf{I}}-{\mathbf{W}}){\mathbf{x}}^*=({\mathbf{I}}-{\mathbf{W}}){\mathbf{1}}_{n\times 1} (x^*)^\top=\mathbf{0}_{n\times 1}(x^*)^\top=\mathbf{0}$.
The fact that $x^*$ is an optimal solution of problem~\eqref{eq:F} means there exists ${\mathbf{q}}^*\in\partial r({\mathbf{x}}^*)$ such that $(\nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*)^\top{\mathbf{1}}_{n\times 1} = \mathbf{0}$.
That is to say all columns of $\nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*$ are orthogonal to ${\mathbf{1}}_{n\times 1}$.
Therefore, Remark~\ref{remark:W} shows the existence of ${\mathbf{p}}^*$ such that $({\mathbf{I}}-{\mathbf{W}}){\mathbf{p}}^*+\nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*=\mathbf{0}$.

``$\Leftarrow$"
Equation~\eqref{for:opt2} shows that ${\mathbf{x}}^*$ is consensual because of item 3 of Assumption~\ref{assu:1}, i.e., ${\mathbf{x}}^*={\mathbf{1}}_{n\times 1}(x^*)^\top$ for some $x^*$.
From~\eqref{for:opt1}, we have $\mathbf{0} =(({\mathbf{I}}-{\mathbf{W}}){\mathbf{p}}^* + \nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*)^\top {\mathbf{1}}_{n\times 1}=({\mathbf{p}}^*)^\top({\mathbf{I}}-{\mathbf{W}}) {\mathbf{1}}_{n\times 1}+(\nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*)^\top {\mathbf{1}}_{n\times 1}=(\nabla s({\mathbf{x}}^*)+{\mathbf{q}}^*)^\top {\mathbf{1}}_{n\times 1}$.
Thus, $\mathbf{0}\in \sum_{i=1}^n(\nabla s_i(x^*)+\partial r_i(x^*))$ because ${\mathbf{x}}^*$ is consensual. This completes the proof for the equivalence.

Lemma~\ref{lemma:fixedpoint} shows that $({\mathbf{d}}^*=({\mathbf{I}}-{\mathbf{W}}){\mathbf{p}}^*, {\mathbf{z}}^*={\mathbf{x}}^*+\Lambda{\mathbf{q}}^*)$ is a fixed point of iteration~\eqref{for:alg2}.
\end{proof}

Lemma~\ref{lemma:condition} shows that we can find a fixed point of iteration~\eqref{for:alg2} to obtain an optimal solution of problem~\eqref{eq:F}.
In addition, Lemma~\ref{lemma:condition} tells us that we need ${\mathbf{d}}^*\in\range({\mathbf{I}}-{\mathbf{W}})$ to get the optimal solution of problem~\eqref{eq:F}.
Therefore, we need ${\mathbf{d}}^1\in\range({\mathbf{I}}-{\mathbf{W}})$.

\begin{lemma}[Norm over range space]\label{lemma:equiv_norm}
For any symmetric positive semidefinite matrix ${\mathbf{A}}\in \mathbb{R}^{n\times n}$ with rank $r$ ($r\leq n$),
let $\lambda_1\geq \lambda_2\geq \cdots\geq \lambda_r>0$ be its $r$ eigenvalues.
Then $\range({\mathbf{A}})$ is a $rp$-dimensional subspace in $\mathbb{R}^{n\times p}$ and has a norm defined by $\|{\mathbf{x}}\|^2_{{\mathbf{A}}^\dagger}:=\langle {\mathbf{x}}, {\mathbf{A}}^\dagger {\mathbf{x}}\rangle$, where ${\mathbf{A}}^\dagger$ is the pseudo inverse of ${\mathbf{A}}$.
In addition, $\lambda_1^{-1}\|{\mathbf{x}}\|^2\leq \|{\mathbf{x}}\|^2_{{\mathbf{A}}^\dagger}\leq \lambda_r^{-1}\|{\mathbf{x}}\|^2$ for all ${\mathbf{x}}\in\range({\mathbf{A}})$.
\end{lemma}
\begin{proof}
Let ${\mathbf{A}}={\mathbf{U}}\Sigma {\mathbf{U}}^\top$, where $\Sigma=\Diag(\lambda_1,\lambda_2,\cdots,\lambda_r)$ and the columns of ${\mathbf{U}}$ are orthonormal eigenvectors for corresponding eigenvalues, i.e., ${\mathbf{U}}\in \mathbb{R}^{n\times r}$ and ${\mathbf{U}}^\top {\mathbf{U}}={\mathbf{I}}_{r\times r}$.
Then ${\mathbf{A}}^\dagger={\mathbf{U}}\Sigma^{-1}{\mathbf{U}}^\top$, where $\Sigma^{-1} = \Diag(\lambda_1^{-1},\lambda_2^{-1},\cdots,\lambda_r^{-1})$.

Letting ${\mathbf{x}}={\mathbf{A}} {\mathbf{y}}$, we have $\|{\mathbf{x}}\|^2 = \langle {\mathbf{U}}\Sigma {\mathbf{U}}^\top {\mathbf{y}}, {\mathbf{U}}\Sigma {\mathbf{U}}^\top {\mathbf{y}}\rangle = \langle \Sigma {\mathbf{U}}^\top {\mathbf{y}}, \Sigma {\mathbf{U}}^\top {\mathbf{y}}\rangle = \|\Sigma {\mathbf{U}}^\top {\mathbf{y}}\|^2$. In addition,
\begin{align*}
\langle {\mathbf{x}}, {\mathbf{A}}^\dagger {\mathbf{x}}\rangle=\langle {\mathbf{A}} {\mathbf{y}}, {\mathbf{A}}^\dagger {\mathbf{A}} {\mathbf{y}}\rangle = & \langle {\mathbf{U}}\Sigma {\mathbf{U}}^\top {\mathbf{y}}, {\mathbf{U}}\Sigma^{-1}{\mathbf{U}}^\top {\mathbf{U}}\Sigma {\mathbf{U}}^\top {\mathbf{y}}\rangle =\langle \Sigma {\mathbf{U}}^\top {\mathbf{y}}, \Sigma^{-1}\Sigma {\mathbf{U}}^\top {\mathbf{y}}\rangle.
\end{align*}
Therefore,
\begin{align}\label{for:equiv_norm}
\lambda^{-1}_1 \|{\mathbf{x}}\|^2 =\lambda^{-1}_1 \|\Sigma {\mathbf{U}}^\top {\mathbf{y}}\|^2 \leq \langle {\mathbf{x}}, {\mathbf{A}}^\dagger {\mathbf{x}}\rangle \leq \lambda^{-1}_r \|\Sigma {\mathbf{U}}^\top {\mathbf{y}}\|^2 = \lambda^{-1}_r \|{\mathbf{x}}\|^2,
\end{align}
which means that $\|\cdot\|^2_{{\mathbf{A}}^\dagger}=\langle \cdot, {\mathbf{A}}^\dagger\cdot\rangle$ is a norm for $\range({\mathbf{A}})$.
\end{proof}

Let ${\mathbf{M}}=c^{-1}({\mathbf{I}}-{\mathbf{W}})^\dagger-\Lambda$ and we have the following proposition.
\begin{proposition} $\|\cdot\|_{{\mathbf{M}}}$ is a norm defined for $\range({\mathbf{I}}-{\mathbf{W}})$.
\end{proposition}
\begin{proof}
Rewrite the matrix ${\mathbf{M}}$ as
\begin{align*}
{\mathbf{M}} = & c^{-1}({\mathbf{I}}-{\mathbf{W}})^\dagger-\Lambda= \Lambda^{1/2}(c^{-1}\Lambda^{-1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger\Lambda^{-1/2}-{\mathbf{I}})\Lambda^{1/2}\\
    = & \Lambda^{1/2}((c\Lambda^{1/2}({\mathbf{I}}-{\mathbf{W}})\Lambda^{1/2})^\dagger-{\mathbf{I}})\Lambda^{1/2}.
\end{align*}
Then, the proposition holds by using Lemma~\ref{lemma:equiv_norm} and the condition $\Lambda^{-1/2}\widetilde{\mathbf{W}}\Lambda^{1/2}$ being positive definite, which implies ${\mathbf{I}}\succ c\Lambda^{1/2}({\mathbf{I}}-{\mathbf{W}})\Lambda^{1/2} \succ\mathbf{0}$.

\end{proof}

The following lemma compares the distance to a fixed point of~\eqref{for:alg2} for two consecutive iterates.

\begin{lemma}[Fundamental inequality]\label{lemma:powerIneq}
Let $({\mathbf{d}}^*,{\mathbf{z}}^*)$ be a fixed point of iteration~\eqref{for:alg2} and ${\mathbf{d}}^*\in\range({\mathbf{I}}-{\mathbf{W}})$, then
\begin{align}
&\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 \nonumber\\
\leq		& \|{\mathbf{z}}^{k}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}-\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2  \label{for:powerIneq}
\\
&  +2\langle\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right),{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\rangle-2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle.\nonumber
\end{align}
\end{lemma}

\begin{proof}
From the update of ${\mathbf{z}}^{k+1}$ in~\eqref{for:alg2_z}, we have
\begin{align}
 & \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^*,{\mathbf{z}}^{k+1}-{\mathbf{z}}^k+{\mathbf{x}}^k-{\mathbf{x}}^*\rangle\nonumber\\
=& \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},2{\mathbf{x}}^{k}-{\mathbf{z}}^{k}-\Lambda\nabla s({\mathbf{x}}^{k})-\Lambda{\mathbf{d}}^{k+1}-{\mathbf{x}}^*\rangle \nonumber\\
=& \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},c^{-1}({\mathbf{I}}-{\mathbf{W}})^\dagger({\mathbf{d}}^{k+1}-{\mathbf{d}}^k)+\Lambda{\mathbf{d}}^{k}-\Lambda{\mathbf{d}}^{k+1}\rangle\nonumber\\
=& \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^*,{\mathbf{d}}^{k+1}-{\mathbf{d}}^k\rangle_{\mathbf{M}}, \label{for:main_ineq_1}
\end{align}
where the second equality comes from~\eqref{for:alg2_d},~\eqref{for:opt2}, and ${\mathbf{d}}^{k+1}-{\mathbf{d}}^*\in \range({\mathbf{I}}-{\mathbf{W}})$.
From~\eqref{for:alg2_x}, we have that
\begin{align}\label{for:proximal_ineq}
\langle {\mathbf{x}}^k-{\mathbf{x}}^*, {\mathbf{z}}^k-{\mathbf{x}}^k-{\mathbf{z}}^*+{\mathbf{x}}^*\rangle_{\Lambda^{-1}} \geq 0.
\end{align}
Therefore, we have
\begin{align}
  & \langle {\mathbf{x}}^k-{\mathbf{x}}^*,\nabla s({\mathbf{x}}^k)-\nabla s({\mathbf{x}}^*)\rangle\nonumber \\
\leq& \langle {\mathbf{x}}^k-{\mathbf{x}}^*,{\Lambda^{-1}}({\mathbf{z}}^k-{\mathbf{x}}^k-{\mathbf{z}}^*+{\mathbf{x}}^*)+\nabla s({\mathbf{x}}^k)- \nabla s({\mathbf{x}}^*)\rangle  \nonumber\\
= & \langle {\mathbf{x}}^k-{\mathbf{x}}^*,{\Lambda^{-1}}({\mathbf{z}}^k-{\mathbf{z}}^{k+1})-{\mathbf{d}}^{k+1}+{\mathbf{d}}^*\rangle\nonumber\\
= & \langle {\mathbf{x}}^k-{\mathbf{x}}^*,{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle_{\Lambda^{-1}} - \langle {\mathbf{x}}^k-{\mathbf{x}}^*,{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\rangle\nonumber\\
= & \langle {\mathbf{x}}^k-{\mathbf{x}}^*,{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle_{\Lambda^{-1}} + \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^*,{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\rangle - \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},{\mathbf{d}}^{k+1}-{\mathbf{d}}^k\rangle_{\mathbf{M}}  \nonumber\\
= & \langle {\Lambda^{-1}}({\mathbf{x}}^k-{\mathbf{x}}^*)-{\mathbf{d}}^{k+1}+{\mathbf{d}}^*,{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle - \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},{\mathbf{d}}^{k+1}-{\mathbf{d}}^k\rangle_{\mathbf{M}}  \nonumber\\
= & \langle {\Lambda^{-1}}({\mathbf{z}}^{k+1}-{\mathbf{z}}^*)+\nabla s({\mathbf{x}}^k)-\nabla s({\mathbf{x}}^*),{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle - \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},{\mathbf{d}}^{k+1}-{\mathbf{d}}^k\rangle_{\mathbf{M}}  \nonumber\\
= & \langle {\mathbf{z}}^{k+1}-{\mathbf{z}}^*,{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle_{\Lambda^{-1}} + \langle \nabla s({\mathbf{x}}^k)-\nabla s({\mathbf{x}}^*),{\mathbf{z}}^k-{\mathbf{z}}^{k+1}\rangle\nonumber \\
  & + \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^*,{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\rangle_{\mathbf{M}}  \nonumber.
\end{align}
The inequality and the third equality comes from~\eqref{for:proximal_ineq} and~\eqref{for:main_ineq_1}, respectively. The first and fifth equalities hold because of the update of ${\mathbf{z}}^{k+1}$ in~\eqref{for:alg2_z}. Using $2\langle {\mathbf{a}},{\mathbf{b}}\rangle=\|{\mathbf{a}}+{\mathbf{b}}\|^{2}-\|{\mathbf{a}}\|^{2}-\|{\mathbf{b}}\|^{2}$ and rearranging the previous inequality give us that
\begin{align*}
& 2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle - 2\langle\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*}),{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\rangle \nonumber\\
\leq		&2\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*},{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\rangle_{\Lambda^{-1}}+2\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{*},{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\rangle_{{\mathbf{M}}} \nonumber\\
=		&\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|^{2}_{\Lambda^{-1}}-\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*}\|^{2}_{\Lambda^{-1}}-\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}_{\Lambda^{-1}} \nonumber\\
&  +\|{\mathbf{d}}^{k}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2}-\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2}-\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{{\mathbf{M}}}^{2}.
\end{align*}
Therefore,~\eqref{for:powerIneq} is obtained.
\end{proof}

\subsection{Sublinear convergence of NIDS}
Using Assumption~\ref{lemma:cocoerciveness}, we are able to show in the following lemma that the distance to a fixed point of~\eqref{for:alg2} is decreasing.
\begin{lemma}[A key inequality of descent]\label{lemma:conv}
Let $({\mathbf{d}}^*,{\mathbf{z}}^*)$ be a fixed point of~\eqref{for:alg2} and ${\mathbf{d}}^*\in\range({\mathbf{I}}-{\mathbf{W}})$, then
\begin{align}
\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{\mathbf{M}}^2
\leq		& \|{\mathbf{z}}^{k}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 \label{for:powerIneq2}\\
& -(1-\max_i{\alpha_iL_i\over 2})\left(\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2\right).\nonumber
\end{align}
\end{lemma}
\begin{proof}
Young's inequality and~\eqref{for:cocoer} give us
\begin{align*}
		 & 2\langle\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right),{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\rangle-2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle \nonumber\\
\leq & {1\over 2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}_{\mathbf{L}}+2\|\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\|^{2}_{{\mathbf{L}}^{-1}}-2\|\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\|^{2}_{{\mathbf{L}}^{-1}} \nonumber\\
=    & \frac{1}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}_{\mathbf{L}}.
\end{align*}
Therefore, from~\eqref{for:powerIneq}, we have
\begin{align*}
        & \|{\mathbf{z}}^{k+1}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 \nonumber\\
\leq		& \|{\mathbf{z}}^{k}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}-\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2  +\frac{1}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}_{\mathbf{L}}\nonumber\\
\leq    & \|{\mathbf{z}}^{k}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -(1-\max_i{\alpha_iL_i\over 2})\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}-\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2  \nonumber\\
\leq    & \|{\mathbf{z}}^{k}-{\mathbf{z}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -(1-\max_i{\alpha_iL_i\over 2})\left(\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2\right). \nonumber
\end{align*}
This completes the proof.
\end{proof}

\begin{lemma}[Monotonicity of successive difference]\label{lemma:nonincreasing}
If $\alpha_i< 2/L_i$ for all $i$, the sequence \\ $\left\{\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^k\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\|_{{\mathbf{M}}}^{2}\right\} _{k\geq0}$
is monotonically nonincreasing.
\end{lemma}
\begin{proof}
Similar to the proof for Lemma~\ref{lemma:powerIneq}, we can show that
\begin{align}\label{for:nonincreasing1}
\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}+{\mathbf{x}}^{k}\rangle= &\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\rangle_{{\mathbf{M}}},\\%=\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{{\mathbf{M}}}\\
\label{for:nonincreasing2}
\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}+{\mathbf{x}}^{k-1}\rangle= &\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\rangle_{{\mathbf{M}}},\\
\label{for:nonincreasing3}
\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},{\mathbf{z}}^{k}-{\mathbf{x}}^{k}-{\mathbf{z}}^{k-1}+{\mathbf{x}}^{k-1}\rangle_{\Lambda^{-1}}\geq &0.
\end{align}

Subtracting~\eqref{for:nonincreasing2} from~\eqref{for:nonincreasing1} on both sides, we have
\begin{align}
     & \langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{x}}^{k}-{\mathbf{x}}^{k-1}\rangle\nonumber\\
=    & \left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{{\mathbf{M}}}-\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},{\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\rangle_{{\mathbf{M}}}+\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},2{\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}-{\mathbf{z}}^{k+1}\rangle\nonumber\\
\geq & \left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{{\mathbf{M}}}-{1\over2}\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\|_{\mathbf{M}}^2-{1\over 2}\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\|^2_{{\mathbf{M}}}\nonumber\\
     & +\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},2{\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}-{\mathbf{z}}^{k+1}\rangle\nonumber\\
= & {1\over2}\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\|_{\mathbf{M}}^2-{1\over 2}\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\|^2_{{\mathbf{M}}}+\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},2{\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}-{\mathbf{z}}^{k+1}\rangle,  \label{nonincreasing4}
\end{align}
where the inequality comes from the Cauchy-Schwarz inequality.
Then, the previous inequality, together with~\eqref{for:nonincreasing3} and the Cauchy-Schwarz inequality, gives
\begin{align*}
        & \langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{k-1})\rangle \nonumber\\
\leq	  & \langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},{\Lambda^{-1}}({\mathbf{z}}^{k}-{\mathbf{x}}^{k}-{\mathbf{z}}^{k-1}+{\mathbf{x}}^{k-1})+\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{k-1})\rangle \nonumber\\
=       & \langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},{\Lambda^{-1}}({\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k})-{\mathbf{d}}^{k+1}+{\mathbf{d}}^{k}\rangle
\nonumber\\
\leq    & \langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k}\rangle_{\Lambda^{-1}}-\langle {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k},2{\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}-{\mathbf{z}}^{k+1}\rangle
\nonumber\\
 		    & -{1\over2}\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{{\mathbf{M}}}+{1\over2}\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\|^2_{{\mathbf{M}}} \nonumber\\
=       &  \langle {\Lambda^{-1}}({\mathbf{x}}^{k}-{\mathbf{x}}^{k-1})-{\mathbf{d}}^{k+1}+{\mathbf{d}}^{k},{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k}\rangle
\nonumber\\
 		    & -{1\over2}\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{{\mathbf{M}}}+{1\over2}\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\|^2_{{\mathbf{M}}} \nonumber\\
=       & \langle {\Lambda^{-1}}({\mathbf{z}}^{k+1}-{\mathbf{z}}^{k})+\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{k-1}\right),{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k}\rangle \nonumber\\
        &  -\frac{1}{2}\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\| _{{\mathbf{M}}}^{2}+\frac{1}{2}\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2} \nonumber\\
\leq    & \langle {\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k}\rangle_{\Lambda^{-1}}+\frac{1}{2}\left\| {\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k-1}+{\mathbf{z}}^{k}\right\| ^{2}_{\Lambda^{-1}} \nonumber\\
        &  +\frac{1}{2}\left\| \nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{k-1}\right)\right\|^{2}_{\Lambda} -\frac{1}{2}\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\| _{{\mathbf{M}}}^{2}+\frac{1}{2}\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2} \nonumber\\
=       &  \frac{1}{2}\left\| {\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}\right\|_{\Lambda^{-1}}^{2}-\frac{1}{2}\left\| {\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\right\|^{2}_{\Lambda^{-1}}+\frac{1}{2}\left\| \nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{k-1}\right)\right\|^{2}_{\Lambda} \nonumber\\
        &  -\frac{1}{2}\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\| _{{\mathbf{M}}}^{2}+\frac{1}{2}\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2}.
\end{align*}
The three inequalities hold because of~\eqref{for:nonincreasing3},~\eqref{nonincreasing4}, and the Cauchy-Schwarz inequality, respectively.
The first and third equalities come from~\eqref{for:alg2_z}.
Rearranging the previous inequality, we obtain
\begin{align*}
      & \left\| {\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\right\|^{2}_{\Lambda^{-1}} +\left\| {\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|_{{\mathbf{M}}}^{2} \nonumber\\
\leq	& \left\| {\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}\right\|^{2}_{\Lambda^{-1}}+\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2}+\frac{1}{2}\left\| \nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{k-1}\right)\right\|^{2}_{\Lambda}\\
      & -\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{k-1},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{k-1})\rangle \nonumber\\
\leq  & \left\| {\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}\right\|^{2}_{\Lambda^{-1}}+\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2}+\frac{1}{2}\left\| \nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{k-1}\right)\right\|^{2}_{\Lambda-2{\mathbf{L}}^{-1}}\nonumber\\
\leq  & \left\| {\mathbf{z}}^{k}-{\mathbf{z}}^{k-1}\right\|^{2}_{\Lambda^{-1}}+\left\| {\mathbf{d}}^{k}-{\mathbf{d}}^{k-1}\right\| _{{\mathbf{M}}}^{2}.
\end{align*}
where the second and last inequalities come from~\eqref{for:cocoer} and $\Lambda< 2{\mathbf{L}}^{-1}$, respectively. It completes the proof.
\end{proof}

\begin{theorem}[Sublinear rate]\label{lemma:conv_rate}
If $\alpha_i< 2/L_i$ for all $i$, we have
\begin{align}
\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{{\mathbf{M}}}^{2} \leq &  \frac{\|{\mathbf{z}}^{1}-{\mathbf{z}}^{*}\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{1}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2} }{k(1-\max_i{\alpha_iL_i\over 2})},\\
\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{{\mathbf{M}}}^{2} = & o\left(\frac{1}{k+1}\right).\label{conv:sublinear}
\end{align}
Furthermore, $({\mathbf{d}}^k,{\mathbf{z}}^k)$ converges to a fixed point $(\bar{\mathbf{d}},\bar{\mathbf{z}})$ of iteration~\eqref{for:alg2} and $\bar{\mathbf{d}}\in\range({\mathbf{I}}-{\mathbf{W}})$.
\end{theorem}

\begin{proof}
Lemma~\ref{lemma:nonincreasing} shows that  $ \left\{\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^k\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\|_{{\mathbf{M}}}^{2}\right\} _{k\geq0}$ is monotonically nonincreasing.
Summing up~\eqref{for:powerIneq2} from $1$ to $k$, we have
\begin{align*}
&  \sum_{j=1}^{k}\left(\|{\mathbf{z}}^{j}-{\mathbf{z}}^{j+1}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{j}-{\mathbf{d}}^{j+1}\|_{{\mathbf{M}}}^{2}\right)  \\
\leq &  {1\over (1-\max_{i}\frac{\alpha_{i}L_{i}}{2})}(\|{\mathbf{z}}^{1}-{\mathbf{z}}^{*}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{1}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2}-\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*}\|_{\Lambda^{-1}}^{2}-\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2}).
\end{align*}
Therefore, we have
\begin{align*}
& \|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{{\mathbf{M}}}^{2} \leq   {1\over k}\sum_{j=1}^{k}\left(\|{\mathbf{z}}^{j}-{\mathbf{z}}^{j+1}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{j}-{\mathbf{d}}^{j+1}\|_{{\mathbf{M}}}^{2}\right)  \\
\leq &  {1\over k(1-\max_{i}\frac{\alpha_{i}L_{i}}{2})}(\|{\mathbf{z}}^{1}-{\mathbf{z}}^{*}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{1}-{\mathbf{d}}^{*}\|_{{\mathbf{M}}}^{2}),
\end{align*}
and~\cite[Lemma 1]{Davis2016} gives us~\eqref{conv:sublinear}.

Inequality~\eqref{for:powerIneq2} shows that the sequence $({\mathbf{d}}^k,{\mathbf{z}}^k)$ is bounded, and there exists a convergent subsequence $({\mathbf{d}}^{k_i}, {\mathbf{z}}^{k_i})$ such that $({\mathbf{d}}^{k_i}, {\mathbf{z}}^{k_i})\rightarrow (\bar{\mathbf{d}},\bar{\mathbf{z}})$.
Then~\eqref{conv:sublinear} gives the convergence of $({\mathbf{d}}^{k_i+1}, {\mathbf{z}}^{k_i+1})$. More specifically, $({\mathbf{d}}^{k_i+1}, {\mathbf{z}}^{k_i+1})\rightarrow (\bar{\mathbf{d}},\bar{\mathbf{z}})$.
Therefore $(\bar{\mathbf{d}},\bar{\mathbf{z}})$ is a fixed point of iteration~\eqref{for:alg2}.
In addition, because ${\mathbf{d}}^k\in\range({\mathbf{I}}-{\mathbf{W}})$ for all $k$, we have $\bar{\mathbf{d}}\in\range({\mathbf{I}}-{\mathbf{W}})$.
Finally Lemma~\ref{lemma:conv} implies the convergence of $({\mathbf{d}}^k,{\mathbf{z}}^k)$ to $(\bar{\mathbf{d}},\bar{\mathbf{z}})$.
\end{proof}

\begin{remark}
Recall that
\begin{align*}
{\mathbf{z}}^{k+1}-{\mathbf{z}}^k
= & {\mathbf{x}}^k-\Lambda\nabla s({\mathbf{x}}^k)-\Lambda {\mathbf{d}}^{k+1}-{\mathbf{z}}^k= -\Lambda({\mathbf{d}}^{k+1}+\nabla s({\mathbf{x}}^k)+{\mathbf{q}}^k),
\end{align*}
where ${\mathbf{q}}^k\in\partial r({\mathbf{x}}^k)$. Therefore, $\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\|_{\Lambda^{-1}}^{2}\rightarrow0$ implies the convergence in terms of~\eqref{for:opt1}.

Combining~\eqref{for:alg2_d} and~\eqref{for:alg2_z}, we have
\begin{align*}
{\mathbf{d}}^{k+1} = & {\mathbf{d}}^k + c({\mathbf{I}}-{\mathbf{W}})(2{\mathbf{x}}^{k}-{\mathbf{z}}^{k}-\Lambda\nabla s({\mathbf{x}}^k)-\Lambda {\mathbf{d}}^k)\\
= & {\mathbf{d}}^k + c({\mathbf{I}}-{\mathbf{W}})(2{\mathbf{x}}^{k}-{\mathbf{z}}^{k}+{\mathbf{z}}^{k+1}-{\mathbf{x}}^k+\Lambda{\mathbf{d}}^{k+1}-\Lambda {\mathbf{d}}^k)\\
= & {\mathbf{d}}^k + c({\mathbf{I}}-{\mathbf{W}})({\mathbf{x}}^{k}-{\mathbf{z}}^{k}+{\mathbf{z}}^{k+1})+c({\mathbf{I}}-{\mathbf{W}})\Lambda({\mathbf{d}}^{k+1}-{\mathbf{d}}^k).
\end{align*}
Rearranging it gives
\begin{align*}
\left({\mathbf{I}}-c({\mathbf{I}}-{\mathbf{W}})\Lambda\right)\left({\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right)=c({\mathbf{I}}-{\mathbf{W}})\left({\mathbf{x}}^{k}-{\mathbf{z}}^{k}+{\mathbf{z}}^{k+1}\right).
\end{align*}
Then we have
\begin{align*}
 \|c({\mathbf{I}}-{\mathbf{W}})\left({\mathbf{x}}^{k}-{\mathbf{z}}^{k}+{\mathbf{z}}^{k+1}\right)\|^2
= & \|\left({\mathbf{I}}-c({\mathbf{I}}-{\mathbf{W}})\Lambda\right)\left({\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right)\|^2 \\
= & \|c\left({\mathbf{I}}-{\mathbf{W}}\right){\mathbf{M}}^{1/2}{\mathbf{M}}^{1/2}\left({\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right)\|^2 \\
\leq & \| c({\mathbf{I}}-{\mathbf{W}}){\mathbf{M}}^{1/2}\|^{2} \left\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^{k}\right\|^2_{\mathbf{M}},
\end{align*}
where the second equality comes from ${\mathbf{d}}^{k+1}-{\mathbf{d}}^k\in\range({\mathbf{I}}-{\mathbf{W}})$.
Thus $\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\|_{\Lambda^{-1}}^{2}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^k\|^2_{\mathbf{M}}\rightarrow0$ implies the convergence in terms of~\eqref{for:opt2}.
\end{remark}

\subsection{Linear convergence for special cases}
In this subsection, we provide the linear convergence rate for the case when $r({\mathbf{x}})=0$, i.e., ${\mathbf{z}}^k={\mathbf{x}}^k$ in NIDS.

\begin{theorem}\label{thm:linear_conv}
If $\{s_i(x)\}_{i=1}^n$ are strongly convex with parameters $\{\mu_i\}_{i=1}^n$, then
\begin{equation}\label{for:strong_conv}
\langle {\mathbf{x}}-{\mathbf{y}},\nabla s({\mathbf{x}})-\nabla s({\mathbf{y}})\rangle\geq \left\|{\mathbf{x}}-{\mathbf{y}}\right\|_{{\mathbf{S}}}^{2},
\end{equation}
where ${\mathbf{S}}=\Diag(\mu_1,\cdots,\mu_n)\in\mathbb{R}^{n\times n}$.
Let
\begin{align}\label{def:rho}
\rho =\max\left(1-(2-\max_i(\alpha_iL_i))\min_i(\mu_i\alpha_i),1-{c\over \lambda_{\max}(\Lambda^{-1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger\Lambda^{-1/2})} \right).
\end{align}
Then we have
\begin{equation}\label{for:linear_conv}
\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{{\mathbf{M}}+\Lambda}^2  \leq \rho\left(\|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{{\mathbf{M}}+\Lambda}^2\right).
\end{equation}
\end{theorem}
\begin{proof}
From~\eqref{for:powerIneq}, we have
\begin{align}
        & \|{\mathbf{x}}^{k+1}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 \nonumber\\
\leq		& \|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^2_{\Lambda^{-1}}-\|{\mathbf{d}}^{k}-{\mathbf{d}}^{k+1}\|_{\mathbf{M}}^2  \label{for:linear_1}\\
        & +2\langle\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right),{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\rangle-2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle.\nonumber
\end{align}
For the two inner product terms, we have
\begin{align}
        & 2\langle\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right),{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\rangle-2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle\cr
=       & -\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1} -\Lambda\nabla s\left({\mathbf{x}}^{k}\right)+\Lambda\nabla s\left({\mathbf{x}}^{*}\right)\|^2_{\Lambda^{-1}}+\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^2_{\Lambda^{-1}}\cr
        & +\|\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right)\|^2_{\Lambda}-2\langle {\mathbf{x}}^{k}-{\mathbf{x}}^{*},\nabla s({\mathbf{x}}^{k})-\nabla s({\mathbf{x}}^{*})\rangle\cr
\leq    & -\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|^2_{\Lambda}+\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^2_{\Lambda^{-1}} +\|\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right)\|^2_{\Lambda}\cr
        & -\max_i(\alpha_iL_i)\|\nabla s\left({\mathbf{x}}^{k}\right)-\nabla s\left({\mathbf{x}}^{*}\right)\|^2_{{\mathbf{L}}^{-1}}-(2-\max_i(\alpha_iL_i))\|{\mathbf{x}}^k-{\mathbf{x}}^*\|^2_{{\mathbf{S}}}\cr
\leq    & -\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|^2_{\Lambda}+\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^2_{\Lambda^{-1}} \nonumber\\
        & -(2-\max_i(\alpha_iL_i))\min_i(\mu_i\alpha_i)\|{\mathbf{x}}^k-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}. \label{for:linear_2}
\end{align}
The first inequality comes from ${\mathbf{x}}^{k+1} = {\mathbf{x}}^{k} -\Lambda\nabla s\left({\mathbf{x}}^{k}\right)-{\mathbf{d}}^{k+1}$, $\Lambda\nabla s\left({\mathbf{x}}^{*}\right)+{\mathbf{d}}^*=\mathbf{0}$,~\eqref{for:cocoer} and~\eqref{for:strong_conv}.
Combing~\eqref{for:linear_1} and~\eqref{for:linear_2}, we have
\begin{align*}
          \|{\mathbf{x}}^{k+1}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{\mathbf{M}}^2
\leq		& \|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{\mathbf{M}}^2 -\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|^2_{\Lambda} \\
        & -(2-\max_i(\alpha_iL_i))\min_i(\mu_i\alpha_i)\|{\mathbf{x}}^k-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}.\nonumber
\end{align*}
Therefore,
\begin{align}
 \|{\mathbf{x}}^{k+1}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}+\|{\mathbf{d}}^{k+1}-{\mathbf{d}}^*\|_{{\mathbf{M}}+\Lambda}^2
\leq		& (1-(2-\max_i(\alpha_iL_i))\min_i(\mu_i\alpha_i))\|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|^2_{\Lambda^{-1}}\\
& +{\lambda_{\max} (\Lambda^{-1/2}{\mathbf{M}}\Lambda^{-1/2})\over \lambda_{\max}(\Lambda^{-1/2}{\mathbf{M}}\Lambda^{-1/2})+1}\|{\mathbf{d}}^{k}-{\mathbf{d}}^*\|_{{\mathbf{M}}+\Lambda}^2.  \nonumber
\end{align}
Since ${\lambda_{\max} (\Lambda^{-1/2}{\mathbf{M}}\Lambda^{-1/2})\over \lambda_{\max}(\Lambda^{-1/2}{\mathbf{M}}\Lambda^{-1/2})+1} = 1-{1\over \lambda_{\max} (\Lambda^{-1/2}({\mathbf{M}}+\Lambda)\Lambda^{-1/2})}=1-{c\over \lambda_{\max} (\Lambda^{-1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger\Lambda^{-1/2})}$.
Let $\rho$ defined as~\eqref{def:rho}, then we have~\eqref{for:linear_conv}.
\end{proof}

\begin{remark}\label{remark4}
The condition ${\mathbf{I}}\succ c\Lambda^{1/2}({\mathbf{I}}-{\mathbf{W}})\Lambda^{1/2}$ implies that $c< \lambda_{n-1}(\Lambda^{-1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger\Lambda^{-1/2})$.
When ${\Lambda}=\alpha{\mathbf{I}}$, i.e., the stepsize for all agents are the same, we have
$$\rho =\max\left(1-(2-\alpha\max_iL_i)\alpha\min_i\mu_i,1-{c\alpha\over \lambda_{\max}(({\mathbf{I}}-{\mathbf{W}})^\dagger)} \right).$$
Letting $\alpha={1\over \max_i L_i}$ and $c={1\over \alpha( 1-\lambda_n({\mathbf{W}}))}$, we have $\rho =\max\left(1-{\min_i\mu_i\over \max_iL_i},{\lambda_2({\mathbf{W}})-\lambda_n({\mathbf{W}})\over 1-\lambda_n({\mathbf{W}})} \right)$.

If we let ${\Lambda}={\mathbf{L}}^{-1}$, then we have $\rho =\max\left(1-\min_i{\mu_i\over L_i},1-{\lambda_{n-1} ({\mathbf{L}}^{1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger{\mathbf{L}}^{1/2})\over \lambda_{\max}({\mathbf{L}}^{1/2}({\mathbf{I}}-{\mathbf{W}})^\dagger{\mathbf{L}}^{1/2})}  \right).$
\end{remark}

\begin{remark}
Theorem~\ref{thm:linear_conv} separates the dependence of linear convergence rate on the functions and the network structure. In our current scheme, all the agents perform information exchange and proximal-gradient step once at each iteration. If the proximal-gradient adaptation is expensive, this explicit rate formula can help us to decide whether the so-called multi-step consensus can help reducing the computational time.

For the sake of simplicity, let us assume for this moment that all the agents have the same strong convexity constant $\mu$ and gradient Lipschitz continuity constant $L$. Suppose that the ``$t$-step consensus'' technique is employed, i.e., the mixing matrix ${\mathbf{W}}$ in our algorithm is replaced by ${\mathbf{W}}^t$, where $t$ is a positive integer. Then to reach $\epsilon$-accuracy, the number of iterations needed is
\[O\left(\max\left(\frac{L}{\mu},\frac{1-\lambda_n({\mathbf{W}}^t)}{1-\lambda_2({\mathbf{W}}^t)}\right)\right)\log\frac{1}{\epsilon}.\]
When $L/\mu=1$ and the step sizes are chosen as $\Lambda={\mathbf{L}}^{-1}$, this formula says that we should let $t\rightarrow+\infty$ if the graph is not a complete graph. Such theoretical result is correct in intuition since in this case, the centralized gradient descent only needs one step to reach optimal while the only bottleneck in decentralized optimization is the graph.

Suppose $t_{\max}$ is a reasonable upper bound on $t$, which is set by the system designer. It is difficult to explicitly find an optimal $t$. But with the above analysis as an evidence, we suggest that one choose $t=\min\left([\log_{\lambda_2({\mathbf{W}})}(1-\frac{\mu}{L})],t_{\max}\right)$ if $1-\frac{\mu}{L}>\lambda_2({\mathbf{W}})$; otherwise $t=1$. Here the operation $[\cdot]$ gives the nearest integer.
\end{remark}

\section{Numerical Experiments}\label{sec:num_exp}
In this section, we compare the performance of our proposed NIDS with several state-of-the-art algorithms for decentralized optimization. These methods are
\begin{itemize}
	\item EXTRA/PG-EXTRA~\eqref{pg-extra} for both the smooth and non-smooth cases.
	\item DIGing-ATC~\cite{nedich2016achieving} for the smooth case only. The DIGing-ATC can be expressed as:
	\begin{subequations}
		\begin{align}
		{\mathbf{x}}^{k+1} =& {\mathbf{W}}({\mathbf{x}}^k-\alpha{\mathbf{y}}),\\
		{\mathbf{y}}^{k+1} =& {\mathbf{W}}({\mathbf{y}}^k + \nabla f({\mathbf{x}}^{k+1}) - \nabla f({\mathbf{x}}^k)).
		\end{align}
	\end{subequations}
\end{itemize}
Note there are two rounds of communication in each iteration of DIGing-ATC while there are only one round of communication in EXTRA/PG-EXTRA and NIDS.
For all the experiments, we first compute the exact solution ${\mathbf{x}}^*$ for~\eqref{eq:F} using the centralized (proximal) gradient descent.

The experiments are carried in Matlab R2016b running on a laptop with Intel i7 CPU @ 2.60HZ, RAM 16.0 GB, and Windows 10 operating system.
The source code for reproducing the numerical results is available via~\href{https://github.com/mingyan08/NIDS}{https://github.com/mingyan08/NIDS}.

\subsection{The strongly convex case with $r({\mathbf{x}})=0$}
Consider the decentralized sensing problem that solves for an unknown signal $x \in \mathbb{R}^{p}$.
Each agent $i \in \{1,\cdots,n\}$ takes its own measurement via $y_i={\mathbf{M}}_ix+e_i$, where $y_i \in \mathbb{R}^{m_i}$ is the measurement vector, ${\mathbf{M}}_i \in \mathbb{R}^{m_i \times p} $ is the sensing matrix, and $e_i \in \mathbb{R}^{m_i} $ is the independent and identically distributed noise.
Then we apply the decentralized algorithms to solve
\begin{align*}
\Min_{\mathbf{x}}~s({\mathbf{x}})=\frac{1}{n}\sum_{i=1}^{n}{1\over2}\|{\mathbf{M}}_ix_i-y_i\|^2 \textnormal{ subject to } {\mathbf{W}}{\mathbf{x}}={\mathbf{x}}.
\end{align*}
In order to ensure that each subfunction $s_i(x) = {1\over 2}\|{\mathbf{M}}_ix-y_i\|^2$ is strongly convex, we choose $m_i=60$ and $p=50$ and set the number of nodes $n=40$.
For the first experiment, we chosen ${\mathbf{M}}_i$ such that the Lipshchitz constant of $\nabla s_i$ satisfies $L_i=1$ and the strongly convex constant $\mu_i=0.5$ for all $i$.
From Remark~\ref{remark4}, we would choose $\alpha={1/(\max_i L_i)}=1$ and $c={1/(1-\lambda_n({\mathbf{W}}))}$ for NIDS.
In addition, we choose $c={1/2}$ such that $\widetilde{{\mathbf{W}}}={{\mathbf{I}}+{\mathbf{W}}\over 2}$, which is the same as in EXTRA. Then, the stopping criteria for all decentralized algorithms is $\|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|<10^{-11}$.

The comparison of these four methods (NIDS with $c={1/(1-\lambda_n({\mathbf{W}}))}$, NIDS with $c=1/2$, EXTRA, and DIGing-ATC) is shown in Figure~\ref{fig:compare_c_noR}.
We choose the same step-size $\alpha=1$ for all the four methods. The experiments presented in the left one in Figure~\ref{fig:compare_c_noR}, is conducted under a less connected network comparing with the right one in Figure~\ref{fig:compare_c_noR}. Figure~\ref{fig:compare_c_noR} shows the better performance of both NIDS than that of EXTRA and DIGing-ATC. NIDS with $c={1/(1-\lambda_n({\mathbf{W}}))}$ always takes less than the half number of steps used by EXTRA to converge. Also DIGing-ATC is sensitive to network since it communicates twice per iteration, so that under the better connected network on the right, DIGing-ATC can catch up with the NIDS with $c=1/2$.
\begin{figure}[!ht]
	\begin{center}

		\includegraphics[width=0.4\textwidth]{figs/per14overL_mu0_5_compa3}
		\includegraphics[width=0.4\textwidth]{figs/per18overL_mu0_5_compa3}

	\end{center}
	\caption{\label{fig:compare_c_noR} Under two different network, the plots of the relative error $\frac{\left\| {\mathbf{x}}-{\mathbf{x}}^{*}\right\|}{\left\| {\mathbf{x}}^{*}\right\|}$ with respect to the iteration number. All methods (two NIDS, EXTRA, and DIGing-ATC) use the same step-size $1 /({\max_iL_i)}$. The two NIDS have different $c$ values: $c={1/(\alpha(1-\lambda_n({\mathbf{W}}))}$ and $c={1/( 2\alpha)}$.}
\end{figure}

Remark~\ref{remark4} tells that different nodes can choose different step-sizes based on its own local function $s_i$.
Therefore, in the next experiment, we change two ${\mathbf{M}}_i$ such that they have different $L_i$ and $\mu_i$ from the rest. More specifically, we adjust the two ${\mathbf{M}}_i$ in $s_{i}$, so that $L_i=2$ and $\mu_i=0.4$, while we keep the rest of $s_{i}$ to have $L_i=1$ and $\mu_i=0.2$.
Then we compare the performance of two NIDS (NIDS with step-size $1 / {L_i}$ for each node and NIDS with a constant step-size $1 / {(\max_iL_i)}$ ) with that of EXTRA and DIGing-ATC in Figure~\ref{fig:compare_adpt_noR}. The $c$ values in both NIDS are chosen based on Remark~\ref{remark4}.

\begin{figure}[!ht]
	\begin{center}

		\includegraphics[width=0.5\textwidth]{figs/per16overL_mu0_2_compa3}

	\end{center}
	\caption{\label{fig:compare_adpt_noR} The plot of relative error $\frac{\left\| {\mathbf{x}}-{\mathbf{x}}^{*}\right\|}{\left\| {\mathbf{x}}^{*}\right\|}$. NIDS, EXTRA and DIGing-ATC use the same step-size $1 / {(\max_iL_i)}$. NIDS-adaptive uses the step-size $1 / {L_i}$ for each nodes.}
\end{figure}

With the same step-size $1 / {(\max_iL_i)}$, NIDS , EXTRA and DIGing-ATC have similar performance on this experiment. We found that DIGing-ATC converges more smoothly than EXTRA, but slower than NIDS. The ability of NIDS to choose different step-size over nodes improves the convergence in this experiment, as shown in Figure~\ref{fig:compare_adpt_noR}.

\subsection{The case with nonsmooth function $r({\mathbf{x}})$}
In this subsection, we compare the performance of NIDS with PG-EXTRA~\cite{shi2015proximal} because DIGing can not be applied to this nonsmooth case.
We consider a decentralized compressed sensing problem.
Agaign, each agent $i \in \{1,\cdots,n\}$ takes its own measurement via $y_i={\mathbf{M}}_ix+e_i$, where $y_i \in \mathbb{R}^{m_i}$ is the measurement vector, ${\mathbf{M}}_i \in \mathbb{R}^{m_i \times p} $ is the sensing matrix, and $e_i \in \mathbb{R}^{m_i} $ is the independent and identically distributed noise.
Here, $x$ is a sparse signal.
\begin{align*}
\Min_{\mathbf{x}}~s({\mathbf{x}})+r({\mathbf{x}})=\frac{1}{n}\sum_{i=1}^{n}{1\over2}\|{\mathbf{M}}_ix_i-y_i\|^2+\frac{1}{n}\sum_{i=1}^{n}\lambda_i\|x_i\|_1, \textnormal{ subject to }{\mathbf{W}}{\mathbf{x}}={\mathbf{x}}.
\end{align*}

We normalize the problem to make sure that the Lipschitz constant for each node satisfies $L_i=1$ for each node, we choose $m_i=3$ and $p=200$ and set the number of nodes $n=40$. Considering the size of problem, the stopping criteria is reset to $\|{\mathbf{x}}^{k}-{\mathbf{x}}^*\|<10^{-7}$.

Fix the network (${\mathbf{W}}$), in Figure~\ref{fig:mulStep_R}, NIDS allows larger step-size which leads to faster convergent speed. With step-size $1$, NIDS and PG-EXTRA converge at the same speed, but if we keep increasing the step-size, PG-EXTRA will diverge with step-size $1.4$, but the step-size of NIDS can be increased to $1.9$, which leads to better rate of convergence.

\begin{figure}[!ht]
	\begin{center}

		\includegraphics[width=0.8\textwidth]{figs/per4overL_mu0_1_compa2}

	\end{center}
	\caption{\label{fig:mulStep_R}  The plot of relative error $\frac{\left\| {\mathbf{x}}-{\mathbf{x}}^{*}\right\|}{\left\| {\mathbf{x}}^{*}\right\|}$. Different step-size is considered here.}
\end{figure}

redpajama_set_name: RedPajamaArXiv


text:
Novum Alpha - Daily Analysis 30 October 2020 (8-Minute Read)
Heading into the weekend, markets in the U.S. staged a dramatic turnaround on Thursday, while Asian markets remained cautious.
U.S. stocks bounced back sharply with the S&P 500 (+1.19%), blue-chip Dow Jones Industrial Average (+0.52%) and the tech-heavy Nasdaq Composite (+1.64%) all up on Trump's comments on stimulus.
Asian stocks were mostly down in the morning trading session, as investors continued to weigh concerns over the pandemic's spread in Europe and the U.S.
U.S. 10-year Treasuries yield ticked up to 0.834% from 0.780% (yields typically rise when Treasury prices fall) as investors rotated back into stocks.
The dollar fell slightly on risk taking.
Oil rebounded from a multi-month low with December contracts for WTI Crude Oil (Nymex) (+0.44%) at US$36.33 from US$36.17 on optimism over stimulus and consumption.
Gold was flat, as December contracts for Gold (Comex) (-0.02%) edged down slightly to US$1,867.70 from US$1,868.00 in the previous session, as investors bet on stocks.
Bitcoin (+2.22%) was up alongside other risk assets to settle at US$13,544 from US$13,250 as outflows from exchanges rose with investors taking the opportunity to buy up Bitcoin (outflows typically suggest that investors are looking to shore up Bitcoin stocks in anticipation of price increases).
Central Banks Sell Their Gold
Coronavirus - Same But Different
Bitcoin's Biggest Boost Came from Ethereum's DeFi
It is literally days till elections in the U.S. and the prospect of having a massive stimulus package being passed through both Congress and the White House, are between slim and none.
Yet that hasn't prevented investors from remaining hopeful, as Trump hinted at plans for a large additional fiscal stimulus after the election.
Depending on how the election goes, a lame duck legislature means that the chances of any substantive legislation being passed between now and January is in the realm of fiction.
But investors, inundated by bad news will cling to any sliver of hope and U.S. stocks rose higher as Trump, who is trailing his Democratic rival Biden at the polls, is throwing everything and the kitchen sink at a last-ditch effort to shore up his re-election efforts.
If so, Asian markets were not buying it, with Tokyo's Nikkei 225 (-0.63%), Hong Kong's Hang Seng Index (-0.49%), Seoul's KOSPI (-0.57%) and Sydney's ASX 200 (-0.10%) all down.
1. Central Banks Sell Their Gold
Countries facing fiscal pressures have seen their central banks sell gold to shore up finances
Global central bank demand for gold is expected to increase in 2021 in light of inflation pressures
All that glitters is not gold, at least according to some central banks.
Because for the first time in almost a decade, central banks have become net sellers of bullion.
Taking advantage of record prices for gold, there are some central banks at least, which have used the opportunity to sell.
Net sales totaled 12.1 tons of bullion in the third quarter of 2020, compared with net purchases of 141.9 tons a year earlier, according to a report by the World Gold Council.
Selling was driven largely by Uzbekistan and Turkey, while Russia's central bank posted its first quarterly sale in 13 years.
To be sure, many of the central banks selling gold are in economies which have come under increasing strain in the past few years.
The Turkish economy had been in near freefall even before the effects of the pandemic, which have only made things worse.
And while some central banks have been selling gold, still others have been snapping it up, including the European Central Bank.
In fact, Citigroup last month predicted that central bank demand for bullion would rebound in 2021, after slowing this year from near record purchases in both 2018 and 2019.
However, for countries which are becoming increasingly strained fiscally, gold has been a godsend.
The central banks of Turkey and Uzbekistan sold 22.3 tons and 34.9 tons of gold respectively in the third quarter, with Uzbekistan in particular diversifying its foreign reserves away from gold as the central Asian nation opens up to the world.
But the longer-term macroeconomic outlook for gold continues to be strong.
And while some central banks may be cashing out their gold reserves to cover fiscal deficits, still more are loading up on it on fears of inflation.
Given the prospect of inflation in the coming years, with the U.S. Federal Reserve seeking to allow inflation to shoot past the target 2% until the economy recovers, there is still some merit to holding on to gold as a store of value.
2. Coronavirus - Same But Different
New coronavirus mutation originating from Spain spreading through much of Europe
Anecdotal evidence coupled with colder temperatures has increased spread of the coronavirus mutation, but little is known of its lethality
Hold fast to your face mask.
Just when you thought it was safe to head out again, the coronavirus has other plans in its quest for global domination.
While scientists have long warned that the coronavirus would mutate, regional variations did not give rise to worsening conditions.
That may be set to change however as a coronavirus variant that was first detected in Spanish farm workers, has spread rapidly throughout much of Europe since the summer, and now accounts for the majority of cases in several countries, including over 80% in the United Kingdom.
In a research paper published yesterday, scientists, who termed the coronavirus variant 20A.EU1, have suggested that people returning from holidaying in Spain in the summer, played a key role in transmitting the new variant, as Europe comes to grip with a devastating second wave.
Scientists in Switzerland and Spain are now rushing to examine if 20A.EU1 is more deadly or more virulent than other strains.
And while all viruses develop mutations, as a result of changes in the individual sequences of their genetic code, not all mutations necessarily make the virus more deadly or virulent.
One coronavirus mutation, D614G is believed to make it more infectious, but given how little scientists know about the coronavirus in general, it's still too soon to make a determination on how mutations affect the efficacy of the virus.
Anecdotal evidence, as evidenced by the rapid spread of 20A.EU1 in recent weeks suggests that this strain may be more infectious, but only time will tell if it has become more deadly.
That it's come from Spain will no doubt draw unfortunate comparisons with the Spanish flu.
The other reason for the rapidity of what appears to be a second wave of coronavirus infections may also have to do with the falling temperatures in Europe.
It is known that colder temperatures allow for the coronavirus to live on surfaces for longer periods.
And as lockdowns were eased across much of Europe, holidaymakers coming from the warmer southern parts of the continent, may have potentially hastened the spread of the new coronavirus variant 20A.EU1, then if temperatures had been warmer up north.
With Germany and France instituting fresh lockdowns, it looks like it'll be a long winter both for the European economy and its people.
3. Bitcoin's Biggest Boost Came from Ethereum's DeFi
Popularity of "wrapped" Bitcoin or Bitcoin that has been modified to work on the Ethereum blockchain has fueled demand for Bitcoin
Longer term, Bitcoin's transactions shifting to the Ethereum blockchain may undermine incentives for Bitcoin miners to secure the Bitcoin blockchain
To call Bitcoin and Ethereum competitors is an apples to oranges sort of comparison.
Whereas Bitcoin is considered by many as the equivalent of digital gold, Ether on the other hand is likened to the digital dollar that powers the global supercomputer, the Ethereum blockchain.
Like chalk and cheese, the two cryptocurrency protocols, far from being competitors are actually complementary in their roles.
And nowhere has this been more evident than in the most recent rally of Bitcoin, powered by one of Ethereum's latest innovations, decentralized finance or DeFi.
DeFi allows users to borrow, lend and trade in a variety of digital assets without intermediaries and one of the hottest digital assets on stock has been wBTC, or Bitcoin that has been wrapped for use on the Ethereum blockchain.
Using wBTC, investors are able to loan out Bitcoin on the Ethereum blockchain using such platforms as Compound and posting dollar-based gains in excess of the 90% that Bitcoin itself has posted this year.
To get wBTC, an investor typically deposits Bitcoin with custodian BitGo, keeping them in a central depository that is then used to generate yield on DeFi platforms.
About 0.6% of all minted Bitcoin has been "wrapped" with that number growing steadily.
The result has been that demand for wBTC on DeFi platforms, and the returns generated there, have led to a higher demand for Bitcoin in general, helping to boost Bitcoin's price.
Responding to the demand, Coinbase Pro listed wBTC two weeks ago, making it more accessible to investors.
But what's sauce for the goose could in this case be poison for the gander.
Because Bitcoin miners get paid for securing transactions on the Bitcoin blockchain, if an increasing pool of Bitcoin just sits there, because it gets wrapped, with the bulk of those transactions taking place on the Ethereum blockchain, Bitcoin miners will earn lower fees in the long run, pushing them to consider a switch to supporting the Ethereum blockchain.
And there are other risks as well.
Putting all that Bitcoin in a centralized depository for wrapping makes it a prime target for hackers or nefarious actors acting from within, and regulators are unlikely to take kindly to wrapped cryptocurrency which further obfuscates its source.
For now at least, it appears that what's good for Ethereum is good for Bitcoin as well, and vice versa.
While markets are expected to continue to be volatile, Novum Digital Asset Alpha's quantitative digital asset trading strategy has done consistently well and proved resilient.
Using our proprietary deep learning tools that actively filter out signal noise, our market agnostic approach provides one of the most sensible ways to participate in the nascent digital asset sector.

redpajama_set_name: RedPajamaCommonCrawl


Recruiting Management | NuView Systems, Inc.
Recruiting Management within our HRIS offers advanced tools to assist recruiters and hiring managers with the entire hiring process, from requisitions, sourcing, applicant tracking and management, to interviewing and job offer.
Recruiting transforms applicant resumes sent via email, or submitted via your web site, into applicant data. Applicant records are automatically populated with key fields, including name, addresses, skills and education.
Our HRIS lets you track detailed position and requisition data for all company openings. It supports both job and position control methodologies.
Recruiting will graphically match applicants and positions based on required skills, identifying the best applicants, significantly reducing the time spent in the qualification process.
I would like someone to contact me with more information regarding Recruiting Management. I saw it in the Human Resources Marketplace.


I'm currently away from home, mothering my mother who is vanishing as she stands right before me, unable to understand why I do the things I do only because they must be done to help her, confused at the additional struggles that would make life difficult for anyone, let alone someone who is slowly forgetting everything, including herself.
I talk a lot on this blog about finding joy in the small things, and we still laugh and enjoy a cup of tea and a citrus slice, or the snow on the mountains today, or the elephant seal pup on the beach on Saturday.
But it is not lost on me that this will be my only experience of mothering anyone, when things happen in reverse, and there is no great joy (and even the little joys are disappearing daily), and there is in its place only sadness.
Holding you in my thoughts, and wishing you moments of peace even in the midst of sadness.
Hugs, Mali. I wish you peace during this challenging time.
So sorry for your sadness. The slowly forgetting, the deteriorating health. It is so hard, and getting harder. And then you still have to take care of yourself, too. Sending hugs and virtual cups of tea.
I'm sorry to hear about the slow loss of your mother. Having lost my own mother through a long illness I can imagine some of the things you might be feeling. Wishing you peace love and hope.
Much love and many hugs to you my friend. I'm thinking of you during this time.
I can only imagine how difficult it is for you.
(I know a bit about it - I have been watching for the last two years my DH, taking care of his mother who has Alzheimer).
Sending so many hugs your way.
I can only imagine how sad and difficult this time is for you.
Tears for you Mali. Wow, what a beautiful, sad post. Take care.
Sometimes there are no words. Hugs.
(((HUGS))) Such a poignant post, Mali. I'm so sorry that your mom is slipping away. It is very difficult to be there for someone who's vanishing. I wish you peace as well and comfort for your mom.
This post made me hold my breath, especially the last paragraph. Holding you in my heart as you hold your mother.
My heart is heavy for you. (Hugs) You are a gift to your mother. I am sorry to hear of her declining health.
I just want to say I understand. Can I share something with you? I remember one time when I was walking my mother down a busy street, holding her hand. By sheer coincidence the care staff had dressed her a in orange and white (and I showed up that day in orange and white) and I felt my whole heart almost explode at the thought that there was a time when she held me hand when I was a little girl, protecting me as we walked. If I were to let go, she'd be lost and confused. At the time, I was childless and I had the exact thought in my head. My heart goes out to you. You are a good daughter.
Huge, huge huge hugs to you. I can only imagine how tough it is to see your mom fading. I remember my mom taking care of my grandmother as she got older and more frail. It's such a lovely gift to have that time with her and I'm glad you are finding some joy there.
I am in awe of your ability to find joy in the small things, even during the slow-motion loss you are experiencing. Sending you my love.
Thinking of you and wishing you peace as you walk through this time. I'm sorry you're going through this and glad that you are able to find some moments of joy to treasure.
Wish I had useful words........I am holding you and your mother in my heart.
I always appreciate your perspectives, Mali, this one in particular zings right through my core.
Like many of the others, this took my breath away. May there be moments of peace, knowing that you are giving her the comfort that no other can, even amidst the sadness. Holding you both in my heart.


Food glorious food, there is no getting away from it on a cruise.
While of course cruising is not simply about tthe food, it's no secret that it does play a significant part. Some of the most exquisite dishes are found at sea, and several of the most famous Michelin chefs now call the sea their home.
Although the main dining room is still a key feature on many ships, it is the rise in specialty restaurants that attract us to open our intrigued taste buds that crave new flavours. Showcasing the best in the cuisine of Italy, Brazil, Asia, and France to name a few, a cruise will take you on a culinary journey like never before.
With specialty restaurants requiring an extra cover charge and most needing a reservation, they change the dynamic of cruise ship dining dramatically. Whether you simply want to dine somewhere different every night, or want to visit an exclusive restaurant for a special occasion, its hard to escape from these award-winning restaurants that tempt you with their mouth-watering menus, intimate settings, and excellent value for money.
Read on to discover our top 10 speciality restaurants at sea.
With Italian food being among the most popular regional cuisines across the world, most cruise lines include an Italian Bistro among their dining options. However, from the al fresco style setting to the family style dining, Giovanni's Table wins our vote. Featured on many Royal Caribbean ships, its enticing menu is only a teaser of how the food actually tastes.
With its apparent Mediterranean influence, Giovanni's Table flaunts a true Italian atmosphere and intense aroma that one would expect from a restaurant in the heart of Venice.
Starters are brought out family style, enabling you to share everything on the menu if you wish. As expected there is lots of pasta, although it is more than just 'pasta'. From authentic sauces, fresh seasonings, and unique cheeses, these starters only leave you more intrigued for the main courses.
Enjoy fresh prosciutto ham that has been cut with a traditional meat slicer, world-class steaks, and the freshest local fish. These are just some of the delectable dishes you can expect to indulge on.
The 'Godfather of modern cooking,' Marco Pierre White was eager to get his culinary wonders to the high seas, and was delighted when P&O Cruises gave him the opportunity to do just this. Owner of three Michelin stars, Marco showcases his talents through The Gala Menu, which is on offer on P&O Cruises' black tie nights.
One of the most desired menus at sea, The Gala Menu is available to all guests on P&O's special occasion, formal evenings. It comprises a beautiful, five course meal, boasting some of Marco's favourite and most exquisite dishes. The superb food combined with faultless service will make for a wonderful, unforgettable evening.
Available on all ships, guests can expect such dishes as Peruvian ceviche, traditional Beef Wellington, and Hampshire trout, and for dessert, why not indulge in chocolate mousse cake, or Champagne sorbet? Created with the best and freshest local ingredients, even the most experienced of taste buds will be blown away here.
Where to start with this restaurant? Like nothing else you'll ever experience on land let alone at sea, this unique dining journey starts from the moment you order your meal on an iPad. There can be no preconceptions about Qsine as it is a restaurant of the unexpected.
After you have used the interactive iPads to design your meal, sit back and wait to be tantalised by unexpected twists on familiar favourites. From the revolutionary sushi lollipops, popcorn fish and chips, and lobster escargot, it has an off-beat edge to give you an experience that you can only find on a Celebrity Cruise.
Qsine's décor is fairly simple and boasts a more casual feel. Decked out in orange and yellows, its bright design portrays a happy atmosphere and great for a fun meal time with friends and family.
Every city, shopping mall, and airport has the latest take on an Asian sushi restaurant, and it didn't take long for cruise lines to jump on the bandwagon either. However, Kai Sushi onboard Princess Cruises stood out for us.
From the moment you step inside, you are transported to an Asian paradise. With deep brown décor combined with bamboo accessories, its large open cooking area showcases highly regarded chefs preparing authentic sushi creations and traditional Japanese seafood dishes.
Those who do not have a love for sushi can opt for lobster, octopus, and other seafood dishes which are equally delicious.
When Norwegian Cruise Line introduced Moderno Churrascaria on Norwegian Epic, the positive reviews flew in and everyone was talking about it. Debuting a new dining experience to the cruise industry, this Brazilian Steakhouse was the first dining concept of its kind at sea.
Although the decor is not the most stand-out design, the food more than makes up for it. The extensive salad bar invites you to delve into its freshly prepared selection including tuna, fresh beans, European cured meats, and Artisan cheeses. However, be careful as this is a meal in itself - and you will certainly not want to fill yourself up before the main course.
Calling all carnivores! Be prepared to feast on the largest selection of meats you have ever seen in one restaurant at the same time. From a range of different beef, chicken, pork, sausage, chorizo, and lamb, it's a pure haven for meat-eating foodies.
With all of this delicious meat being sliced before your very eyes, it's a wonder they even thought about dessert, but if you do have room, you are in for a brilliant surprise. The signature dessert of crispy fried Portuguese sweet bread puffs with caramel and vanilla, is the icing on the cake for your Moderno Churrascaria experience.
Remy is way up there on our list of favourite restaurants, and not only at sea. This intimate adult-only eatery is an enchanted retreat that serves the finest French cuisine. Remy manages to transport you to an authentic roof-top restaurant in the centre of Paris.
Soft lighting, gold décor, and timeless art work compliment the immaculately dressed tables. Like the rest of the ship, Disney have sprinkled their magic on this restaurant to ensure everyone has a five-star dining experience.
The French-inspired menu was created by Chef Arnaud Lallement who has worked at numerous Michelin star restaurants, and Chef Scott Hunnell from the award-winning Victoria & Albert's at Walt Disney World Resort.
A complimentary chilled champagne cocktail is prepared at your table before you place your orders from the enticing menu. Some of the tasty dishes you can expect to choose from include Halibut, King Salmon, Kobe Beef, and Niman Ranch Lamb.
One for those who like the finer things in life, 150 Central Park is the premium specialty restaurant onboard Oasis and Allure of the Seas. Created by award-winning Chef Michael Schwartz, he brings his distinct flavours alive in this intimate and charming restaurant.
Located in the centre of the onboard Central Park, its boutique style exterior is set deep within the lush greenery. Once the door has been opened by one of the immaculately dressed hosts, you are guided to a table that looks like it has been prepared for the Queen. The grand domed chairs are an excellent touch.
Featuring two rotating multi-course menus per cruise, each set course is accompanied with the perfect wine to enhance each dish into an explosion of deliciousness. Although each of the courses are fairly small, do not let this deceive, as every course compliments the others, ensuring you are more than satisfied by the end.
A signature Cucumber Martini (only available here) at the beginning is then followed by a selection of breads. The waiter will then explain the salts that are available to have with your bread, a really interesting concept. From here expect to experience a world-class cheese trolley, a 0.65kg dry-aged rib eye steak, and the iconic 150 Central Park Candy Bar.
The restaurant of flavours, Sindhu was created by Michelin star chef Atul Kochhar who has brought his much-loved Indian style to the cruise world. Showcasing his modern Indian cuisine with a British twist, Sindhu sets all the senses alive and gives you the ultimate dining experience.
Kochhar has explored flavours from across the Far East and infuses them in all of the dishes available at East. There are two inspiring menus available onboard that offer his most exotic dishes.
The interior design boasts deep red and gold décor that illuminates a charming atmosphere throughout. It is not only the food that allows you to have a special evening here, but the atmosphere and regular presence of chefs make it a memorable dining experience.
With an extensive menu, it is hard to choose, but rest assured that whatever choice you make you will not be disappointed. From spiced meats, fish dishes, and an array of vegetarian options, it is Indian cuisine as you've never seen it.
A steak house with an Italian bistro is a couple rarely seen together at sea, until the launch of Tuscan Grille. Celebrity Cruises wanted a restaurant that was elegant yet edgy to showcase an array of distinct dishes.
Tuscan Grille has an exciting character that creates an infectious sense of smiles and enjoyment within every visitor. With its casual style, it allows guests to enjoy elegant food in a more contemporary setting.
It's bright lighted entrance entices you to go further as you walk through a small tunnel-like walk way before leading to the bright, open restaurant that boasts floor to ceiling windows overlooking the ocean.
Steak is the highlight at Tuscan Grille. Celebrity's corn-fed USDA dry-aged steaks are bursting with juicy flavour and incredible tenderness. Or, for those who don't enjoy steak, opt for the salmon or seabass which are sent to your table sizzling from the grill. A range of salads and pasta dishes are also popular choices.
Everyone loves a steakhouse, so what sets one above the other? For us, Crown Grill is the ultimate in cruise line steakhouses.
Voted 'Best Cruise Ship Steakhouse' by USA Today, it's no surprise why. With deep brown décor, grand dining tables, and a menu to die for, no other steakhouse will compare. Crown Grill is a large sized restaurant and can accommodate a fair amount of guests - which is great as it appears to be one of the most popular restaurants onboard, with a number of guests going back a second or even third time.
A stand-out feature is the open theatre-style kitchen that displays the chefs cooking up their surprises. The large fire oven oozes tantalising aromas that leave you eager for the waiters to present you with your chosen dishes.
The chefs prepare custom-made dishes including steamed lobster, prime steaks and the classic filet mignon. Other dishes featured on this extensive menu include a white wine muscle pot, Chilean sea bass, and grilled tiger prawns.
Our favourite dish: The 4oz Maine lobster tails, and for dessert definitely the Molten Dutch Chocolate Fudge Obsession!
Are you a self-proclaimed foodie? Why not book onto a Food Heroes cruise, or check out these top Cruises for Foodies.
Farewell Indy - Will Anthem Of The Seas Be Southampton's New Sensation?
Can you do 100 activities onboard Allure of the Seas in one day?