Distributed Linearized Alternating Direction Method of Multipliers for Composite Convex Consensus Optimization

I Introduction

where $\xi_{i}$ is a possibly non-smooth convex function, and $f_{i}$ is a smooth convex function.

is efficiently computable for $i\in\mathcal{N}$.

In this paper, we study a distributed consensus problem ; in particular, we consider solving a multi-agent consensus optimization problem of minimizing the sum of privately known composite convex functions in (1) satisfying Assumption 1:

We consider the setting where only local information exchange is allowed, i.e., there is no central node such that the data can be collected, and only neighboring nodes can exchange data; and we focus on the following equivalent formulation:

The contribution of the paper can be summarized as follows: 1) we propose a proximal gradient alternating direction method of multipliers (PG-ADMM) and its stochastic gradient variant SPG-ADMM to solve composite convex problems; we only assume that the prox map of $\xi_{i}$ can be computed efficiently, while other ADMM based algorithms are efficient when either $\Phi_{i}=\xi_{i}+f_{i}$ or both $\xi_{i}$ and $f_{i}$ have simple prox maps that can be computed efficiently; 2) we establish that when the gradient is deterministic PG-ADMM is equivalent to primal-dual algorithms for saddle-point problems proposed in – hence, SPG-ADMM extends these algorithms to noisy gradient setting; 3) we show ergodic convergence of both (expected) suboptimality and consensus violation bounds for PG-ADMM with the rate of $\mathcal{O}(1/t)$, and for SPG-ADMM with the rate of $\mathcal{O}(1/\sqrt{t})$; 4) we implement PG-ADMM and SPG-ADMM on consensus formulations of (3) for unweighted and weighted static communication networks – this gives rise to two different node-based distributed algorithms: DPGA and DPGA-W and their stochastic gradient variants SDPGA and SDPGA-W – and we examine the effect of the underlying network topology on their convergence rate. 5) The proposed algorithms DPGA, DPGA-W, SDPGA and SDPGA-W are fully distributed, i.e., the agents are not required to know any global parameters depending on the entire network topology, e.g., the second smallest eigenvalue of the Laplacian; instead, we only assume that agents know who their neighbors are. Using only local communication, our node-based distributed algorithms require less communication burden and memory storage compared to edge-based distributed algorithms. 6) Proposed algorithms consist of a single loop, i.e., there are no outer and inner iteration loops; therefore, they are easy and practical to be implemented over distributed networks.

To sum up, there are many practical problems where one can compute the prox map for $\xi_{i}$ efficiently; however, computing the prox map for $\Phi_{i}=\xi_{i}+f_{i}$ is not easy. The methods proposed in this paper can compute an $\epsilon$-optimal $\epsilon$-feasible solution in $\mathcal{O}(\epsilon^{-1})$ iterations without assuming bounded $\nabla f_{i}$ for any $i\in\mathcal{N}$; each iteration of these methods requires computing $\mathbf{prox}_{\xi_{i}}$ and $\nabla f_{i}$ for $i\in\mathcal{N}$, and one or two communication rounds among the neighbors – hence, $\mathcal{O}(\epsilon^{-1})$ communications per node in total.

I-B Related work

Wei & Ozdaglar , and recently Makhdoumi & Ozdaglar proposed distributed ADMM algorithms that can compute an $\epsilon$-optimal and $\epsilon$-feasible solution in $\mathcal{O}(1/\epsilon)$ prox map evaluations for each $\Phi_{i}$. These algorithms have superior iteration complexity compared to the subgradient methods discussed above. That said, there are many practical problems where one can compute $\mathbf{prox}_{\xi_{i}}$ efficiently; but, computing the prox map for $\Phi_{i}=\xi_{i}+f_{i}$ is not easy -see Section IV for an example. One can overcome this limitation of ADMM by locally splitting variables, i.e., setting $\Phi_{i}(x_{i},y_{i})\triangleq\xi_{i}(x_{i})+f_{i}(y_{i})$, and adding a constraint $x_{i}=y_{i}$ in (4). However, this approach more than doubles local memory requirement; and in order for ADMM to be efficient, the prox maps for both $\xi_{i}$ and $f_{i}$ still must be simple.

When node functions $\Phi_{i}$ are composite convex, i.e., $\Phi_{i}=\xi+f_{i}$, assuming that the non-smooth term $\xi$ is the same at all nodes, and $\nabla f_{i}$ is bounded for all $i\in\mathcal{N}$, Chen & Ozdaglar proposed an inexact proximal-gradient method, which exploits the function structure, for distributed minimization of (3) over a time-varying network topology. Their method also consists of two loops; it can compute $\epsilon$-feasible and $\epsilon$-optimal solution in $T=\mathcal{O}(1/\sqrt{\epsilon})$ iterations which require $k$ communication rounds with neighbors during the $k$-th iteration for each $1\leq k\leq T$ – hence, leading to $\sum_{k=1}^{T}k=\mathcal{O}(\epsilon^{-1})$ communications per node in total. Note that there are also many practical problems where nodes in the network have different non-smooth components in their objective and/or have different preference when choosing non-smooth regularizers. In contrast, our methods allow node specific non-smooth functions $\xi_{i}$, do not assume bounded $\nabla f_{i}$ for any $i\in\mathcal{N}$, and are still able to compute an $\epsilon$-optimal $\epsilon$-feasible solution in $\mathcal{O}(\epsilon^{-1})$ iterations.

Aybat et al. proposed a distributed first-order augmented Lagrangian (DFAL) algorithm to solve (3), where each $\Phi_{i}$ is a composite convex function as in (1). Assuming $\xi_{i}$ is bounded below by a norm, i.e., $\xi_{i}(.)\geq\left\|.\right\|$, and it has a uniformly bounded subdifferential for each $i\in\mathcal{N}$, they showed that any limit point of DFAL iterates is optimal; and for any $\epsilon>0$, an $\epsilon$-optimal and $\epsilon$-feasible solution can be computed within $\mathcal{O}(\log(\epsilon^{-1}))$ DFAL iterations, which require $\mathcal{O}(\frac{\sigma_{\max}^{1.5}(\Omega)}{d_{\min}}~{}\epsilon^{-1})$ gradient computations and communications per node in total, where $d_{\min}$ is the degree of the smallest degree node. Based on our tests and the results reported in the algorithm DFAL performs very well in practice; however, due to its double-loop structure, distributed implementation requires a more complex network protocol. Specifically, checking the subgradient stopping criterion for inner iterations requires evaluating a logical conjunction over $\mathcal{G}$, which may not be easy for large networks.

