Multi-Agent Distributed Optimization via Inexact Consensus ADMM

I Introduction

We consider a network with multiple agents, for example a sensor network, a data cloud network or a communication network. The agents seek to collaborate to accomplish certain task. For example, distributed database servers may cooperate for data mining or for parameter learning in order to fully exploit the data collected from individual servers . Another example arises from large-scale machine learning applications , where a computation task may be executed by collaborative microprocessors with individual memories and storage spaces . Distributed optimization becomes favorable as it is not always efficient to pool all the local information for centralized computation, due to large size of problem dimension, a large amount of local data, energy constraints and/or privacy issues . Many of the distributed optimization tasks, such as those described above, can be cast as an optimization problem of the following form

In the setting of distributed optimization, it is commonly assumed that each agent $i$ only has knowledge about the local information $f_{i}$, $g_{i}$ and ${\bm{A}}_{i}$. The challenge is to obtain, for each agent in the system, the optimal ${\bm{x}}$ of (P1) using only local information and messages exchanged with neighbors .

In addition to (P1), another common problem formulation has the following form

Problem (7) thus has the same form as (P1). Given the optimal ${\bm{\nu}}$ of (7) and assuming that (P2) has a zero duality gap , each agent $i$ can obtain the associated optimal variable ${\bm{x}}_{i}$ by solving (8). Therefore, a distributed optimization method that can solve (P1) may also be used for (P2) through solving (7).

There is an extensive literature on distributed consensus optimization methods, such as the consensus subgradient methods; see and the recent developments in . The consensus subgradient methods are appealing owing to their simplicity and the ability to handle a wide range of problems. However, the convergence of the consensus subgradient methods are usually slow.

Recently, the alternating direction method of multipliers (ADMM) has become popular for solving problems with forms of (P1) and (P2) in a distributed fashion. In , distributed transmission designs for multi-cellular wireless communications were developed based on ADMM. In , several ADMM based distributed optimization algorithms were developed for solving the sparse LASSO problem . In , using a different consensus formulation from and assuming the availability of a certain coloring scheme for the graph, ADMM is applied to solving the BP problem for both row partitioned and column partitioned data models . In , the methodologies proposed in are extended to handling a more general class of problems with forms of (P1) and (P2). In , a distributed ADMM with a sequential update rule is proposed; while in , the method is extended and can be implemented asynchronously. The fast practical performance of ADMM is corroborated by its nice theoretical property. In particular, ADMM was found to converge linearly for a large class of problems , meaning a certain optimality measure can decrease by a constant fraction in each iteration of the algorithm. In , such fast convergence rate has also been built for distributed optimization.

It is important to note that existing ADMM based algorithms can be readily used to solve problems (P1) and (P2). For example, by applying the consensus formulation proposed in and ADMM to (P1), a fully parallelized distributed optimization algorithm can be obtained (where the agents update their variables in a fully parallel manner), which we refer to as the consensus ADMM (C-ADMM). To solve (P2), the same consensus formulation and ADMM can be used on its Lagrange dual problem in (7), referred to as the dual consensus ADMM (DC-ADMM). The main drawback of these algorithms lies in the fact that each agent needs to repeatedly solve certain subproblems to global optimality. This can be computationally demanding, especially when the cost functions $f_{i}$’s have complicated structures or when the problem size is large . If a low-accuracy suboptimal solution is used for these subproblems instead, the convergence is no longer guaranteed.

The main objective of this paper is to study algorithms that can significantly reduce the computational burden for the agents. In particular, we propose two algorithms, named the inexact consensus ADMM (IC-ADMM) and the inexact dual consensus ADMM (IDC-ADMM’), both of which allow the agents to perform a single proximal gradient (PG) step at each iteration. The benefit of the proposed approach lies in the fact that the PG step is usually simple, especially when $g_{i}$’s are structured functions . Notably, the cheap iterations of the proposed algorithms is made possible by inexactly solving the subproblems arising in C-ADMM and DC-ADMM, in a way that is not known in the ADMM or consensus literature. For example, the proposed IC-ADMM approximates the smooth functions $f_{i}$’s in C-ADMM, which is very different from the known inexact ADMM methods , where only the quadratic penalty is approximated (thus does not always result in cheap PG steps). We summarize our main contributions below.

For (P1), we propose an IC-ADMM method for reducing the computational complexity of C-ADMM. Conditions for global convergence of IC-ADMM are analyzed. Moreover, we show that IC-ADMM converges linearly, under similar conditions as in .

