Exact Diffusion for Distributed Optimization and Learning --- Part II: Convergence Analysis

I Introduction and review of Part I[2]

For ease of reference, we provide a brief review of the main construction from Part I . We consider a collection of $N$ networked agents working cooperatively to solve an aggregate optimization problem of the form:

where the $\{q_{k}\}$ are positive weighting scalars, each $J_{k}(w)$ is convex and differentiable, and the aggregate cost ${\mathcal{J}}^{\star}(w)$ is strongly-convex. When $q_{1}\cdots=q_{N}$, problem (1) reduces to

Problems of the type (1)–(2) find applications in a wide range of areas including including wireless sensor networks , distributed adaptation and estimation strategies , distributed statistical learning and clustering .

Various algorithms have been proposed to solve problem (2) such as . These algorithms either employ doubly-stochastic or right-stochastic combination matrices. In Part I, we derived the exact diffusion strategy (3)–(5).

where $\mathds{1}_{N}$ refers to a column vector with all entries equal to one. It is assumed that the network graph is strongly-connected, which translates into a primitive matrix $A$. This implies, in view of the Perron-Frobenius theorem , that there exists a Perron vector $p$ satisfying

Furthermore, it was argued in Eq.(11) of Part I that given $q$ and $A$ (and hence $p$), one can always adjust $\{\mu_{k}\}_{k=1}^{N}$ and find a positive constant $\beta$ such that

Let $P=\mbox{\rm diag}(p)$, the matrix $A$ is said to be balanced if

We showed in Part I that balanced left-stochastic matrices are common in practice and that condition (9) endows $A$ with several useful properties that enabled the derivation of the above exact diffusion strategy, and which will be used again in this work to examine its convergence properties.

The structure of the exact diffusion strategy listed in (3)–(5) is very similar to the standard diffusion implementation , with the only difference being the addition of an extra correction step between the adaptation and combination steps. We can rewrite the recursions (3)–(5) in an aggregate form by resorting to a block vector notation. First, we introduce the eigen-decomposition

Using these variables, and was already explained in Part I, the recursions (3)–(5) can be rewritten in the following equivalent so-called primal-dual form:

For the initialization, we set $y_{-1}=0$ and ${\scriptstyle{\mathcal{W}}}_{-1}$ to be any value, and hence for $i=0$ we have

The following auxiliary lemma, which was established in Part I, is used in the subsequent convergence analysis.

In this article, we will establish the linear convergence of exact diffusion using the primal-dual form (19). This is a challenging task due to the coupled dynamics among the agents. To facilitate the analysis, we first apply a useful coordinate transformation and characterize the error dynamics in this transformed domain. Then, we show analytically that exact diffusion is stable, converges linearly, and has a wider stability range than EXTRA consensus strategy. We also compare the performance of exact diffusion to other existing linearly convergent algorithms besides EXTRA, such as DIGing and Aug-DGM with numerical simulations.

II Convergence of Exact Diffusion

The purpose of the analysis in this section is to establish the exact convergence of $w_{k,i}$ to $w^{\star}$, for all agents in the network, and to show that this convergence attains an exponential rate.

If condition (8) holds and block vectors $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star})$ exist that satisfy:

then it holds that the block entries of ${{\scriptstyle{\mathcal{W}}}}^{\star}$ satisfy:

where $w^{\star}$ is the unique solution to problem (1).

Next we check $w_{k}^{\star}=w^{\star}$. Since ${\mathcal{P}}>0$, condition (23) is equivalent to

where equality (a) holds because ${\mathcal{V}}$ is symmetric and (22). Since $\beta\neq 0$, we conclude that $\sum_{k=1}^{N}q_{k}{\nabla}J_{k}(w^{\star}_{k})=0$, which shows that the entries $\{w_{k}^{\star}\}$, which are identical, must coincide with the minimizer $w^{\star}$ of (1).

Observe that since ${{\mathcal{J}}}^{\star}(w)$ is assumed strongly-convex, then the solution to problem (1), $w^{\star}$, is unique, and hence ${\scriptstyle{\mathcal{W}}}^{\star}$ is also unique. However, since ${\mathcal{V}}$ is rank-deficient, there can be multiple solutions ${{\scriptstyle{\mathcal{Y}}}}^{\star}$ satisfying (25). Using an argument similar to , we can show that among all possible ${{\scriptstyle{\mathcal{Y}}}}^{\star}$, there is a unique solution ${{\scriptstyle{\mathcal{Y}}}}^{\star}_{o}$ lying in the column span of ${{\mathcal{V}}}$.

When condition (8) holds and ${\mathcal{J}}^{o}(w)$ defined by (2) is strongly-convex, there exists a unique pair of variables $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star}_{o})$, in which ${\scriptstyle{\mathcal{Y}}}^{\star}_{o}$ lies in the range space of ${\mathcal{V}}$, that satisfies conditions (23)-(24).

First we prove that there always exist some block vectors $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star})$ satisfying (23)–(24). Indeed, when ${\mathcal{J}}^{o}(w)$ is strongly-convex, the solution to problem (1), $w^{\star}$, exists and is unique. Let ${{\scriptstyle{\mathcal{W}}}}^{\star}=\mathds{1}_{N}\otimes w^{\star}$. We conclude from Lemma 1 that condition (24) holds. Next we check whether there exists some ${\scriptstyle{\mathcal{Y}}}^{\star}$ such that

where the last “$\Leftrightarrow$” holds because ${\mathcal{V}}$ is symmetric.

We now establish the existence of the unique pair $({{\scriptstyle{\mathcal{W}}}}^{\star},{{\scriptstyle{\mathcal{Y}}}}_{o}^{\star})$. Thus, let $({{\scriptstyle{\mathcal{W}}}}^{\star},{{\scriptstyle{\mathcal{Y}}}}^{\star})$ denote an arbitrary solution to (25). Let further ${{\scriptstyle{\mathcal{Y}}}}_{o}^{\star}$ denote the projection of ${{\scriptstyle{\mathcal{Y}}}}^{\star}$ onto the column span of ${{\mathcal{V}}}$. It follows that ${\mathcal{V}}({\scriptstyle{\mathcal{Y}}}^{\star}-{\scriptstyle{\mathcal{Y}}}^{\star}_{o})=0$ and, hence, ${\mathcal{V}}{\scriptstyle{\mathcal{Y}}}^{\star}={\mathcal{V}}{\scriptstyle{\mathcal{Y}}}_{o}^{\star}$. Therefore, the pair $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}_{o}^{\star})$ also satisfies conditions (23)-(24).