Table II summarizes the storage and communication requirements for the algorithms discussed above. We will illustrate their practical performance in Section IV. After we started writing this paper, we became aware of other recent work for solving (3) over a connected graph $\mathcal{G}$. These methods are very closely related to our proximal gradient ADMM (PG-ADMM), and are based on linearized ADMM method. Suppose $\Phi_{i}(x)=\xi_{i}(x)+f_{i}(A_{i}x)$. When compared to our smooth convexity assumption on $\{f_{i}\}_{i\in\mathcal{N}}$, Chang et al. showed the convergence of their distributed method under a far more stringent assumption: $f_{i}$ is strongly convex with a Lipschitz continuous gradient for $i\in\mathcal{N}$. Moreover, under this stronger assumption, they were able to show linear convergence rate only when the non-smooth terms are absent, i.e., $\xi_{i}\equiv 0$, and $A_{i}$ has full column rank for all $i\in\mathcal{N}$. Finally, their distributed algorithm requires the global knowledge of $\sigma_{\min}(\Omega+2W)$ of the graph $\mathcal{G}$, where $W$ is the adjacency matrix. On the other hand, the algorithms we propose in this paper are fully distributed, i.e., the agents do not require the knowledge of some global parameters depending on the entire network topology; instead, we only assume that agents know who their neighbors are. Ling et al. were able to show the convergence of their distributed method without strong convexity when penalty parameter is chosen sufficiently large; however, no rate has been shown for this setting – again, as in determining whether the parameter is large enough requires the global knowledge of $\sigma_{\min}(\Omega)$. The algorithm in is similar to our DPGA algorithm, and in contrast to sublinear rate result shown in this manuscript for the convex setting, Ling et al. were able to establish a rate result only under strong convexity assumption. Bianchi et al. also proposed a distributed algorithm based on linearized ADMM for solving (3), where each node computes proximal gradient steps; the authors proved its convergence and also showed almost sure convergence for its randomized version, where a random set of agents become active and compute their proximal gradient steps and broadcast the recently updated local variables to their neighbors. However, no rate has been shown for neither the deterministic nor the randomized versions. The methods in run on edge-based formulations of the decentralized problem; consequently, information exchange, computational effort and memory requirement are far more expensive than node-based algorithms proposed in this paper. While we are finalizing our paper, we become aware of the work , where the authors also develop a distributed algorithm based on linearized ADMM for solving (3) over both random and static networks and they attain similar rate results to ours. For the static network setting, their algorithm achieves $\mathcal{O}(1/t)$ rate using deterministic gradient and $\mathcal{O}(1/\sqrt{t})$ rate using the stochastic gradient; however, in contrast to our results, these rates are established assuming bounded domain for all $\xi_{i}$ (for both deterministic and stochastic gradient settings); explicit bounds for suboptimality and infeasibility are not separately provided; and when the gradient is noisy, their algorithm does not have a compact characterization using only primal local decisions (see Theorem 4.2 and Algorithm 1 in ) – even if the network is static, in case the gradient is noisy, one needs to use Algorithm 1 which requires updating edge-variables and explicitly computing the dual variables, while our algorithm SDPGA using stochastic gradient is in a compact form updating only primal node-variables, does not explicitly compute the dual iterates and still achieves $\mathcal{O}(1/\sqrt{t})$ rate without assuming compact domain for any $\xi_{i}$.

The focus of our paper is on synchronous computation over undirected static communication topology; that said, there has been work considering more general settings, e.g., see for distributed optimization on directed graphs, and for computation over random networks.

To sum up, unlike two-loop methods, e.g., , DPGA algorithms proposed here have only single-loop, and they are very easy to implement - see Fig. 1 and Fig. 2. These surprisingly simple algorithms can compute an $\epsilon$-feasible and $\epsilon$-optimal solution to (3) within $\mathcal{O}(1/\epsilon)$ communication rounds among neighboring nodes for all $\epsilon>0$ (this is the best rate known for our setting) under much weaker assumptions on $\xi_{i}$ and $f_{i}$ compared to DFAL and with much simpler set of instructions compared to all the algorithms discussed above. To the best of our knowledge, in terms of storage and communication requirements per communication round, and convergence rate in terms of communication rounds, DPGA achieves the best guarantees known in the literature for problem (3) when $\Phi_{i}$ is as in (1) for $i\in\mathcal{N}$.

II Proximal Gradient ADMM and its connections

where $\lambda=[\lambda_{i}]_{i\in\mathcal{N}}$, and $\phi_{\gamma}$ denotes the smooth part of the augmented Lagrangian, i.e.,

Note setting $\gamma_{i}=0$ for all $i\in\mathcal{N}$, $\mathcal{L}_{\gamma}$ becomes the standard Lagrangian function $\mathcal{L}(\mathbf{x},y,\lambda)$.

Consider the algorithm PG-ADMM stated below for solving (5): for $k\geq 0$ compute

where $c_{i}>0$ is the gradient step size for $i\in\mathcal{N}$, which should be related to $L_{i}$ and $\left\|A_{i}\right\|$. In Section II-A, we study the convergence properties of (6) given a deterministic first-order oracle which returns $\nabla f_{i}$; and we also consider the effect of using stochastic first-order oracle, which returns noisy observations of $\nabla f_{i}$, on the convergence rate.

Let $G_{i}$ denote an SFO for $\nabla f_{i}$ for $i\in\mathcal{N}$ with common parameter $\sigma$. Let $\bar{G}_{i}$ be an SFO for $\nabla_{x_{i}}\phi_{\gamma}$ defined as $\bar{G}_{i}(x_{i},\nu_{i};x_{-i},y,\lambda)=G_{i}(x_{i},\nu_{i})+A_{i}^{\mathsf{T}}\left(\lambda_{i}+\gamma_{i}(A_{i}x_{i}+B_{i}y-b_{i})\right)$.

Under Assumption 2, consider the algorithm SPG-ADMM stated below for solving (5):

for $k\geq 0$, where $c_{i}^{k}>0$ is the stochastic-gradient step size for $i\in\mathcal{N}$ at the $k$-th iteration.