For (P2), we first propose a DC-ADMM method which can globally solve (P2) for any connected graph and convex $\phi_{i}$’s. We further propose an IDC-ADMM method for reducing the computational burden of DC-ADMM. Conditions for global (linear) convergence are presented.

Numerical examples for solving distributed sparse logistic regression problems will show that the proposed IC-ADMM and IDC-ADMM methods converge much faster than the consensus subgradient method . Further, compared with the original C-ADMM and DC-ADMM, the proposed method can reduce the overall computational cost by an order of magnitude.

The paper is organized as follows. Section II presents the applications and assumptions. The C-ADMM and IC-ADMM are presented in Section III; while DC-ADMM and IDC-ADMM are presented in Section IV. Numerical results are given in Section V and conclusions are drawn in Section VI.

Notations: ${\bm{A}}\succeq{\bm{0}}$ ($\succ{\bm{0}}$) means that matrix ${\bm{A}}$ is positive semidefinite (positive definite). ${\bm{I}}_{K}$ is the $K\times K$ identity matrix; ${\bf 1}_{K}$ is the $K$-dimensional all-one vector. $\|{\bm{a}}\|_{2}$ denotes the Euclidean norm of vector ${\bm{a}}$, and $\|{\bm{z}}\|^{2}_{\bm{A}}\triangleq{\bm{z}}^{T}{\bm{A}}{\bm{z}}$ for some ${\bm{A}}\succeq{\bm{0}}$. Notation $\otimes$ denotes the Kronecker product. ${\rm diag}\{a_{1},\ldots,a_{N}\}$ is a diagonal matrix with the $i$th diagonal element being $a_{i}$; while ${\rm blkdiag}\{{\bm{A}}_{1},\ldots,{\bm{A}}_{N}\}$ is a block diagonal matrix with the $i$th diagonal block matrix being ${\bm{A}}_{i}$. $\lambda_{\max}({\bm{A}})$ and $\lambda_{\min}({\bm{A}})$ denote the maximum and minimum eigenvalues of matrix ${\bm{A}}$, respectively.

II Applications and Network Model

where ${\bm{A}}_{i}=[{\bm{a}}_{i1},\ldots,{\bm{a}}_{iM}]^{T}$ contains $M$ training data vectors and $b_{im}\in\{\pm 1\}$ are binary labels for the training data. It is clear that (9) has the same form as (P1). Here, the non-smooth function $g_{i}$ can be 1-norm for sparse regression, as well as mixture with an indicator functions specifying that ${\bm{y}}$ is confined in certain constraint set.

By introducing a slack variable ${\bm{z}}=[z_{1},\ldots,z_{M}]^{T}\triangleq\sum_{i=1}^{N}{\bf E}_{i}{\bm{x}}_{i}$, the CPD LR problem can be reformulated as

which is an instance of (P2). In Section V, we will primarily test our algorithms on the RPD and CPD regression problems.

II-B Network Model and Assumptions

Let an undirected graph $\mathcal{G}$ denote a multi-agent network, which contains a node set $V=\{1,\ldots,N\}$ and an edge set $\mathcal{E}$. An edge $(i,j)\in\mathcal{E}$ if and only if agent $i$ and agent $j$ can communicate with each other (i.e., neighbors). The edge set $\mathcal{E}$ defines an adjacency matrix ${\bm{W}}\in\{0,1\}^{N\times N}$, where $[{\bm{W}}]_{i,j}=1$ if $(i,j)\in\mathcal{E}$ and $[{\bm{W}}]_{i,j}=0$ otherwise. In addition, one can define an index subset $\mathcal{N}_{i}=\{j\in V\mid(i,j)\in\mathcal{E}\}$ for the neighbors of each agent $i$, and a degree matrix ${\bm{D}}={\rm diag}\{|{\mathcal{N}}_{1}|,\ldots,|{\mathcal{N}}_{N}|\}$ (a diagonal matrix). With ${\bm{W}}$ and ${\bm{D}}$, the Laplacian matrix of $\mathcal{G}$ is given by ${\bm{L}}={\bm{D}}-{\bm{W}}$ which is a positive semidefinite matrix (i.e., ${\bm{L}}\succeq{\bm{0}}$) and satisfies ${\bm{L}}{\bf 1}_{N}={\bm{0}}$ .