Next we verify the uniqueness of ${\scriptstyle{\mathcal{Y}}}_{o}^{\star}$ by contradiction. Suppose there is a different ${\scriptstyle{\mathcal{Y}}}_{1}^{\star}$ lying in ${\mathcal{R}}({\mathcal{V}})$ that also satisfies condition (23). We let ${\scriptstyle{\mathcal{Y}}}^{\star}_{o}={\mathcal{V}}{\scriptstyle{\mathcal{X}}}^{\star}_{o}$ and ${\scriptstyle{\mathcal{Y}}}^{\star}_{1}={\mathcal{V}}{\scriptstyle{\mathcal{X}}}^{\star}_{1}$. Substituting ${\scriptstyle{\mathcal{Y}}}^{\star}_{o}$ and ${\scriptstyle{\mathcal{Y}}}^{\star}_{1}$ into condition (23), we have

Subtracting (42) from (41) and recall ${\mathcal{P}}>0$, we have ${\mathcal{V}}^{2}({\scriptstyle{\mathcal{X}}}_{o}^{\star}-{\scriptstyle{\mathcal{X}}}_{1}^{\star})=0$, which leads to ${\mathcal{V}}({\scriptstyle{\mathcal{X}}}_{o}^{\star}-{\scriptstyle{\mathcal{X}}}_{1}^{\star})=0\Longleftrightarrow{\scriptstyle{\mathcal{Y}}}_{o}^{\star}={\scriptstyle{\mathcal{Y}}}_{1}^{\star}$. This contradicts the assumption that ${\scriptstyle{\mathcal{Y}}}_{o}^{\star}\neq{\scriptstyle{\mathcal{Y}}}_{1}^{\star}$.

Using the above auxiliary results, we will show that $({\scriptstyle{\mathcal{W}}}_{i},{\scriptstyle{\mathcal{Y}}}_{i})$ generated through the exact diffusion (19) will converge exponentially fast to $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star}_{o})$.

II-B Error Recursion

Let ${{\scriptstyle{\mathcal{W}}}}^{\star}=\mathds{1}_{N}\otimes w^{\star}$, which corresponds to a block vector with $w^{\star}$ repeated $N$ times. Introduce further the error vectors

The first step in the convergence analysis is to examine the evolution of these error quantities. Multiplying the second recursion of (19) by ${\mathcal{V}}$ from the left gives:

Substituting (44) into the first recursion of (19), we have

Subtracting optimality conditions (23)–(24) from (45) leads to

Next we examine the difference ${\nabla}{\mathcal{J}}^{o}({\scriptstyle{\mathcal{W}}}_{i-1})-{\nabla}{\mathcal{J}}^{o}({\scriptstyle{\mathcal{W}}}^{\star})$. To begin with, we get from (17) that

When ${\nabla}J_{k}(w)$ is twice-differentiable (see Assumption 1), we can appeal to the mean-value theorem from Lemma D.1 in , which allows us to express each difference in (50) in the following integral form in terms of Hessian matrices for any $k=1,2,\ldots,N$:

Using the relations $\overline{{\mathcal{A}}}^{\mathsf{T}}=\frac{I_{MN}+{\mathcal{A}}^{\mathsf{T}}}{2}$ and ${\mathcal{V}}^{2}=\frac{{\mathcal{P}}-{\mathcal{P}}{\mathcal{A}}^{\mathsf{T}}}{2}$, it is easy to verify that

That is, the error vectors evolve according to:

Relation (81) is the error dynamics for the exact diffusion algorithm. We next examine its convergence properties.

II-C Proof of Convergence

Each $J_{k}(w)$ is twice differentiable, and its Hessian matrix satisfies

Moreover, there exists at least one agent $k_{o}$ such that $J_{k_{o}}(w)$ is $\nu$-strongly convex, i.e.

Note that when $J_{k}(w)$ is twice differentiable, condition (88) is equivalent to requiring each ${\nabla}J_{k}(w)$ to be $\delta$-Lipschitz continuous . In addition, condition (89) ensures the strong convexity of ${\mathcal{J}}^{o}(w)$ and ${{\mathcal{J}}}^{\star}(w)$, and the uniqueness of $w^{o}$ and $w^{\star}$. It follows from (88)–(89) and the definition (51) that

The direct convergence analysis of recursion (81) is challenging. To facilitate the analysis, we identify a convenient change of basis and transform (81) into another equivalent form that is easier to handle. To do that, we first let

It holds that ${\mathcal{B}}=B\otimes I_{M}$. In the following lemma we introduce a decomposition for matrix $B$ that will be fundamental to the subsequent analysis.

The matrix $B$ admits the following eigendecomposition

Remark 1. (Other possible decompositions) The eigendecomposition (94) for $B$ is not unique because we can always scale $X$ and $X^{-1}$ to achieve different decompositions. In this paper, we will study the following family of decompositions:

and $c$ can be set to any nonzero constant value. We will exploit later the choice of $c$ in identifying the stability range for exact diffusion.

For convenience, we introduce the vectors:

where ${\mathcal{D}}_{1}=D_{1}\otimes I_{M}$,

To evaluate the block entries of ${{\mathcal{S}}}_{i-1}$, we partition

Substituting (II-C), (177)–(179) and (185) into (158), we have

As a result, $\widehat{{\scriptstyle{\mathcal{X}}}}_{i}$ will stay at only if the initial value $\widehat{{\scriptstyle{\mathcal{X}}}}_{0}=0$. From the definition of ${\mathcal{L}}_{2}$ in (121) and (169) we have