In the extreme case that $\xi_{i}=0$ for $i\in\mathcal{N}$ and $|\mathcal{N}|=1$, PG-ADMM (6) and SPG-ADMM (7) reduce to G-ADMM and SG-ADMM that take gradient steps for $x_{i}$-subproblems and have been studied in and . Specifically, proves the $O(1/t)$ convergence rate of G-ADMM and $O(1/\sqrt{t})$ convergence rate of SG-ADMM. Our PG-ADMM and SPG-ADMM can be viewed as extensions of G-ADMM and SG-ADMM where general $\xi_{i}$’s are allowed. Our proofs of convergence rate results for PG-ADMM and SPG-ADMM in Section II-A are inspired by .

Preliminaries and Simple Identities: In our analysis, we used two well-known identities frequently:

We denote the set of optimal primal-dual pairs for (5) as $\chi^{*}$, i.e., $w^{*}=(\mathbf{x}^{*},y^{*},\lambda^{*})\in\chi^{*}$ if and only if $w^{*}$ is a saddle point of the Lagrangian function $\mathcal{L}$ corresponding to (5). Moreover, for $i\in\mathcal{N}$, define $\chi_{i}^{*}$ as the projection of $\chi^{*}$ onto $x_{i}$-coordinate.

We analyze SPG-ADMM, stated in (7), under Assumptions 2 and 3; and specialize these results for PG-ADMM stated in (6). The following assumption is made in the rest of the discussions.

The optimal primal-dual pair set $\chi^{*}$ for (5) is non-empty, i.e., there exists $(\mathbf{x}^{*},y^{*},\lambda^{*})\in\chi^{*}$ such that $\mathcal{L}(\mathbf{x},y,\lambda^{*})\geq\mathcal{L}(\mathbf{x}^{*},y^{*},\lambda^{*})\geq\mathcal{L}(\mathbf{x}^{*},y^{*},\lambda)$ for all $\mathbf{x}$, $y$, $\lambda$.

According to the first-order optimality conditions for (5), solving (5) is equivalent to finding $(\mathbf{x}^{*},y^{*},\lambda^{*})\in\chi^{*}$ such that the following holds:

Note PG-ADMM and SPG-ADMM produce the same iterate sequence with probability 1 when $\sigma=0$ in Definition 2. Therefore, we will first analyze SPG-ADMM, and then derive the bounds for PG-ADMM by sharpening the SPG-ADMM bounds for the case $\sigma=0$. After some constant terms are discarded, SPG-ADMM for solving (5) can be stated as: for $k\geq 0$,

The first-order optimality conditions for (11a)-(11b) are given respectively as follows

Since $\xi_{i}$ and $g$ are convex, using the subgradients above with (11c), we have

We analyze the convergence of SPG-ADMM when either $D<+\infty$ or $D^{*}(\mathbf{x}^{0})<\infty$.

Starting from given $w^{0}$ such that $-\sum_{i=1}^{N}B_{i}^{\top}\lambda_{i}^{0}\in\partial g(y^{0})$, Let $\{w^{k}\}_{k\geq 1}$ be the SPG-ADMM iterate sequence generated as in (11a)-(11c). If $\{c_{i}^{k}\}_{k\geq 0}$ is chosen such that $c_{i}^{k}\leq\left(L_{i}+{\gamma_{i}}\left\|A_{i}\right\|^{2}+\mathds{1}(\delta_{i}^{k})(1+\sqrt{k})\right)^{-1}$ for all $i\in\mathcal{N}$ and $k\geq 0$, then for any $\lambda$ and $u^{*}=(\mathbf{x}^{*},y^{*})\in\chi^{*}$, the following inequality holds for all $k\geq 0$,

where $\mathds{1}(\delta_{i}^{k})$ is $1$ if $\left\|\delta_{i}^{k}\right\|>0$, and equal to otherwise, i.e., when $\delta_{i}^{k}=0$; and \bar{Q}_{i}^{k}\triangleq\frac{1}{c_{i}^{k}}Q_{i}^{k}-\big{(}L_{i}+\mathds{1}(\delta_{i}^{k})(1+\sqrt{k})\big{)} for $k\geq 0$ and $i\in\mathcal{N}$.

where the equality follows from identity (8) with $Q=Q_{i}^{k}$, and from the definition of $\delta_{i}^{k}$. Since each $f_{i}$ is convex with Lipschitz continuous $\nabla f_{i}$ for all $x_{i}\in\mathop{\bf dom}\xi_{i}$, we have $0\leq f_{i}(x_{i})-f_{i}(x_{i}^{k})-\nabla f_{i}(x_{i}^{k})^{\top}(x_{i}-x_{i}^{k})\leq\frac{L_{i}}{2}\left\|x_{i}-x_{i}^{k}\right\|^{2}$; hence

Moreover, it also trivially follows from the definition of $\mathds{1}(\delta_{i}^{k})$ that

Finally, applying identity (9) with $Q=I_{m_{i}}$, $v_{1}=A_{i}x_{i}-b_{i}$, $v_{2}=A_{i}x^{k+1}_{i}-b_{i}$, $v_{3}=-B_{i}y^{k+1}$, and $v_{4}=-B_{i}y^{k}$, we have

Therefore, using (17), (18) and (19) within (16), it follows that

Thus, adding $\sum_{i=1}^{N}\frac{1}{2\gamma_{i}}\left\|\lambda_{i}^{k+1}-\lambda_{i}^{k}\right\|^{2}$ to both side of (21), and using the above equality, we obtain the desired inequality in (15). Indeed, since $u^{*}$ is a solution to (5), $A_{i}x_{i}^{*}+B_{i}y^{*}=b_{i}$ for $i\in\mathcal{N}$. Hence, for any $\lambda$ and $\hat{w}$

We use the above equality with $\hat{w}=w^{k+1}$ to simplify (21). ∎

Under Assumptions 1, 2 and 3, let $\{w^{k}\}_{k\geq 1}$ be the SPG-ADMM iterate sequence generated as in (11a)-(11c) starting from given $w^{0}=\left(\mathbf{x}^{0},y^{0},\lambda^{0}\right)$ as in Lemma 2. Define $\bar{u}^{t}=(\bar{\mathbf{x}}^{t},\bar{y}^{t})$ as $\bar{\mathbf{x}}^{t}=\frac{1}{t}\sum_{k=1}^{t}\mathbf{x}^{k}$, and $\bar{y}^{t}=\frac{1}{t}\sum_{k=1}^{t}y^{k}$ for $t\geq 1$. Fix arbitrary $\lambda$ and $u^{*}=(\mathbf{x}^{*},y^{*})\in\chi^{*}$.