We make the following assumptions on $\mathcal{G}$ and problems (P1) and (P2).

The undirected graph $\mathcal{G}$ is connected.

Assumption 1 implies that any two agents in the network can always influence each other in the long run. We also have the following assumptions on problems (P1) and (P2).

For all $i\in V$, the smooth function $f_{i}$ in (2) is strongly convex, i.e., there exists some $\sigma_{f,i}^{2}>0$ such that

Moreover, $f_{i}$ has Lipschitz continuous gradients, i.e., there exists some $L_{f,i}>0$ such that

Note that, even under Assumption 3, $\phi_{i}({\bm{x}})=f_{i}({\bm{A}}_{i}{\bm{x}})+g_{i}({\bm{x}})$ is not necessarily strongly convex in ${\bm{x}}$ since the matrix ${\bm{A}}_{i}$ can be fat and rank deficient. Both the LASSO problem and the LR function in (10) satisfy Assumption 3 The logistic regression function $\log(1+\exp(-x)$ is strongly convex given that $x$ lies in a compact set..

III Distributed Consensus ADMM

In Section III-A, we briefly review the original C-ADMM for solving (P1). In Section III-B, we propose a computationally efficient inexact C-ADMM method.

Under Assumption 1, (P1) can be equivalently written as

where $\{{\bm{t}}_{ij}\}$ are slack variables. According to (15), each agent $i$ can optimize its local function $f_{i}({\bm{A}}_{i}{\bm{y}}_{i})+g_{i}({\bm{y}}_{i})$ with respect to a local copy of ${\bm{y}}$, i.e, ${\bm{y}}_{i}$, under the consensus constraints in (15b) and (15c). In , ADMM is employed to solve (15) in a distributed manner. Let $\{{\bm{u}}_{ij}\}$ and $\{{\bm{v}}_{ij}\}$ denote the Lagrange dual variables associated with constraints (15b) and (15c), respectively. According to , ADMM leads to the following iterative updates at each iteration $k$:

where $c>0$ is a penalty parameter and ${\bm{u}}_{ij}^{(0)}+{\bm{v}}_{ij}^{(0)}={\bm{0}}~{}\forall i,j$. Note that variables $\{{\bm{t}}_{ij}^{(k)}\}$ are not shown in (16) as they can be expressed by variables $\{{\bm{y}}_{i}^{(k-1)}\}$; see for the details.

The updates in (16) are useful for convergence analysis. For practical implementation, we define ${\bm{p}}_{i}^{(k)}\triangleq\sum_{j\in{\mathcal{N}}_{i}}({\bm{u}}_{ij}^{(k)}+{\bm{v}}_{ji}^{(k)}),$ $i\in V$. Then, (16) boils down to Algorithm 1.

It is important to note from Step 4 and Step 5 of Algorithm 1 that, except for the parameter $c$ which has to be universally known, each agent $i$ updates the variables $({\bm{y}}_{i}^{(k)},{\bm{p}}_{i}^{(k)})$ in a fully parallel manner, by only using the local function $\phi_{i}$ and messages $\{{\bm{y}}_{j}^{(k-1)}\}_{j\in{\mathcal{N}}_{i}}$, which come from its direct neighbors. It has been shown in that, under Assumptions 1 and 2, C-ADMM is guaranteed to converge for any $c>0$In general, the parameter $c$ is chosen empirically. Only for some special instance, optimal $c$ may be analytically found; e.g., see . :

where ${\bm{y}}^{\star}\triangleq{\bm{y}}_{1}^{\star}=\cdots={\bm{y}}_{N}^{\star}$ and $\{{\bm{u}}_{ij}^{\star},{\bm{v}}_{ij}^{\star}\}$ denote a pair of optimal primal and dual solutions to problem (15), and ${\bm{y}}^{\star}$ is optimal to (P1). It is also shown that C-ADMM can converge linearly when $\phi_{i}$’s are purely smooth (i.e., $g_{i}({\bm{y}}_{i})=0~{}\forall i$) and strongly convex with respect to ${\bm{y}}_{i}$ .

One key issue about C-ADMM is that the subproblem in (17) is not always easy to solve. For instance, for the LR function in (10), the associated subproblem (17) is given by

As seen, due to the complicated LR cost, problem (III-A) cannot yield simple solutions, and a numerical solver has to be employed. Clearly, obtaining a high-accuracy solution of (III-A) can be computationally expensive, especially when the problem dimension or the number of training data is large. While a low-accuracy solution to (III-A) can be adopted for complexity reduction, it may destroy the convergence behavior of C-ADMM, as will be shown in Section V.

III-B Proposed Inexact C-ADMM

To reduce the complexity of C-ADMM, instead of solving subproblem (17) directly, we consider the following update:

In (III-B) we have replaced the smooth cost function $f_{i}({\bm{A}}_{i}{\bm{y}}_{i})$ in (17) with a proximal first-order approximation around ${\bm{y}}_{i}^{(k-1)}$:

where $\gamma_{i}=\beta_{i}+2c|{\mathcal{N}}_{i}|$. Clearly, using this definition, (III-B) can be expressed more compactly as

which is a proximal gradient (PG) update.

where $(x)^{+}\triangleq\max\{x,0\}$. The IC-ADMM is presented in Algorithm 2.

Although the idea of “inexact ADMM” is not new, our approach is significantly different from the existing methods , where the inexact update is obtained by approximating the quadratic penalization term only. It can be seen that problem (III-A) is still difficult to solve even the inexact update in is applied. Two notable exceptions are the algorithms proposed in and where the cost function is also linearized. However, an additional back substitution step and two extragradient steps are required in and , respectively, which is not suited for distributed optimization.

The convergence properties of IC-ADMM is characterized by the following theorem.

Suppose that Assumptions 1, 2(a) and 3 hold. Let

and let ${\bm{y}}^{\star}\triangleq{\bm{y}}_{1}^{\star}=\cdots={\bm{y}}_{N}^{\star}$ and $\{{\bm{u}}_{ij}^{\star},{\bm{v}}_{ij}^{\star}\}$ denote a pair of optimal primal and dual solutions to problem (15) (i.e., (P1)).

For Algorithm 2, ${\bm{y}}_{1}^{(k)},\ldots,{\bm{y}}_{N}^{(k)}$ converge to a common point ${\bm{y}}^{\star}$.

If $\phi_{i}({\bm{y}})=f_{i}({\bm{A}}_{i}{\bm{y}})$, where ${\bm{A}}_{i}$ has full column rank, for all $i\in V$, then we have

The proof is presented in Appendix A. Theorem 1 implies that, given sufficiently large $\beta_{i}$’s, IC-ADMM not only achieves consensus and optimality, but also converges linearly provided that $\phi_{i}$ is purely smooth and strongly convex. Note that, to ensure (25), the global knowledge of $\lambda_{\min}({\bm{D}}+{\bm{W}})$ is required by all agents. As a parallel work, we should mention that a concurrent result similar as Theorem 1(b) is presented in .

IV Distributed Dual Consensus ADMM

In this section, we turn the focus to (P2). In Section IV-A, we present a DC-ADMM method for solving (P2). In Section IV-B, an inexact DC-ADMM method is proposed.

The DC-ADMM is obtained by applying the C-ADMM (Algorithm 1) to problem (7) which is equivalent to the Lagrange dual of (P2). Firstly, similar to (15), we write problem (7) as

in which $\{{\bm{u}}_{ij}\}$ and $\{{\bm{v}}_{ij}\}$ are dual variables associated with the two constraints in (28b) and are updated in a similar fashion as in (16a) and (16b), i.e.,

In general, subproblem (29b) is not easy to handle because $\varphi_{i}$ is implicit and (29b) is in fact a min-max optimization problem given by

Fortunately, since the objective function in (IV-A) is convex in ${\bm{\nu}}_{i}$ for any ${\bm{x}}_{i}$ and is concave in ${\bm{x}}_{i}$ for any ${\bm{\nu}}_{i}$, the minimax theorem [38, Proposition 2.6.2] can be applied so that the min-max problem (IV-A) can be equivalently solved by considering its max-min counterpart and saddle point exists. Specifically, the max-min counterpart of (IV-A) is given by

where the equality is obtained by completing the quadratic term of ${\bm{\nu}}_{i}$. Let ${\bm{x}}_{i}^{(k)}$ be an inner maximizer of (IV-A) so that $({\bm{\nu}}_{i}^{(k)},{\bm{x}}_{i}^{(k)})$ is a saddle point of (IV-A). Then, $({\bm{x}}_{i}^{(k)},{\bm{\nu}}_{i}^{(k)})$ is a pair of outer-inner solution to (IV-A) and (34) [38, Proposition 2.6.1]. From (34), the inner minimizer ${\bm{\nu}}_{i}^{(k)}$ can be uniquely determined by

As a result, the min-max subproblem (29b) can actually be obtained by first solving the subproblem (IV-A) with respect to the primal variable ${\bm{x}}_{i}$ followed by evaluating ${\bm{\nu}}_{i}^{(k)}$ using the close-form in (IV-A). The proposed DC-ADMM is summarized in Algorithm 3.

Interestingly, while DC-ADMM handles the equivalent dual problem in (7), it directly yields primal optimal solution of (P2), as we state in the following theorem.

Suppose that Assumptions 1 and 2(b) hold. Then $({\bm{\nu}}_{1}^{(k)},\ldots,{\bm{\nu}}_{N}^{(k)})$ converges to a common point ${\bm{\nu}}^{\star}$, which is optimal to the dual problem (7). Moreover, any limit point of $({\bm{x}}_{1}^{(k)},\ldots,{\bm{x}}_{N}^{(k)})$ is primal optimal to (P2).

Proof: Since DC-ADMM is a direct application of C-ADMM to the dual problem (7), it follows from that as $k\rightarrow\infty$,

What remains is to show that any limit point of $({\bm{x}}_{1}^{(k)},\ldots,{\bm{x}}_{N}^{(k)})$ is asymptotically optimal to (P2), i.e., as $k\to\infty$,

To show (40), consider the optimality condition of (IV-A), i.e.,

where the second equality is obtained by (IV-A). Since (IV-A) holds for all $k$ and ${\bm{\nu}}_{i}^{(k)}\rightarrow{\bm{\nu}}^{\star}$ by (39), (40) is true when $k\to\infty$.

where the last equality is obtained by (30) and (31). Upon summing (IV-A) for $i=1,\ldots,N$, and by the fact that

(by applying (A.13) and (A) in Appendix A), we can obtain

Note that ${\bm{\nu}}_{i}^{(k)}-{\bm{\nu}}_{i}^{(k-1)}\to{\bm{0}}~{}\forall i\in V$ as inferred from ${\bm{\nu}}_{i}^{(k)}\to{\bm{\nu}}^{\star}~{}\forall i\in V$ in (39). By applying this fact to (44), we obtain that (41) is true as $k\to\infty$. $\blacksquare$

Interestingly, from (44), one observes that the primal feasibility of $({\bm{x}}_{1}^{(k)},\ldots,{\bm{x}}_{N}^{(k)})$ to (P2) depends on the agents’ consensus on the dual variable ${\bm{\nu}}$.

We remark that Algorithm 3 is different from the D-ADMM algorithm in [12, Algorithm 3]. Firstly, Algorithm 3 can be implemented in a fully parallel manner; secondly, Algorithm 3 does not involve solving a min-max subproblem at each iteration; thirdly, convergence of Algorithm 3 can be achieved without the assumption that the graph $\mathcal{G}$ is bipartite.

IV-B Proposed Inexact DC-ADMM

where, with a slight abuse of notation, $\beta_{i}>0$ is a penalty parameter. By (21), equation (IV-B) can be further written as the following PG update

We summarize the proposed IDC-ADMM in Algorithm 4.

The convergence property of IDC-ADMM is stated below.

Suppose that Assumptions 1, 2(b) and 3 hold and

Let ${\bm{x}}^{\star}=[({\bm{x}}_{1}^{\star})^{T},\ldots,({\bm{x}}_{N}^{\star})^{T}]^{T}$ denote an optimal solution to (P2), and let ${\bm{\nu}}^{\star}\triangleq{\bm{\nu}}_{1}^{\star}=\cdots={\bm{\nu}}_{N}^{\star}$ and $\{{\bm{u}}_{ij}^{\star},{\bm{v}}_{ij}^{\star}\}$ denote a pair of optimal primal and dual solutions to problem (28) (i.e., (7)).

The sequence ${\bm{x}}^{(k)}=[({\bm{x}}_{1}^{(k)})^{T},\ldots,({\bm{x}}_{N}^{(k)})^{T}]^{T}$ generated from Algorithm 4 converges to ${\bm{x}}^{\star}$ of (P2) while ${\bm{\nu}}_{1}^{(k)},\ldots,{\bm{\nu}}_{N}^{(k)}$ converge to a common point ${\bm{\nu}}^{\star}$ of problem (7).

If $\phi_{i}({\bm{x}})=f_{i}({\bm{A}}_{i}{\bm{x}})$, where ${\bm{A}}_{i}$ has full column rank, and ${\bf E}_{i}$ has full row rank, for all $i\in V$, then for some $0<\alpha<1$ and $\rho>0$, we have

where ${\bm{u}}^{(k)}$ and ${\bm{u}}^{\star}$ are defined similarly as in Theorem 1, ${\bf M}$ is defined in (27), and ${\bm{P}}\triangleq{\bm{D}}_{\beta}-\frac{1}{2c}{\rm blkdiag}\{\frac{1}{|{\mathcal{N}}_{1}|}{\bf E}_{1}^{T}{\bf E}_{1},\ldots,\frac{1}{|{\mathcal{N}}_{N}|}{\bf E}_{N}^{T}{\bf E}_{N}\}\succ{\bm{0}}$.

The proof is presented in Appendix B. Note that, in addition to the smooth and strongly convex objective function, IDC-ADMM also requires matrices ${\bf E}_{i}$’s to have full row rank in order to have a linear convergence rate.

V Numerical Results

In this section, we examine the numerical performance of Algorithm 1 to 4 presented so far.

To implement C-ADMM (Algorithm 1), we employed the fast iterative shrinkage thresholding algorithm (FISTA) to solve subproblem (17) for each agent $i$. For (17), the associated FISTA steps can be shown as

For IC-ADMM (Algorithm 2), the corresponding step in (III-B) is given by

The stopping criterion of Algorithms 1 and 2 was based on measuring the solution accuracy ${\sf acc}=({{\sf obj}(\hat{}{\bm{y}}^{(k)})-{\sf obj}^{\star}})/{{\sf obj}^{\star}}$ and variable consensus error ${\sf cserr}={\sum_{i=1}^{N}\|\hat{}{\bm{y}}^{(k)}-{\bm{y}}^{(k)}_{i}\|^{2}_{2}}/{N}$, where $\hat{}{\bm{y}}^{(k)}=({\sum_{i=1}^{N}{\bm{y}}^{(k)}_{i}})/{N}$, ${\sf obj}(\hat{}{\bm{y}}^{(k)})$ denotes the objective value of (9) given ${\bm{y}}=\hat{}{\bm{y}}^{(k)}$, and ${\sf obj}^{\star}$ is the optimal value of (9) which was obtained by FISTA with a high solution accuracy of ${\sf{\sf pgr}}<10^{-6}$. The two algorithms were set to stop whenever acc and cserr are both smaller than preset target values.

V-B Performance of DC-ADMM and IDC-ADMM

In Table II(b), we considered another example with $K$ increased to $800$. We set $c=0.05$ for DC-ADMM, and set $c=0.08$ and $\beta=5$ for IDC-ADMM. From Table II(b) and Figs. 3(b) and 3(c), one can observe similar results.

VI Conclusions

In this paper, we have presented ADMM based distributed optimization methods for solving problems (P1) and (P2) in multi-agent networks. In particular, aiming at reducing the computational complexity of C-ADMM for solving large-scale instances of (P1) with complicated objective functions, we have proposed the IC-ADMM method (Algorithm 2) where agents perform one PG update only at each iteration. For (P2), we have proposed the DC-ADMM method (Algorithm 3) and its complexity reduced counterpart IDC-ADMM (Algorithm 4). Preliminary numerical results based on the distributed LR problems (9) and (II-A) have shown that the proposed methods converge faster than the consensus subgradient method. Moreover, both IC-ADMM and IDC-ADMM require more ADMM iterations than C-ADMM and DC-ADMM, but the traded computational complexity reduction is significant.

Appendix A Proof of Theorem 1

By recalling that ${\bm{p}}_{i}^{(k)}=\sum_{j\in{\mathcal{N}}_{i}}({\bm{u}}_{ij}^{(k)}+{\bm{v}}_{ji}^{(k)})$ $\forall i\in V$, and by the optimality condition of (III-B) , we have that

By combining (A.4) with (A.1), one obtains

Adding and subtracting ${\bm{A}}_{i}^{T}\nabla f_{i}({\bm{A}}_{i}{\bm{y}}_{i}^{(k)})$ in the left hand side (LHS) of (A.5) followed by multiplying $({\bm{y}}_{i}^{(k)}-{\bm{y}}^{\star})$ on both sides yields

Note that the first term on the LHS of (A) can be lower bounded as

for any $\rho_{i}>0$, where the second inequality is due to (14) in Assumption 3. By the strong convexity of $f_{i}$ and convexity of $g_{i}$, the third and fourth terms of (A) can respectively be lower bounded as

Moreover, it follows from (16a) and (16b) that the fifth term of (A) can be expressed as

By substituting (A) to (A) into (A) and summing over $i=1,\ldots,N$, we obtain

It can be observed from (A.3) and also (16a) and (16b) that

given the initial ${\bm{u}}_{ij}^{(0)}+{\bm{v}}_{ij}^{(0)}={\bm{0}}~{}\forall j,i,k$ which is equivalent to setting ${\bm{p}}_{i}^{(k)}={\bm{0}}~{}\forall i\in V$ (See Step 1 of Algorithm 2). Besides, due to the symmetric property of ${\bm{W}}$, for any $\{\alpha_{ij}\}$, we have

By the above two properties, the fourth and fifth terms in the LHS of (A) can be written as

where the first equality is owing to (A), the second equality is by (A.12) and (A.13), and the third equality is due to (16a). In (A), ${\bm{u}}^{(k)}$ (${\bm{u}}^{\star}$) is a vector that stacks ${\bm{u}}_{ij}^{(k)}$ (${\bm{u}}_{ij}^{\star}$) for all $j\in\mathcal{N}_{i}$, $i=1,\ldots,N$. The sixth term in the LHS of (A) can be rearranged as follows

Note that, by the graph theory , the normalized Laplacian matrix, i.e., ${\bm{D}}^{-\frac{1}{2}}{\bm{L}}{\bm{D}}^{-\frac{1}{2}}$, have $\lambda_{\max}({\bm{D}}^{-\frac{1}{2}}{\bm{L}}{\bm{D}}^{-\frac{1}{2}})\leq 2$. Thus, in (A),

By substituting (A) and (A) into (A), we obtain

for any sequence ${\bm{a}}^{(k)}$ and matrix ${\bm{Q}}\succeq{\bm{0}}$. By applying (A) to each of the terms in (A), one obtains that

Now, consider the condition on $\beta_{i}$ in (25). It can be easily checked that (25) implies that

for some $\sigma_{f,i}^{2}\leq\rho_{i}<2\sigma_{f,i}^{2}~{}\forall i\in V$, and therefore

Thirdly, by applying the result of ${\bm{y}}^{(k)}-{\bm{y}}^{(k-1)}\rightarrow{\bm{0}}$ and (A.23) to (A.4), we have

Proof of Theorem 1(b): Let $0<\alpha<1$ be some positive number and rewrite (A) as

Then, in order to prove linear convergence rate, i.e., for some $\delta>0$,

By applying (A.12) and (A.13), (A) can be expressed as

After stacking (A) for $i=1,\ldots,N$, one obtains

According to Note that the matrix ${\bm{\Upsilon}}$ corresponds to matrix $M_{-}$ in ., both ${\bm{u}}^{(k+1)}$ and ${\bm{u}}^{\star}$ lie in the range space of ${\bm{\Upsilon}}^{T}$. Hence, one can show that

where $\sigma_{\min}({\bm{\Upsilon}})>0$ is the minimum nonzero singular value of ${\bm{\Upsilon}}$. From (A), we have that

where the first inequality is due to the fact that

for any ${\bm{a}},{\bm{q}}$ and $\mu>0,$ the second inequality is obtained by setting $\mu>1$ and (A.32), and the last inequality is by (14). Equation (A) implies that

which are respectively satisfied if the following three conditions can be satisfied for some $\delta>0$

Appendix B Proof of Theorem 3

Firstly, by recalling that ${\bm{p}}_{i}^{(k)}=\textstyle\sum_{j\in{\mathcal{N}}_{i}}({\bm{u}}_{ij}^{(k)}+{\bm{v}}_{ji}^{(k)})$, it follows from (IV-A) and (A.39) that

By multiplying ${\bm{\nu}}_{i}^{(k)}-{\bm{\nu}}^{\star}$ to the both sides of (A.43), we obtain

Secondly, from the optimality of (IV-B), we have that

where, in the first equality, we have added and subtracted $\frac{1}{2c|{\mathcal{N}}_{i}|}{\bf E}_{i}^{T}{\bf E}_{i}{\bm{x}}_{i}^{(k)}$ and defined

the second equality is due to (IV-A); and the last equality is because ${\bm{x}}_{i}^{\star}$ is a maximizer to (8) with ${\bm{\nu}}={\bm{\nu}}_{i}^{\star}$. Multiplying both (A.46) and (A.47) with ${\bm{x}}_{i}^{(k)}-{\bm{x}}_{i}^{\star}$, combining with (B), and summing for $i=1,\ldots,N$, yields

Similar to (A) and by (31), the fifth term in the LHS of (B) can be expressed as

Moreover, the sixth term in the LHS of (B) can be shown as

where ${\bm{Q}}\triangleq({\bm{D}}+{\bm{W}})\otimes{\bm{I}}_{M}$. By applying (A), (A), (A.9), (B) and (B) to (B), one obtains

It is easy to show that, under (49), it holds true that

for some $\sigma_{f,i}^{2}\leq\rho_{i}<2\sigma_{f,i}^{2}$ $\forall i\in V$, which implies that

Thirdly, applying the fact of ${\bm{u}}_{ij}^{(k+1)}-{\bm{u}}_{ij}^{(k)}\rightarrow{\bm{0}}$ to (31a) yields

The result of ${\bm{\nu}}_{i}^{(k)}-{\bm{\nu}}_{j}^{(k)}\to{\bm{0}}~{}\forall j,i$ and Assumption 1 implies that ${\bm{\nu}}^{(k)}-{\bf 1}_{N}\otimes{\bm{\nu}}^{(k)}_{i}\rightarrow{\bm{0}}$ for any $i\in V$. Since the Laplacian matrix ${\bm{L}}{\bf 1}_{N}={\bm{0}}$ , one obtains

which, when combined with (A.56), further implies that

By applying (A.61) to (A.42), one obtains

where $\partial\varphi_{i}(\hat{}{\bm{\nu}}_{i})=-{\bf E}_{i}\hat{}{\bm{x}}_{i}$ since (A.57) implies that $\hat{}{\bm{x}}_{i}$ is a maximizer to (8) with ${\bm{\nu}}=\hat{}{\bm{\nu}}_{i}$ . Finally, by summing (A.62) for $i=1,\ldots,N$, followed by applying (A) and (A.58), one obtains

Therefore, it suffices to show that, for some $\delta>0$,

Firstly, from (A.45) and (A.47), we have that (without $g_{i}$’s)

By applying (A.34) to (B), we have, for some $\mu_{1}>1$,

where the second inequality is obtained by (14). Note that ${\bm{D}}+{\bm{W}}=2{\bm{D}}-{\bm{L}}\preceq 2{\bm{D}}$ as ${\bm{L}}\succeq{\bm{0}}$ . Hence, we have

where the second inequality is due to (B), \tau_{1}=\max_{i\in V}\big{\{}\frac{|{\mathcal{N}}_{i}|}{(1-\frac{1}{\mu_{1}})\lambda_{\min}({\bf E}_{i}{\bf E}_{i}^{T})}\big{\}}>0 and \tau_{2}=\max_{i\in V}\big{\{}\frac{(\mu_{1}-1)\lambda_{\max}^{2}({\bm{A}}_{i}^{T}{\bm{A}}_{i})|{\mathcal{N}}_{i}|L_{f,i}}{(1-\frac{1}{\mu_{1}})\lambda_{\min}({\bf E}_{i}{\bf E}_{i}^{T})}\big{\}}>0 are finite given that ${\bf E}_{i}$’s have full row rank.

Secondly, upon stacking (A.43) for all $i\in V$ and applying (A.3) and (A.12), one obtains

where ${\bf E}={\rm blkdiag}\{{\bf E}_{1},\ldots,{\bf E}_{N}\}$ and ${\bm{\Upsilon}}$ is given in (A.31). Analogously, by applying (A.34) to (B) and by (A.32), one can show that, for some $\mu_{2}>1$,

where $\tau_{3}={(1-\frac{1}{\mu_{2}})\sigma_{\min}^{2}({\bm{\Upsilon}})}>0$. By (B) and (B), sufficient conditions for satisfying (B) are therefore given by: $\forall i\in V,$

Under (A.54) and full column rank ${\bm{A}}_{i}$’s, we see that (A.71) is true for some $\delta>0$. The proof is complete. $\blacksquare$

References