With (201), recursion (195) is equivalent to

The convergence of the above recursion is stated as follows.

Suppose each cost function $J_{k}(w)$ satisfies Assumption 1, the left-stochastic matrix $A$ satisfies the local balance condition (9), and also condition (8) holds. The exact diffusion recursion (19) converges exponentially fast to $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star}_{o})$ for step-sizes satisfying

where $\lambda=\sqrt{\lambda_{2}(\overline{A})}<1$, $\tau_{k_{o}}=\mu_{k_{o}}/\mu_{\max}$, $p_{\max}=\max_{k}\{p_{k}\}$ and

The convergence rate for the error variables is given by

where $C$ is some constant and $\rho=1-O(\mu_{\max})$, namely,

With similar arguments shown above, we can also establish the convergence property of the exact diffusion algorithm 1’ from Part I . Compared to the above convergence analysis, the error dynamics for algorithm 1’ will now be perturbed by a mismatch term caused by the power iteration. Nevertheless, once the analysis is carried out we arrive at a similar conclusion.

Under the conditions of Theorem 1, there exists a positive constant $\bar{\mu}>0$ such that for step-sizes satisfying $\mu<\bar{\mu}$, the exact diffusion Algorithm 1’ will converge exponentially fast to $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}_{o}^{\star})$.

III Stability Comparison with EXTRA

In the case where the combination matrix $A$ is symmetric and doubly-stochastic, and all agents choose the same step-size $\mu$, the exact diffusion recursion (19) reduces to

where ${\mathcal{P}}=I_{MN}/N$. In comparison, the EXTRA consensus algorithm has the following form for the same ${{\mathcal{P}}}$ (recall though that exact diffusion (19) was derived and is applicable to a larger class of balanced left-stochastic matrices and is not limited to symmetric doubly stochastic matrices; it also allows for heterogeneous step-sizes):

where we are using the notation ${\scriptstyle{\mathcal{W}}}_{i}^{e}$ and ${\scriptstyle{\mathcal{Y}}}_{i}^{e}$ to refer to the primal and dual iterates in the EXTRA implementation. Similar to (20), the initial condition for (218) is

Comparing (217) and (218) we observe one key difference; the diffusion update in (217) involves a traditional gradient descent step in the form of ${{\scriptstyle{\mathcal{W}}}}_{i-1}-\mu\nabla{\cal J}^{o}({{\scriptstyle{\mathcal{W}}}}_{i-1})$. This step starts from ${{\scriptstyle{\mathcal{W}}}}_{i-1}$ and evaluates the graduate vector at the same location. The result is then multiplied by the combination policy $\widetilde{\cal A}$. The same is not true for exact consensus in (218); we observe an asymmetry in its update: the gradient vector is evaluated at ${{\scriptstyle{\mathcal{W}}}}_{i-1}^{e}$ while the starting point is at a different location given by $\widetilde{\cal A}{{\scriptstyle{\mathcal{W}}}}_{i-1}^{e}$. This type of asymmetry was shown in to result in instabilities for the traditional consensus implementation in comparison to the traditional diffusion implementation. It turns out that a similar problem continues to exist for the EXTRA consensus solution (218). In particular, we will show that its stability range is smaller than exact diffusion (i.e., the latter is stable for a larger range of step-sizes, which in turn helps attain faster convergence rates). We will illustrate this behavior in the simulations in some detail. Here, though, we establish these observations analytically. The arguments used to examine the stability range of EXTRA consensus are similar to what we did in Section II for exact diffusion; we shall therefore be brief and highlight only the differences.

As already noted in , the optimality conditions for the EXTRA consensus algorithm require the existence of block vectors $({{\scriptstyle{\mathcal{W}}}}^{\star},{{\scriptstyle{\mathcal{Y}}}}^{\star})$ such that

Moreover, as argued in Lemma 3, there also exists a unique pair of variables $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star}_{o})$, in which ${\scriptstyle{\mathcal{Y}}}^{\star}_{o}$ lies in the range space of ${\mathcal{V}}$, that satisfies (220)–(221). Now we introduce the block error vectors:

and examine the evolution of these error quantities. Using similar arguments in Section II-B, and recalling the facts that $\overline{{\mathcal{A}}}$ is symmetric doubly-stochastic, and ${\mathcal{M}}=\mu I_{MN}$, we arrive at the error recursion for EXTRA consensus (see Appendix D):

It is instructive to compare (232)–(237) with (81)–(87). These recursions capture the error dynamics for the exact consensus and diffusion strategies. Observe that ${\mathcal{B}}^{e}={\mathcal{B}}$ when $\overline{{\mathcal{A}}}$ is symmetric and ${\mathcal{M}}=\mu I_{MN}$. Therefore, ${\mathcal{B}}^{e}$ has the same eigenvalue decomposition as in (II-C)–(143). With similar arguments to (94)–(208), we conclude that the reduced error recur-sion for EXTRA consensus takes the form (see Appendix E):

Following the same proof technique as for Theorem 1, we can now establish the following result concerning stability conditions and convergence rate for EXTRA consensus.

Suppose each cost function $J_{k}(w)$ satisfies Assumption 1, and the combination matrix $A$ is primitive, symmetric and doubly-stochastic. The EXTRA recursion (232) converges exponentially fast to $({\scriptstyle{\mathcal{W}}}^{\star},{\scriptstyle{\mathcal{Y}}}^{\star}_{o})$ for step-sizes $\mu$ satisfying

where $\lambda=\sqrt{\lambda_{2}(\overline{A})}<1$ and

The convergence rate for the error variables is given by

where $C$ is some constant and $\rho=1-O(\mu_{\max})$, namely,

III-B Comparison of Stability Ranges

When $\overline{{\mathcal{A}}}$ is symmetric and ${\mathcal{M}}=\mu I_{MN}$, from Theorem 1 we get the stability range of exact diffusion:

Comparing (253) with (245), we observe that the expressions differ by the terms $\|{\mathcal{T}}_{e}\|$ and $\|{\mathcal{T}}_{d}\|$. We therefore need to compare these two norms.