Suppose $\sigma>0$ and $D<\infty$. For $i\in\mathcal{N}$, when $\{c_{i}^{k}\}_{k\geq 0}$ is chosen such that $\frac{1}{c_{i}^{k}}=\frac{1}{c_{i}}+\sqrt{k}$ and $c_{i}=(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}+1)^{-1}$, then the following bounds hold for $\bar{D}=D$ and for all $t\geq 1$:

Suppose $\sigma=0$, i.e., $G_{i}(x_{i})=\nabla f_{i}(x_{i})$ w.p.1 for any $x_{i}$ and $i\in\mathcal{N}$. When $c_{i}^{k}=c_{i}$ for all $k\geq 0$ for some $c_{i}\in(0,\frac{1}{L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}}]$, the following bound holds w.p.1 for all $t\geq 1$,

Invoking the convexity of $F(\cdot)$ justifies the first inequality below:

where the second inequality follows from Lemma 2 and the fact that $\bar{Q}_{i}^{k}\succeq\mathbf{0}$ for $k\geq 0$.

First, consider the PG-ADMM iterate sequence generated using $G_{i}(x_{i}^{k},\nu_{i}^{k})=\nabla f_{i}(x_{i}^{k})$, i.e., $\delta_{i}^{k}=0$ for all $i\in\mathcal{N}$ and $k\geq 0$. In this setting, according to Lemma 2, we are allowed to fix a constant step size $c_{i}$ for each $i\in\mathcal{N}$. Indeed, $c_{i}^{k}=c_{i}\triangleq\left(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}\right)^{-1}$ for $k\geq 1$. Hence, one obtains the desired result in (3) by showing

which follows from dropping the non-positive terms after the telescoping sum in the definition of $\Gamma^{t}$ is evaluated, and using the fact that $A_{i}x_{i}^{*}+B_{i}y^{*}=b_{i}$ for all $i\in\mathcal{N}$.

Next, consider the SPG-ADMM iterate sequence for which $\delta_{i}^{k}>0$ with probability 1 for all $i\in\mathcal{N}$ and $k\geq 0$. In this case, according to Lemma 2, if one sets $c_{i}^{k}=\left(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}+1+\sqrt{k}\right)^{-1}$ for all $i\in\mathcal{N}$ and $k\geq 0$, then $F(\bar{u}^{t})-F(u^{*})+\sum\limits_{i\in\mathcal{N}}\lambda_{i}^{\top}\left(A_{i}\bar{x}_{i}^{t}+B_{i}\bar{y}^{t}-b_{i}\right)\leq\Gamma^{t}$ holds for all $t\geq 1$. Moreover, we also have

We obtain the desired result by taking the expectation of both sides in (25) and using the inequality $\sum_{k=0}^{t-1}\frac{1}{1+\sqrt{k}}\leq\int_{0}^{t-1}\frac{1}{1+\sqrt{s}}ds\leq\sqrt{t}$. ∎

Suppose $\sigma>0$ and $D=\infty$. Assume that $D^{*}(\mathbf{x}^{0})<\infty$. For any $t\geq 1$, let $\{c_{i}^{k}\}_{0\leq k\leq t}$ be chosen such that $\frac{1}{c_{i}^{k}}=\frac{1}{c_{i}}+\sqrt{t}$ and $c_{i}=(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}+1)^{-1}$ for $i\in\mathcal{N}$, then (3) holds for $\bar{D}=D^{*}(\mathbf{x}^{0})$.

Now we are ready to prove the $O(1/t)$ and $O(1/\sqrt{t})$ convergence rates of PG-ADMM stated in (6) and SPG-ADMM stated in (7) in an ergodic sense for solving (5).

Under the same settings of Theorem 3, fix an arbitrary point $(u^{*},\lambda_{1}^{*},\ldots,\lambda_{N}^{*})\in\chi^{*}$.

Suppose $\sigma=0$, i.e., $G_{i}(x_{i})=\nabla f_{i}(x_{i})$ w.p.1 for any $x_{i}$ and $i\in\mathcal{N}$. When $c_{i}^{k}=c_{i}$ for all $k\geq 0$ for some c_{i}\in\big{(}0,~{}{\frac{1}{L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}}}\big{)}, the following bounds hold for all $t\geq 1$:

where C(c_{1},\ldots,c_{N})\triangleq\sum\limits_{i=1}^{N}\Big{(}\frac{1}{\gamma_{i}}\left(4\|\lambda_{i}^{*}\|^{2}+\left\|\lambda_{i}^{0}\right\|^{2}\right)+\frac{1}{2c_{i}}\left\|x_{i}^{*}-x_{i}^{0}\right\|_{Q_{i}}^{2}\Big{)}+\frac{1}{2}\left\|y^{*}-y^{0}\right\|_{\sum_{i=1}^{N}\gamma_{i}B_{i}^{\top}B_{i}}^{2}. and $Q_{i}\triangleq I-c_{i}\gamma_{i}A_{i}^{\top}A_{i}$. Moreover, both $\{w^{k}\}_{k\geq 0}$ and $\{\bar{w}^{k}\}_{k\geq 0}$ converge to a primal-dual optimal point if $B\triangleq[B_{i}]_{i\in\mathcal{N}}$, formed by vertically concatinating $\{B_{i}\}_{i\in\mathcal{N}}$, has full column rank.

Suppose $\sigma>0$. Fix $c_{i}=(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2}+1)^{-1}$ for $i\in\mathcal{N}$ and set $C\triangleq C(c_{1},\ldots,c_{N})$. Let $C^{\prime}\triangleq N(D^{2}/2+\sigma^{2})$, and $D\triangleq\max_{i\in\mathcal{N}}\sup_{x,x^{\prime}\in\mathop{\bf dom}(\xi_{i})}\left\|x-x^{\prime}\right\|$. When $\{c_{i}^{k}\}_{k}$ sequence is chosen as $c_{i}^{k}=\left(\frac{1}{c_{i}}+\sqrt{k}\right)^{-1}$ for $i\in\mathcal{N}$, the following bounds hold for all $t\geq 1$:

Suppose $\sigma=0$. Consider $\bar{Q}_{i}^{k}$ defined in Lemma 2; since $c_{i}^{k}=c_{i}\in(0,(L_{i}+\gamma_{i}\left\|A_{i}\right\|^{2})^{-1})$, we have $\bar{Q}_{i}\triangleq\bar{Q}_{i}^{k}=\frac{1}{c_{i}}Q_{i}-L_{i}\succ\mathbf{0}$ for $k\geq 0$ and $i\in\mathcal{N}$. For $i\in\mathcal{N}$, let $a_{i}^{k}\triangleq\frac{1}{c_{i}}\left\|x_{i}^{k}-x_{i}^{*}\right\|_{Q_{i}}^{2}+\gamma_{i}\left\|B_{i}(y^{k}-y^{*})\right\|^{2}+\frac{1}{\gamma_{i}}\left\|\lambda_{i}^{k}-\lambda^{*}_{i}\right\|^{2}$ and $b_{i}^{k}\triangleq\left\|x_{i}^{k+1}-x_{i}^{k}\right\|_{\bar{Q}_{i}}^{2}+\gamma_{i}\left\|B_{i}(y^{k+1}-y^{k})\right\|^{2}+\frac{1}{\gamma_{i}}\left\|\lambda_{i}^{k+1}-\lambda_{i}^{k}\right\|^{2}$; define $a^{k}\triangleq\sum_{i=1}^{N}a_{i}^{k}$ and $b^{k}\triangleq\sum_{i=1}^{N}b_{i}^{k}$ for $k\geq 0$. Hence, Lemma 2 implies that $a^{k+1}+b^{k}\leq a^{k}$ for $k\geq 0$, where we used $F(u^{*})\leq F(u^{k+1}){+\sum_{i=1}^{N}\left\langle\lambda^{*}_{i},~{}A_{i}x_{i}^{k+1}+B_{i}y^{k+1}-b_{i}\right\rangle}$ because $\mathcal{L}(\mathbf{x}^{k+1},y^{k+1},\lambda^{*})\geq\mathcal{L}(\mathbf{x}^{*},y^{*},\lambda^{*})$. Therefore, $\lim_{k}a^{k}$ exists and $\sum_{k=0}^{\infty}b^{k}<\infty$, which implies that $\{a_{i}^{k}\}_{k\geq 0}$ is bounded for all $i$. Moreover $Q_{i}\succ\mathbf{0}$ implies that $\{\lambda_{i}^{k}\}$, $\{x_{i}^{k}\}$ and $\{B_{i}y^{k}\}$ are all bounded sequences for $i\in\mathcal{N}$. If $B$ has full column rank, $\{y^{k}\}$ is bounded. Hence, there exists $\{k_{n}\}_{n\geq 0}$ such that $\lim_{n}\lambda_{i}^{k_{n}}\triangleq\bar{\lambda}$, $\lim_{n}x_{i}^{k_{n}}\triangleq\bar{x}$ for all $i$ and $\lim_{n}y^{k_{n}}\triangleq\bar{y}$ exist. Moreover, since $\sum_{k=1}^{\infty}b^{k}<\infty$, we have $\sum_{k=1}^{\infty}b_{i}^{k}<\infty$ for $i\in\mathcal{N}$; thus, $\lim_{k}\left\|x_{i}^{k+1}-x_{i}^{k}\right\|=\lim_{k}\left\|\lambda_{i}^{k+1}-\lambda_{i}^{k}\right\|=0$ for all $i$, and $\lim_{k}\left\|y^{k+1}-y^{k}\right\|=0$. This implies that $\lim_{n}\lambda_{i}^{k_{n}\pm 1}=\bar{\lambda}$, $\lim_{n}x_{i}^{k_{n}\pm 1}=\bar{x}$ for $i\in\mathcal{N}$ and $\lim_{n}y^{k_{n}\pm 1}=\bar{y}$. Note $A_{i}\bar{x}_{i}+B\bar{y}-b_{i}=\lim_{n}A_{i}x_{i}^{k_{n}}+By^{k_{n}}-b_{i}=\frac{1}{\gamma_{i}}\lim_{n}\lambda_{i}^{k_{n}}-\lambda_{i}^{k_{n}-1}=0$. Now, consider the subsequential limit of both sides of the relations in (12) along $k_{n}$. Since $g$ and $\xi_{i}$ for all $i$ are proper, closed convex functions, it follows from Theorem 24.4 in that $\mathbf{0}\in\partial\xi_{i}(\bar{x}_{i})+\nabla f_{i}(\bar{x}_{i})+A_{i}^{\top}\bar{\lambda}$ for all $i$, and $\mathbf{0}\in\partial g(\bar{y})+\sum_{i=1}^{N}B_{i}^{\top}\bar{\lambda}$. Thus $\bar{w}=(\bar{x},\bar{y},\bar{\lambda})$ is a primal-dual point for (5). Now define $r_{i}^{k}\triangleq\frac{1}{\gamma_{i}}\left\|\bar{\lambda}_{i}-\lambda_{i}^{k}\right\|^{2}+\frac{1}{c_{i}}\left\|\bar{x}_{i}-x_{i}^{k}\right\|_{Q_{i}}^{2}+\gamma_{i}\left\|B_{i}(y^{k}-\bar{y})\right\|^{2}$ and $r^{k}=\sum_{i=1}^{N}r_{i}^{k}$ for $k\geq 0$. Thus $\lim_{k}r^{k}=\lim_{n}r^{k_{n}}=0$ and we have $\lim x_{i}^{k}=\bar{x}$ (since $\bar{Q}\succ\mathbf{0}$) and $\lim\lambda_{i}^{k}=\bar{\lambda}$ for all $i$, and $\lim_{k}y^{k}=\bar{y}$.

In the rest, we prove the rate result. Since any $(u^{*},\lambda^{*})\in\chi^{*}$ is a saddle point of $\mathcal{L}$, it satisfies $\mathcal{L}(u,\lambda^{*})\geq\mathcal{L}(u^{*},\lambda^{*})$ for any $u=(\mathbf{x},y)$, which can be easily checked using the optimality condition (10). Thus, setting $u=\bar{u}^{t}=(\bar{\mathbf{x}}^{t},\bar{y}^{t})$ and using the fact that $A_{i}x_{i}^{*}+B_{i}y^{*}=b_{i}$ for $i\in\mathcal{N}$ we obtain