It is easy to recognize that $\lambda_{\max}(I_{MN}+{\mathcal{V}}^{2})=\lambda_{\max}(I_{N}+V^{2})$. Now, since $A$ is assumed symmetric doubly-stochastic and $P={1\over N}I_{N}$, we have

Moreover, since $A$ is primitive, symmetric and doubly stochastic, we can decompose it as

With this decomposition, expression (259) can be rewritten as

Similarly, $\lambda_{\max}(\overline{{\mathcal{A}}}(I_{MN}+{\mathcal{V}}^{2})\overline{{\mathcal{A}}})=\lambda_{\max}(\overline{A}(I_{N}+V^{2})\overline{A})$. Using $\overline{A}=\frac{I_{N}+A}{2}$, and equations (260) and (262), we have

It is worth noting that the “$=$” sign cannot hold in (a) because

In other words, $\left(\frac{\lambda_{k}(A)+1}{2}\right)^{2}$ and $\frac{2N+1-\lambda_{k}(A)}{2N}$ cannot reach their maximum values at the same $k$. As a result,

This means that the upper bound on $\mu$ in (245) is smaller than the upper bound on $\mu$ in (253).

We can also compare the convergence rates of EXTRA consensus and exact diffusion when both algorithms converge. When $\overline{{\mathcal{A}}}$ is symmetric and ${\mathcal{M}}=\mu I_{MN}$, from Theorem 1 we get the convergence rate of exact diffusion:

It is clear from (III-B) and (3) that EXTRA consensus and exact diffusion have the same convergence rate to first-order in $\mu_{\max}$, namely,

More generally, when higher-order terms in $\mu_{\max}$ cannot be ignored, it holds that $\rho_{d}<\rho_{e}$ because $\alpha_{d}<\alpha_{e}$ (see (269)). In this situation, exact diffusion converges faster than EXTRA.

III-C An Analytical Example

In this subsection we illustrate the stability of exact diffusion by considering the example of mean-square-error (MSE) networks . Suppose $N$ agents are observing streaming data $\{{\boldsymbol{d}}_{k}(i),{\boldsymbol{u}}_{k,i}\}$ that satisfy the regression model

It was shown in Example 6.1 of that the global minimizer of problem (273) coincides with the unknown $w^{o}$ in (272).

When $R_{u,k}$ and $r_{du,k}$ are unknown and only realizations of ${\boldsymbol{u}}_{k,i}$ and ${\boldsymbol{d}}_{k}(i)$ are observed by agent $k$, one can employ the diffusion algorithm with stochastic gradient descent to solve (273). However, when $R_{u,k}$ and $r_{du,k}$ are known in advance, problem (273) reduces to deterministic optimization problem:

We can then employ the exact diffusion or the EXTRA consensus algorithm to solve (274).

To illustrate the stability issue, it is sufficient to consider a network with $2$ agents (see Fig. 1) and with diagonal Hessian matrices, i.e.,

We assume the agents use the combination weights $\{a,1-a\}$ with $a\in(0,1)$, so that

which is symmetric and doubly stochastic. The two agents employ the same step-size $\mu$ (or $\mu^{e}$ in the EXTRA recursion). It is worth noting that the following analysis can be extended to $N$ agents with some more algebra.

To guarantee the convergence of $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}$ and $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}^{e}$, we need to examine the eigenstructure of the $4\times 4$ matrices $Q_{d}$ and $Q_{e}$. The proof of the next lemma is quite similar to Lemma 4; if desired, see Appendix F of the arXiv version.

The matrix $Q_{d}$ admits the following eigendecomposition

Moreover, the matrices $X$ and $X^{-1}$ are given by

It is observed that $Q_{d}$ always has an eigenvalue at $1$, which implies that $Q_{d}$ is not stable no matter what the step-size $\mu$ is. However, this eigenvalue does not influence the convergence of recursions (280). To see that, from Lemma 5 we have

where ${\mathcal{X}}_{R}=X_{R}\otimes I_{M}$, ${\mathcal{X}}_{L}=X_{L}\otimes I_{M}$, ${\mathcal{E}}_{d}=E_{d}\otimes I_{M}$, and

The exact diffusion recursion (280) can be transformed into

which can be further divided into two separate recursions:

As a result, we only need to focus on the other recursion:

If we select the step-size $\mu$ such that all eigenvalues of $E_{d}$ stay inside the unit-circle, then we guarantee the convergence of $\check{{\scriptstyle{\mathcal{Z}}}_{i}}$ and, hence, $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}$.

all eigenvalues of $E_{d}$ will lie inside the unit-circle, which implies that $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}$ in (280) converges to , i.e., $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}\to 0$.

Next we turn to the EXTRA error recursion (281).

it holds that $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}^{e}$ generated through EXTRA (281) will diverge.

Comparing the statements of Lemmas 6 and 7, and since $1+a<2$, exact diffusion has a larger range of stability than EXTRA (i.e., exact diffusion is stable for a wider range of step-size values). In particular, if agents place small weights on their own data, i.e., when $a\approx 0$, the stability range for exact diffusion will be almost twice as large as that of EXTRA.

IV Numerical Experiments

In this experiment, we focus on the least-squares problem:

The simulation setting is the same as Sec. VI.A of Part I.

In the simulation we compare exact diffusion with EXTRA, DIGing, and Aug-DGM. These algorithms work with symmetric doubly-stochastic or right-stochastic matrices $A$. Therefore, we now employ doubly-stochastic matrices for a proper comparison. Moreover, there are two information combinations per iteration in DIGing and Aug-DGM algorithms, and each information combination corresponds to one round of communication. In comparison, there is only one information combination (or round of communication) in EXTRA and exact diffusion. For fairness we will compare the algorithms based on the amount of communications, rather than the iterations. In the figures, we use one unit amount of communication to represent $2ME$ communicated variables, where $M$ is the dimension of the variable while $E$ is the number of edges in the network. The problem setting is the same as in the simulations in Part I, except that $A$ is generated through the Metropolis rule . In the top plot in Fig. 2, all algorithms are carefully adjusted to reach their fastest convergence. It is observed that exact diffusion is slightly better than EXTRA, and both of them are more communication efficient than DIGing and Aug-DGM. When a larger step-size $\mu=0.02$ is chosen for all algorithms, it is observed that EXTRA and DIGing diverge while exact diffusion and Aug-DGM converge, and exact diffusion is much faster than Aug-DGM algorithm.

We also compare exact diffusion with Push-EXTRA and Push-DIGing for non-symmetric combination policies. We consider the unbalanced network topology shown in Fig. 6 in Part I . The combination matrix is generated through the averaging rule. Note that the Perron eigenvector $p$ is known beforehand for such combination matrix $A$, and we can therefore substitute $p$ directly into the recursions of Push-EXTRA and Push-DIGing. In the simulation, all algorithms are adjusted to reach their fastest convergence. In Fig. 3, it is observed that exact diffusion is the most communication efficient among all three algorithms. This figure illustrates that exact diffusion has superior performance for locally-balanced combination policies.

IV-B Distributed Logistic Regression

The simulation setting is the same as Sec. VI.B of Part I.

In this simulation, we also compare exact diffusion with EXTRA, DIGing, and Aug-DGM. A symmetric doubly-stochastic $A$ is generated through the Metropolis rule. In the top plot in Fig. 4, all algorithms are carefully adjusted to reach their fastest convergence. It is observed that exact diffusion is the most communication efficient among all algorithms. When a larger step-size $\mu=0.04$ is chosen for all algorithms in the bottom plot in Fig. 4, it is observed that both exact diffusion and Aug-DGM are still able to converge linearly to $w^{o}$, while EXTRA and DIGing fail to do so. Moreover, exact diffusion is observed much more communication efficient than Aug-DGM.

Appendix A Proof of Lemma 4

With $V^{\prime}=V+\mathds{1}_{N}$ and the fact $V\mathds{1}_{N}=0$ (see Lemma 1), we also have

With relations (340) and (341), we can verify that

where in (a) we used $V^{2}=(P-PA)/2$ and $\overline{A}^{\mathsf{T}}=(I_{N}+A^{\mathsf{T}})/2$. Using $A=Y\Lambda Y^{-1}$ from Lemma 3 of Part I, we have

and $\lambda_{1}(\overline{A})=1$. Moreover, we can also verify that

where $\overline{\Lambda}_{1}={\rm diag}\{0,\lambda_{2}(\overline{A}),\cdots,\lambda_{N}(\overline{A})\}.$ This is because the vectors $\mathds{1}_{N}^{\mathsf{T}}$ and $p$ are the left- and right-eigenvectors of $\overline{A}$. Combining relations (357) and (358), we have

With permutation operations, it holds that

Now we seek the eigenvalues of $E_{k}$. Let $d$ denote an eigenvalue of $E_{k}$. The characteristic polynomial of $E_{k}$ is

Since $\lambda_{k}(\overline{A})\in(0,1)$ when $k=2,3,\cdots,N$, it holds that $4\lambda_{k}^{2}(\overline{A})<4\lambda_{k}(\overline{A})$. Therefore, $d$ is a complex number, and its magnitude is $\sqrt{\lambda_{k}(\overline{A})}$. Therefore, $E_{k}$ can be diagonalized as

where $d_{k,1}$ and $d_{k,2}$ are complex numbers and

Since each factor in $\overline{X}$ is invertible, $\overline{X}^{\hskip 0.56905pt-1}$ must exist. Combining (348) and (361)–(386), we finally arrive at

and $D_{1}$ has the structure claimed in (4).

Therefore, we have established so far the form of the eigenvalue decomposition of $B$. In this decomposition, each $k$-th column of $\overline{X}$ is a right-eigenvector associated with the eigenvalue $D(k,k)$, and each $k$-th row of $\overline{X}^{-1}$ is the left-eigenvector associated with $D(k,k)$. Recall, however, that eigenvectors are not unique. We now verify that we can find eigenvector matrices $\overline{X}$ and $\overline{X}^{-1}$ that have the structure shown in (102) and (107). To do so, it is sufficient to examine whether the two columns of $R$ are independent right-eigenvectors associated with eigenvalue $1$, and the two rows of $L$ are independent left-eigenvectors associated with $1$. Let

Obviously, $r_{1}$ and $r_{2}$ are independent. Since

we know $r_{1}$ and $r_{2}$ are right-eigenvectors associated with eigenvalue $1$. As a result, an eigenvector matrix $X$ can be chosen in the form X=\left[\begin{array}[]{ccc}R&\vline&X_{R}\\ \end{array}\right], where each $k$-th column of $X_{R}$ corresponds to the right-eigenvector associated with eigenvalue $D_{1}(k,k)$. Similarly, we let

where each $k$-th row of $X_{L}$ corresponds to a left-eigenvector associated with eigenvalue $D_{1}(k,k)$.

Appendix B Proof of Theorem 1

From the first line of recursion (208), we have

Squaring both sides and using Jensen’s inequality gives

for any $t\in(0,1)$. Using $\tau_{k}=\mu_{k}/\mu_{\max}$, we obtain

where $\sigma_{11}=p_{k_{o}}\tau_{k_{o}}\nu$. Similarly, we can also obtain

where inequality $(a)$ holds because $\tau_{k}<1$ and $\sum_{k=1}^{N}p_{k}=1$. It is obvious that $\delta>\sigma_{11}$. As a result, we have

which implies that when the step-size satisfy

Recall (176) and by introducing E=\left[\begin{array}[]{cc}I_{MN}&0_{MN}\\ \end{array}\right], we have ${\mathcal{X}}_{R,u}=E{\mathcal{X}}_{R}$. Therefore, it holds that

where $\sigma_{12}\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\sqrt{p_{\max}}\delta\|{\mathcal{X}}_{R}\|/c$. Notice that $\sigma_{12}$ is independent of $\mu_{\max}$. Substituting (419) and (B) into (B), we get