Let $\rho_{i}\triangleq 2\|\lambda_{i}^{*}\|$ and $\bar{\tau}_{i}\triangleq A_{i}\bar{x}_{i}^{t}+B_{i}\bar{y}^{t}-b_{i}$ for $i=1,2,\ldots,N$. Note (3) holds for any $\lambda=[\lambda_{i}]_{i\in\mathcal{N}}$; hence, by setting $\lambda_{i}=\rho_{i}\bar{\tau}_{i}/\left\|\bar{\tau}_{i}\right\|$ in (3), noting that $\|\lambda_{i}\|=\rho_{i}$, and using $\left\|\lambda_{i}-\lambda_{i}^{0}\right\|^{2}/2\leq\left\|\lambda_{i}\right\|^{2}+\left\|\lambda_{i}^{0}\right\|^{2}$, we obtain $F(\bar{u}^{t})-F(u^{*})+\sum\limits_{i=1}^{N}\rho_{i}\left\|A_{i}\bar{x}_{i}^{t}+B_{i}\bar{y}^{t}-b_{i}\right\|\leq C(c_{1},\ldots,c_{N})/t$. From (26) and the above inequality, it follows that

Hence, since $\rho_{i}\triangleq 2\left\|\lambda_{i}^{*}\right\|$, it follows that $\sum_{i=1}^{N}\|\lambda_{i}^{*}\|\|\bar{\tau}_{i}\|\leq\frac{C(c_{1},\ldots,c_{N})}{t}$. Therefore, one can conclude that $\max\{|F(\bar{u}^{t})-F(u^{*})|,\ \sum_{i=1}^{N}\|\lambda_{i}^{*}\|\|A_{i}\bar{x}_{i}^{t}+B_{i}\bar{y}^{t}-b_{i}\|\}\leq\frac{C(c_{1},\ldots,c_{N})}{t}$.

II-B Connections to the existing work

There is a strong connection between PG-ADMM and the primal-dual algorithms (PDA) in proposed for solving saddle point problems. Let $\Phi=\xi+f$ as in (1) such that $\nabla f$ is Lipschitz with constant $L$; after fixing stepsize $c>0$ and penalty parameter $\gamma>0$, implementing PG-ADMM on $\min_{x,y}\{\Phi(x)+g(y):\ Ax-y=\mathbf{0}\}$ generates the following iterate sequence:

For PG-ADMM iterate sequence, the suboptimality and infeasibility converges to 0 in the ergodic sense for any $\gamma>0$ when $\frac{1}{c}\geq L+\gamma\left\|A\right\|^{2}$. Note (27a) can be rewritten as $x^{k+1}=\mathbf{prox}_{c\xi}(x^{k}-c[\nabla f(x^{k})+A^{\top}(2\lambda^{k}-\lambda^{k-1})])$. Let $g^{*}$ denote the convex conjugate of $g$; using Moreau proximal decomposition on $y$-updates in (27b), we get

Combining (28) and (27c) shows $\lambda^{k+1}=\mathbf{prox}_{\gamma g^{*}}(\lambda^{k}+\gamma Ax^{k+1})$. Thus, (27) can be written as

The iterative scheme in (29) is the same as the PDA proposed in , where Condat only considered the convergence of the algorithm, and no iteration complexity was given in . The scheme in (29) is also a variant of PDA iterations in . In particular, PG-ADMM as written in (29) generates the same iterate sequence as $(x^{k+1},\lambda^{k+1})=\mathcal{P}\mathcal{D}_{c,\gamma}(x^{k},\lambda^{k},x^{k+1},2\lambda^{k}-\lambda^{k-1})$ in when the Bregman functions $D_{x}$ and $D_{\lambda}$ chosen as $\tfrac{1}{2}\left\|\cdot\right\|^{2}$. Moreover, one can easily prove that Theorem 1 in is still true for this variant of PDA for any $c,\gamma>0$ such that $(\frac{1}{c}-L)\frac{1}{\gamma}\geq\left\|A\right\|^{2}$. It is worth emphasizing that this equivalence is no longer true on problems $\min_{x,y}\{\Phi(x)+g(y):\ Ax+By=b\}$ with a general $B$, instead of $B=-I_{n_{y}}$. Note that PG-ADMM is more general than PDAs in in the sense that it can also deal with noisy gradients while PDAs cannot.

III Proximal Gradient Methods for Distributed Optimization

In this section, we provide consensus formulations of the decentralized optimization problem in (4) for unweighted and weighted static (undirected) communication networks; and these formulations are special cases of (5). Hence, we develop two different distributed algorithms based on PG-ADMM in (6), one for each formulation; and finally we derive the customized convergence bounds showing the effect of network topology for each implementation. Similarly, one can also implement SPG-ADMM in (7) on the two different decentralized formulations of (4) to obtain the stochastic gradient variants of these distributed algorithms based on SPG-ADMM. The error bounds for these stochastic variants can be driven as we obtain the bounds for the deterministic versions using Theorem 3. Due to space considerations, we skip their proofs and only state the error bounds for these variants using stochastic gradients as corollaries of the deterministic error bound results shown in Theorem 7 and Theorem 8.

Let $\{x_{i}^{0}\}_{i\in\mathcal{N}}$ denote the set of initial primal iterates. The smooth part of the augmented Lagrangian $\phi_{\gamma}$ corresponding to the formulation (31) can be written as

for $k\geq 0$ and the steps of PG-ADMM in (6) take the following form:

For $k\geq 0$, (33b) can be solved in closed form:

Summing (33c) and (33d), and using (34), we get for $k\geq 0$

In this section, we examine the effect of network topology on the convergence rate of DPGA, which is nothing but PG-ADMM customized to the decentralized formulation in (31) as discussed in Section III-A. To obtain simple $\mathcal{O}(1)$ constants in the error bounds, we set $\alpha_{ij}^{0}=\beta_{ij}^{0}=\mathbf{0}$ for all $(i,j)\in\mathcal{E}$.