where we are selecting $t=\sigma_{11}\mu_{\max}$.

Next we check the second line of recursion (208):

Squaring both sides and using Jensen’s inequality again,

where $t\in(0,1)$. From Lemma 4 we have that $\lambda\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|D_{1}\|=\sqrt{\lambda_{2}(\overline{A})}<1$. By setting $t=\lambda$, we reach

We introduce the matrix $\Gamma={\rm diag}\{\tau_{1}I_{M},\cdots,\tau_{N}I_{M}\}$, and note that we can write ${\mathcal{M}}=\mu_{\max}\Gamma$. Substituting it into (87),

We also emphasize that $\|{\mathcal{T}}_{d}\|^{2}$ is independent of $\mu_{\max}$. With inequality (436), we further have

since $\|{\mathcal{R}}_{1}\|=1$, and where $\sigma_{21}$ and $\sigma_{22}$ are defined as

With (437) and (438), inequality (B) becomes

Combining (B) and (440), we arrive at the inequality recursion

Now we check the spectral radius of the matrix $G$. Recall the fact that the spectral radius of a matrix is upper bounded by any of its norms. Therefore,

where we already know that $\lambda<1$. To guarantee $\rho(G)<1$, it is enough to select the step-size parameter small enough to satisfy

To get a simpler upper bound, we transform (450) such that

If, in addition, we let (451) be less than $1$, which is equivalent to selecting

then we guarantee equality (450). Combing (449), (452) and (453), we have

will guarantee $\|G\|_{1}$ to be less than $1$. In fact, the upper bound in (454) can be further simplified. From the definitions of $\sigma_{11}$, $\sigma_{12}$, $\sigma_{21}$ and $\sigma_{22}$, we have

because $p_{k_{o}}<p_{\max}$, $\tau_{k_{o}}<1$ and $\nu<\delta$. Therefore, the inequality in (454) is equivalent to

It is observed that the constant value $c$ affects the upper bound in (460). If $c$ is sufficiently large, then the first term in (460) dominates and $\mu_{\max}$ has a narrow feasible set. On the other hand, if $c$ is sufficiently small, then the second term dominates and $\mu_{\max}$ will also have a narrow feasible set. To make the feasible set of $\mu_{\max}$ as large as possible, we should optimize $c$ to maximize

Notice that the first term $1/(\|{\mathcal{X}}_{L}\|^{2}\|{\mathcal{T}}_{d}\|^{2}c^{2})$ is monotone decreasing with $c^{2}$, while the second term $c^{2}/\|{\mathcal{X}}_{R}\|^{2}$ is monotone increasing with $c^{2}$. Therefore, when

we get the maximum upper bound for $\mu_{\max}$, i.e.

Next we compare the above upper bound with $1/\delta$. Recall that for any matrix $A$, its spectral radius is smaller than its $2-$induced norm so that

Moreover, recall from Lemma 4 that $X_{L}X_{R}=I_{2(N-1)}$, so that ${\mathcal{X}}_{L}{\mathcal{X}}_{R}=X_{L}X_{R}\otimes I_{M}=I_{2M(N-1)}$, which implies that

Using relations (464) and (465), and recalling that $p_{k_{o}}\leq p_{\max}<\sqrt{p_{\max}}$, $\tau_{k_{o}}<1$, $1-\lambda<1$ and $\nu<\delta$, we have

Therefore, the upper bounds in (454), (455) are determined by

In other words, when $\mu_{\max}$ satisfies (467), $\|G\|_{1}$ will be guaranteed to be less than $1$, i.e.,

where $\alpha_{d}\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|{\mathcal{X}}_{L}\|\|{\mathcal{T}}_{d}\|\|{\mathcal{X}}_{R}\|$. Let

Computing the $1$-norm of both sides gives

where we define $\rho\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|G\|_{1}$. Inequality (473) is equivalent to

By re-incorporating $\widehat{{\scriptstyle{\mathcal{X}}}}_{i}=0$, relation (478) also implies that

where the constant $C=\|{\mathcal{X}}\|^{2}C_{0}$.

Appendix C Proof of Theorem 2

Substituting recursions (98) and (99) from Part I into expre-ssion (100) we obtain (compare with (93) from Part I ):

which can be rewritten into a primal-dual form (compare with (89) from Part I ):

For the initialization, we set $y_{-1}=0$ and ${\scriptstyle{\mathcal{W}}}_{-1}$ to be any value, and hence for $i=0$ we have

Recursions (494) and (495) are very close to the standard exact diffusion recursions (19) and (20), except that the step-size matrix ${\mathcal{M}}_{i}^{\prime}$ is now changing with iteration $i$. Following the arguments (43) – (45), we have

Subtracting optimality conditions (23)–(24) from (496) leads to

Comparing recursions (497) and (46), it is observed that recursion (497) has an extra “mismatch” term, $\overline{{\mathcal{A}}}^{\mathsf{T}}({\mathcal{M}}_{i}^{\prime}-{\mathcal{M}}){\nabla}{\mathcal{J}}^{o}({\scriptstyle{\mathcal{W}}}_{i-1}).$ This mismatch arises because we do not know the perron vector $p$ in advance. We need to run the power iteration (see recursion (97) from Part I) to learn it. Intuitively, since ${\mathcal{M}}_{i}^{\prime}\rightarrow{\mathcal{M}}$ as $i\to\infty$, we can expect the mismatch term to vanish gradually. Let

By following arguments (50)–(59), recursion (497) is equivalent to

By following (69)–(87), recursion (503) can be rewritten as

where ${\mathcal{B}}$ and ${\mathcal{T}}_{i}$ are defined in (87), and

Relation (515) is the error dynamics for the exact diffusion algorithm $1^{\prime}$. Comparing (515) with (81), we find that algorithm $1^{\prime}$ is essentially the standard exact diffusion with error perturbation. Using Lemma (4) and by following arguments from (121) to (208), we can transform the error dynamics (515) into

Next we analyze the convergence of the above recursion. From the first line we have