when the step-size $c_{i}\leq(L_{i}+\gamma_{i}d_{i})^{-1}$ for $i\in\mathcal{N}$, where $\kappa_{i}>0$ denotes a bound on the elements of $\partial\Phi_{i}(x^{*})$, i.e., if $q\in\partial\Phi_{i}(x^{*})$, then $\left\|q\right\|\leq\kappa_{i}$, for each $i\in\mathcal{N}$, and $Q\triangleq\mathop{\bf diag}([\frac{1}{\gamma_{i}}+\frac{1}{\gamma_{j}}]_{(i,j)\in\mathcal{E}})$.

From the optimality conditions for (37), $\theta^{*}$ is an optimal dual solution to (37) if and only if

and $\alpha^{*}_{ij}+\beta^{*}_{ij}=\mathbf{0}$ for all $(i,j)\in\mathcal{E}$. Therefore, given an optimal dual solution to (37), say $\theta^{*}$, one can construct a dual optimal solution $(\alpha^{*},\beta^{*})$ to (31) by simply setting $\alpha^{*}=\theta^{*}$ and $\beta^{*}=-\theta^{*}$. In the rest of the proof, we fix $(\mathbf{x}^{*},\mathbf{y}^{*},\alpha^{*},\beta^{*})$ as a primal-dual optimal solution to (31) such that $x_{i}^{*}=x^{*}$ for $i\in\mathcal{N}$, $y^{*}_{ij}=x^{*}$, $\alpha^{*}_{ij}=\theta^{*}_{ij}$ and $\beta^{*}_{ij}=-\theta^{*}_{ij}$ for all $(i,j)\in\mathcal{E}$, where $\theta^{*}$ is some dual optimal solution to (37).

Hence, setting $\theta=\mathbf{0}$ in (39) leads to

From convexity of $\Phi_{i}$, (38) and the fact that $(M\otimes I_{n})\mathbf{x}^{*}=\mathbf{0}$, it follows that

Adding ${\theta^{*}}^{\top}(M\otimes I_{n})\bar{\mathbf{x}}^{t}$ to both sides, and invoking (39) for $\theta$ such that $\theta_{ij}=2\theta_{ij}^{*}$ for $(i,j)\in\mathcal{E}$, we get

Invoking (39) once again for $\theta=\theta^{*}+(M\otimes I_{n})\bar{\mathbf{x}}^{t}/\left\|(M\otimes I_{n})\bar{\mathbf{x}}^{t}\right\|$ and using (41), we get

where the last inequality follows from $\left\|a+b\right\|_{Q}^{2}\leq 2\left\|a\right\|_{Q}^{2}+2\left\|b\right\|_{Q}^{2}$. Next, by appropriately choosing a dual optimal (37), we bound $\left\|\theta^{*}\right\|_{Q}$, which appears in (42) and (43).

Hence, $\left\|\bar{\theta}\right\|_{Q}^{2}\leq\frac{\sigma_{\max}(Q)}{\sigma_{\min}(\Omega)}\sum_{i\in\mathcal{N}}\kappa_{i}^{2}$. Thus, using this bound within (42) and (43), and combining the resulting inequalities together with (40) and (41) implies the desired bounds. ∎

Note that \gamma^{*}=\frac{2}{\left\|x^{0}-x^{*}\right\|}\sqrt{\Big{(}\sum_{i\in\mathcal{N}}\frac{\kappa_{i}^{2}}{\sigma_{\min}(\Omega)}+1\Big{)}/|\mathcal{E}|} is an optimal choice for constant penalty.

III-B DPGA-W Algorithm for weighted communication networks

where $\Phi_{i}$ is defined in (1). Note that the Laplacian $\Omega$ of the graph $\mathcal{G}$ is also a communication matrix, and can also be used to model unweighted networks. In the rest of this section, assume that (3) has a solution, and (44) satisfies Assumption 3.

The smooth part of the augmented Lagrangian $\phi_{\gamma}$ for the formulation (45) can be written as

and the steps of PG-ADMM in (6) take the following form:

Since $y$-step and $\lambda$-step are the same as those in , the results of this paragraph directly follow from Section III of . Let $\{x_{i}^{0}\}_{i\in\mathcal{N}}$ denote the set of initial primal iterates. For $k\geq 0$, let $p_{i}^{k+1}$ be the optimal Lagrange multiplier corresponding to $\mathbf{y}_{i}\in\mathcal{Y}_{i}$ constraint in (46b); hence, $y_{ij}^{k+1}=W_{ij}x_{j}^{k+1}+\frac{1}{\gamma_{j}}(\lambda_{ij}^{k}-p_{i}^{k+1})$. On the other hand, combining this equality with (46c), we conclude that $\lambda_{ij}^{k+1}=p_{i}^{k+1}$ for all $k\geq 0$. Moreover, since $\mathbf{y}_{i}^{k+1}\in\mathcal{Y}_{i}$, the optimal dual $p_{i}^{k+1}$ can be computed using the recursion: $p_{i}^{k+1}=p_{i}^{k}+(\sum_{j\in\mathcal{N}_{i}\cup\{i\}}\frac{1}{\gamma_{j}})^{-1}\sum_{j\in\mathcal{N}_{i}\cup\{i\}}W_{ij}x_{j}^{k+1}$ for $k\geq 0$. Suppose that we initialize $\lambda_{ij}^{0}=p_{i}^{0}$ for all $j\in\mathcal{N}_{i}\cup\{i\}$ for some given $p_{i}^{0}$ for all $i\in\mathcal{N}$. Finally, by defining $s_{i}^{0}=\mathbf{0}$ and $s_{i}^{k}\triangleq(\sum_{j\in\mathcal{N}_{i}\cup\{i\}}\frac{1}{\gamma_{j}})^{-1}\sum_{j\in\mathcal{N}_{i}\cup\{i\}}W_{ij}x_{j}^{k}$ for $k\geq 1$, and initializing $y_{ij}^{0}\triangleq W_{ij}x_{j}^{0}$ for all $j\in\mathcal{N}_{i}\cup\{i\}$ and $i\in\mathcal{N}$, the computation of $\nabla_{x_{j}}\phi_{\gamma}$ in (46a) can be simplified. Indeed, for any $j\in\mathcal{N}$, $\lambda_{ij}^{k}+\gamma_{j}(W_{ij}x_{j}^{k}-y_{ij}^{k})=2p_{i}^{k}-p_{i}^{k-1}$ for all $i\in\mathcal{N}_{j}\cup\{j\}$; hence,