where the last inequality follows the arguments in (413)–(B). From the second line of recursion (525), we have

Next let us bound the mismatch term $\|e_{i}\|^{2}$. From (498) we have

where $g\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|{\mathcal{J}}^{o}({\scriptstyle{\mathcal{W}}}^{\star})\|^{2}$ is a constant independent of iteration. Recall that ${\mathcal{M}}=M\otimes I_{M}$ and ${\mathcal{M}}^{\prime}_{i}=M^{\prime}_{i}\otimes I_{M}$ where

Using the relation $\mu_{k}=q_{k}\mu_{o}/p_{k}$ (see equation (13) from Part I), we have

where $\tau_{k}=\mu_{k}/\mu_{\max}\leq 1$.

Now we examine the convergence of $1-p_{k}/z_{k,i}(k)$. From the discussion in Policy 5 form Part I, it is known that ${\scriptstyle{\mathcal{Z}}}_{i}$ generated from the power iteration (see equation (37) from Part I) will converge to $[(\mathds{1}_{N}\otimes I_{N})(p^{\mathsf{T}}\otimes I_{N})]{\scriptstyle{\mathcal{Z}}}_{-1}$. Therefore,

Recall from the discussion in Policy 5 from Part I that

where $h\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|{\scriptstyle{\mathcal{Z}}}_{-1}\|^{2}$ is a constant, and $\rho_{A}$ is the second largest eigenvalue magnitude of matrix $A$, i.e., $\rho_{A}=\max\{|\lambda_{2}(A)|,|\lambda_{N}(A)|\}$. Since $A$ is locally balanced, we know $A$ is diagonalizable with real eigenvalue in $(-1,1]$, and it has a single eigenvalue at $1$ (see Table I from Part I ), we conclude that $\rho_{A}<1$. Also, recall from the discussion at the end of Policy 5 in Part I that $z_{k,i}(k)>0$ is guaranteed when $\bar{a}_{kk}>0$. Let

Combining (C) and (549), it holds that for $k=1,\cdots,N$,

where we define $h_{k}\;\stackrel{{\scriptstyle\Delta}}{{=}}\;h/\alpha_{k}$. Substituting (550) into (C), it holds that

where $h^{\prime}\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\max_{k}\{\tau^{2}_{k}h_{k}\}$ is a constant independent of iterations. Substituting (551) into (543), we have

where the last equality holds because $\widehat{{\scriptstyle{\mathcal{X}}}}_{i}=0$ for $i=0,1,\cdots$ (see (201)). Substituting (C) into (C), we have

where $b^{\prime},c^{\prime},d^{\prime},e^{\prime}$ are constants defined as

These constants are independent of iterations. It can be verified that when iteration $i$ is large enough such that

where we can prove $\rho\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|G^{\prime}\|_{1}=1-O(\mu_{\max})<1$ by following arguments (B). Inequality (580) further implies that

where $f^{\prime}\;\stackrel{{\scriptstyle\Delta}}{{=}}\;d^{\prime}\mu_{\max}+e^{\prime}\mu_{\max}^{2}>0$. Let $\beta=\max\{\rho,\rho_{A}\}<1$. Inequality (584) becomes

By adding $\gamma f^{\prime}\beta^{2i+4}$, where $\gamma$ can be any positive constant to be chosen, to both sides of the above inequality, we get

As a result, the quantity $\left(\|\bar{{\scriptstyle{\mathcal{X}}}}_{i}\|^{2}+\|\check{{\scriptstyle{\mathcal{X}}}}_{i}\|^{2}\right)+\gamma f^{\prime}\beta^{2(i+2)}$ converges to linearly. Since $f^{\prime}>0,\gamma>0$ and $\beta>0$, we can conclude that $\|\bar{{\scriptstyle{\mathcal{X}}}}_{i}\|^{2}+\|\check{{\scriptstyle{\mathcal{X}}}}_{i}\|^{2}$, and hence $\|\widetilde{\scriptstyle{\mathcal{W}}}_{i}\|^{2}+\|\widetilde{\scriptstyle{\mathcal{Y}}}_{i}\|^{2}$, converges to linearly.

Appendix D Error Recursion for EXTRA Consensus

Multiplying the second recursion of (218) by ${\mathcal{V}}$ gives:

Substituting into the first recursion of (218) gives

From (591) and the second recursion in (218) we conclude that

Subtracting the optimality condition (220)–(221) from (592) leads to

Using relations $\overline{{\mathcal{A}}}=\frac{I_{MN}+{\mathcal{A}}}{2}$ and ${\mathcal{V}}^{2}=\frac{{\mathcal{P}}-{\mathcal{P}}{\mathcal{A}}}{2}$, it is easy to verify that

Substituting (607) into (602) gives (232)–(237).

Appendix E Error Recursion in Transformed Domain

Multiplying both sides of (232) by $({\mathcal{X}}^{\prime})^{-1}$:

To compute each entry of ${\mathcal{S}}^{e}_{i-1}$, we let

we find for the second line of ${{\mathcal{S}}}_{i-1}^{e}$ that

Substituting (E), (641) and (649) into (622), we rewrite (622) as

As a result, $\widehat{{\scriptstyle{\mathcal{X}}}}^{e}_{i}$ will converge to only if the initial value $\widehat{{\scriptstyle{\mathcal{X}}}}^{e}_{0}=0$. To verify that, from the definition of ${\mathcal{L}}_{2}$ in (121) and (633) we have

Recall that ${\scriptstyle{\mathcal{Y}}}_{o}^{\star}$ lies in the ${\mathcal{R}}({\mathcal{V}})$, so that ${\scriptstyle{\mathcal{Y}}}^{\star}_{o}-{\mathcal{V}}{\scriptstyle{\mathcal{W}}}_{0}$ also lies in ${\mathcal{R}}({\mathcal{V}})$. Recall further from Lemma 1 that ${\mathcal{I}}^{\mathsf{T}}{\mathcal{V}}=0$, and conclude that $\widehat{{\scriptstyle{\mathcal{X}}}}^{e}_{0}=0$. Therefore, from (660) we have