holds for $k\geq 0$. Note that this is true for $k=0$ because of how we initialize $\lambda^{0}$ and $\mathbf{y}^{0}$. Therefore, the steps in (46a)-(46c) can be simplified as shown in Figure 2 below.

As in DPGA, to be able compute $s_{i}^{k}$ updates DPGA-W requires each node $i\in\mathcal{N}$ to send $\gamma_{i}$ to and receive $\gamma_{j}$ from all its neighbors $j\in\mathcal{N}_{i}$ once at the beginning. Moreover, stepsize $c_{i}$ depends on $\omega_{i}$, which is formed by the weights $W_{ji}$ assigned to $i$ by all its neighbors $j\in\mathcal{N}_{i}$; therefore, assigned weights are exchanged among neighbors once at the beginning as well. Note that while DPGA-W can be applied to more general weighted communication networks, it requires each node to communicate two times with its neighbors per iteration, in contract to one time for DPGA.

In this section, we examine the effect of network topology on the convergence rate of DPGA-W, which is nothing but PG-ADMM customized to the decentralized formulation in (45) as discussed in Section III-B. To obtain simple $\mathcal{O}(1)$ constants in the error bounds, we set $p_{i}^{0}=\mathbf{0}$ for all $i\in\mathcal{N}$.

where $\kappa_{i}>0$ denotes an upper bound on the elements of $\partial\Phi_{i}(x^{*})$, i.e., if $q\in\partial\Phi_{i}(x^{*})$, then $\left\|q\right\|\leq\kappa_{i}$, for each $i\in\mathcal{N}$, and $\tau_{\max}\triangleq\max_{i\in\mathcal{N}}\sum_{j\in\mathcal{N}_{i}}\frac{1}{\gamma_{j}}$.

From the optimality conditions for (47), $\mathbf{p}^{*}$ is an optimal dual solution to (47) if and only if

i.e., $-(W\otimes I_{n})^{\top}\mathbf{p}^{*}\in\partial F(\mathbf{x}^{*})$ such that $x^{*}_{i}=x^{*}$ for $i\in\mathcal{N}$. Moreover, from the first-order optimality conditions for (45), $\lambda^{*}$ is dual optimal to (45) if and only if there exists some $\mathbf{p}=[p_{i}]_{i\in\mathcal{N}}$ such that $\lambda^{*}_{ij}=p_{i}$ for all $j\in\mathcal{N}_{i}\cup\{i\}$ and $i\in\mathcal{N}$, and $\mathbf{0}\in\partial\Phi_{j}(x^{*})+\sum_{i\in\mathcal{N}_{j}\cup\{j\}}W_{ij}\lambda^{*}_{ij}$ for all $j\in\mathcal{N}$. Therefore, given an optimal dual solution to (47), say $\mathbf{p}^{*}$ , one can construct a dual optimal $\lambda^{*}$ to (45) by simply setting $\lambda_{ij}^{*}=p_{i}^{*}$ for all $j\in\mathcal{N}_{i}\cup\{i\}$ and $i\in\mathcal{N}$. In the rest, we fix $(\mathbf{x}^{*},\mathbf{y}^{*},\lambda^{*})$ as a primal-dual optimal solution to (45) such that $x_{i}^{*}=x^{*}$ for $i\in\mathcal{N}$, $y^{*}_{ij}=W_{ij}x^{*}$ and $\lambda^{*}_{ij}=p^{*}_{i}$ for $j\in\mathcal{N}_{i}\cup\{i\}$ and $i\in\mathcal{N}$, where $\mathbf{p}^{*}$ is some dual optimal solution to (47).

where $\tau_{i}\triangleq\sum_{j\in\mathcal{N}_{i}\cup\{i\}}\frac{1}{\gamma_{j}}$ for $i\in\mathcal{N}$, and the above inequality follows from the facts that $\sum_{j\in\mathcal{N}_{i}\cup\{i\}}\bar{y}_{ij}^{t}=\mathbf{0}$ and $c_{i}=(L_{i}+\gamma_{i}\left\|\omega_{i}\right\|^{2}+\vartheta_{i})^{-1}$. Hence, setting $\mathbf{p}=\mathbf{0}$ in (49) leads to

From the convexity of $\Phi_{i}$, (48) and the fact $(W\otimes I_{n})\mathbf{x}^{*}=\mathbf{0}$, it follows that

Adding the last term to both sides, and invoking (49) for $\mathbf{p}$ such that $p_{i}=2p_{i}^{*}$ for $i\in\mathcal{N}$, we get

where $\tau_{\max}\triangleq\max_{i\in\mathcal{N}}\tau_{i}$. Invoking (49) once again for $\mathbf{p}=\mathbf{p}^{*}+(W\otimes I_{n})\bar{\mathbf{x}}^{t}/\left\|(W\otimes I_{n})\bar{\mathbf{x}}^{t}\right\|$ and using (51), we get

where the last inequality follows from $\left\|a+b\right\|^{2}\leq 2\left\|a\right\|^{2}+2\left\|b\right\|^{2}$.

Using (54) within (52) and (53), and combining the resulting inequalities together with (51) and (50) implies the desired bounds. ∎

III-C Stochastic gradient variants of DPGA and DPGA-W

Using Theorem 3, one can provide error bounds for the stochastic gradient variants of DPGA and DPGA-W as corollaries of Theorem 7 and Theorem 8. Both SDPGA and SDPGA-W employ SFO $G_{i}$ defined in Definition 2 for $i\in\mathcal{N}$ instead of accessing to $\nabla f_{i}$. Due to space constraints, we only provide the result for SDPGA, that said the bounds for SDPGA-W immediately follows from the same arguments. In Fig. 1 simply replace $\nabla f_{i}(x_{i}^{k})$ with $G_{i}(x_{i}^{k},\nu_{i}^{k})$ and set the stepsize at the $k$-th iteration as $c_{i}^{k}=(L_{i}+\gamma_{i}d_{i}+1+\sqrt{k})^{-1}$. Then under Assumption 2, slightly modifying the proof of Theorem 7 by invoking the result of Theorem 3 for the case $\sigma>0$, we immediately obtain the bounds for SDPGA in Corollary 9.