With (665), recursion (659) is equivalent to (244).

Appendix F Proof of Theorem 3

From the first line of recursion (244), we have

Squaring both sides and using Jensen’s inequality gives

for any $t\in(0,1)$. For the term ${\mu\overline{{\mathcal{P}}}^{\mathsf{T}}{\mathcal{H}}_{i-1}{\mathcal{I}}}$, we have

where $\sigma_{11}=\nu/N$. Similarly, we can obtain the upper bound

where equality $(a)$ holds because $\sum_{k=1}^{N}p_{k}=1$. It is obvious that $\delta>\sigma^{e}_{11}$. As a result, we have

which implies that when the step-size is sufficiently small to satisfy

where $\sigma^{e}_{12}=\delta\|{\mathcal{X}}_{R}\|/(c\sqrt{N})$ and the “$=$” sign in the third line holds because $p_{k}=1/N$. Notice that $\sigma^{e}_{12}$ is independent of $\mu$. Substituting (672) and (F) into (F), we get

where we are selecting $t=\sigma^{e}_{11}\mu$.

Next we check the second line of recursion (244), which amounts to

Squaring both sides of (675), and using Jensen’s inequality again,

where $t\in(0,1)$. From Lemma 4 we have that $\lambda\;\stackrel{{\scriptstyle\Delta}}{{=}}\;\|D_{1}\|=\sqrt{\lambda_{2}(\widetilde{A})}<1$. By setting $t=\lambda$, we reach

From the definition of ${\mathcal{T}}^{e}_{i-1}$ in (237), we have

We also emphasize that $\|{\mathcal{T}}_{e}\|^{2}$ is independent of $\mu$. With inequality (685), we further have

notice that $\|{\mathcal{R}}_{1}\|=1$, $\sigma^{e}_{21}$ and $\sigma^{e}_{22}$ are defined as

With (686) and (687), inequality (F) becomes

Combining (F) and (689), we arrive at the inequality recursion:

From this point onwards, we follow exactly the same argument as in (449)–(491) to arrive at the conclusion in Theorem 3.

Appendix G Proof of Lemma 6

It is observed from expression (295) for $E_{d}$ that one of the eigenvalues is $1-\mu\sigma^{2}$. It is easy to verify that when $\mu$ satisfies (334), it holds that $-1<1-\mu\sigma^{2}<1.$ Next, we check the other two eigenvalues. Let $\theta$ denote a generic eigenvalue of $E_{d}$. From the right-bottom $2\times 2$ block of $E_{d}$ in (295), we know that $\theta$ will satisfy the following characteristic polynomial

where $a\in(0,1)$ is a combination weight (see the expression for $A$ in (278)). Solving (697), the two roots are

Based on the value of $\mu\sigma^{2}$ and $a$, $\Delta$ can be negative, zero, or positive. Recall from (334) that $0<\mu\sigma^{2}<2$. In that case, over the smaller interval $1\leq\mu\sigma^{2}<2$, it holds that $(1-\mu\sigma^{2})\geq 0$ and, from (699), $\Delta>0$. For this reason, as indicated in cases 1 and 2 below, the scenarios corresponding to $\Delta<0$ or $\Delta=0$ can only occur over $0<\mu\sigma^{2}<1$:

Case 1: $\Delta<0$. It can be verified that when

it holds that $\Delta<0$. In this situation, both $\theta_{1}$ and $\theta_{2}$ are imaginary numbers with magnitude

where the last inequality holds because $0<\mu\sigma^{2}<1$ (see (334) and (700)) and $a\in(0,1)$.

Case 2: $\Delta=0$. It can be verified that when

it holds that $\Delta=0$. In this situation, from (698) we have

where the last inequality holds because $0<\mu\sigma^{2}<1$ (see (334) and (700)) and $a\in(0,1)$. Observe further that the upper bound on $a$ in (700) is positive and smaller than one when $0<\mu\sigma^{2}<1$.

Case 3: $\Delta>0$. It can be verified that when

or when $1\leq\mu\sigma^{2}<2$, it holds that $\Delta>0$. In this situation, $\theta$ is real and

Moreover, since $(2-\mu\sigma^{2})a>0$, we have

We regard $\theta_{1}$ as a function of $a$, i.e., $\theta_{1}=f(a)$. It holds that $f(a)$ is monotone increasing with $a$. To prove it, note that

we conclude that $f^{\prime}(a)>0$. Since $a<1$, it follows that

In summary, when $\mu$ satisfies (334), for any $a\in(0,1)$ it holds that all three eigenvalues of $E_{d}$ stay within the unit-circle, which implies that $\rho(E_{d})<1$, and also $\rho({\mathcal{E}}_{d})<1$. As a result, $\check{{\scriptstyle{\mathcal{Z}}}}_{i}$ in (333) will converge to . Since $\widehat{{\scriptstyle{\mathcal{Z}}}}_{i}=0$ for any $i$, we conclude that $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}$ converges to .

Appendix H Proof of Lemma 7

Similar to the arguments used to establish Lemma 5 and (310)–(333), the EXTRA error recursion (281) can also be divided into two separate recursions

where ${\mathcal{E}}_{e}=E_{e}\otimes I_{M}$, and

Now we suppose $\mu^{e}\sigma^{2}\geq a+1$ as noted in (335), it then follows that

and hence both $\theta_{1}^{e}$ and $\theta_{2}^{e}$ are real numbers with

Moreover, with $\mu^{e}\sigma^{2}\geq a+1$ we further have

where the last inequality holds because of (718) and (721). Therefore, when $\mu^{e}$ is chosen such that $\mu^{e}\sigma^{2}\geq 1+a$, there always exists one eigenvalue $\theta^{e}$ such that $|\theta^{e}|>1$ which implies that $\check{{\scriptstyle{\mathcal{Z}}}}_{i}^{e}$ diverges, and so does $\widetilde{\scriptstyle{\mathcal{Z}}}_{i}^{e}$.

References