An Asynchronous Distributed Proximal Gradient Method for Composite Convex Optimization

Introduction

Let $\mathcal{G}=(\mathcal{N},\mathcal{E})$ denote a connected undirected graph of $N$ computing nodes where nodes $i$ and $j$ can communicate information only if $(i,j)\in\mathcal{E}$. Each node $i\in\mathcal{N}:=\{1,\ldots,N\}$ has a private (local) cost function

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

We propose a distributed augmented Lagrangian algorithm for efficiently computing a solution for the convex problem:

Optimization problems of form (4) model a variety of very important applications, e.g., distributed linear regression (Mateos et al., 2010), distributed control (Necoara & Suykens, 2008), machine learning (McDonald et al., 2010), and estimation using sensor networks (Lesser et al., 2003).

We call a solution $\mathbf{\bar{x}}=(\bar{x}_{i})_{i\in\mathcal{N}}$ $\epsilon$-feasible if the consensus violation \max_{(i,j)\in\mathcal{E}}\big{\{}\|\bar{x}_{i}-\bar{x}_{j}\|_{2}\big{\}}\leq\epsilon and $\epsilon$-optimal if \big{|}\sum_{i\in\mathcal{N}}F_{i}(\bar{x}_{i})-F^{*}\big{|}\leq\epsilon. In this work, we propose a distributed first-order augmented Lagrangian (DFAL) algorithm, establish the following main result for the synchronous case in Section 2.2.3, and extend it to an asynchronous setting in Section 2.2.4.

Given the importance of (4), a number of different distributed optimization algorithms have been proposed to solve (4). Duchi et al. (2012) proposed a dual averaging algorithm to solve (3) in a distributed fashion over $\mathcal{G}$ when each $F_{i}$ is convex. This algorithm computes $\epsilon$-optimal solution in $\mathcal{O}(1/\epsilon^{2})$ iterations; however, they do not provide any guarantees on the consensus violation $\max\{\|\bar{x}_{i}-\bar{x}_{j}\|_{2}:\ (i,j)\in\mathcal{E}\}$. Nedic & Ozdaglar (2009) developed a subgradient method with constant step size $\alpha>0$ for distributed minimization of (3) where the network topology is time-varying. Setting $\alpha=\mathcal{O}(\epsilon)$ in their method guarantees that consensus violation and suboptimality is $\mathcal{O}(\epsilon)$ in $\mathcal{O}(1/\epsilon^{2})$ iterations; however, since the step size is constant none of the errors are not guaranteed to decrease further. Wei and Ozdaglar (2012; 2013), and recently Makhdoumi & Ozdaglar (2014) proposed an alternating direction method of multipliers (ADMM) algorithm that computes an $\epsilon$-optimal and $\epsilon$-feasible solution in $\mathcal{O}(1/\epsilon)$ proximal map evaluations for $F_{i}$. There are several problems where one can compute the proximal map for $\rho_{i}$ efficiently; however, computing the proximal map for $F_{i}=\rho_{i}+\gamma_{i}$ is hard -see Section 3 for an example. One can overcome this limitation of ADMM by locally splitting variables, i.e., setting $F_{i}(x_{i},y_{i}):=\rho_{i}(x_{i})+\gamma_{i}(y_{i})$, and adding a constraint $x_{i}=y_{i}$ in (4). This approach doubles local memory requirement; in addition, in order for ADMM to be efficient, proximal maps for both $\rho_{i}$ and $\gamma_{i}$ must be efficiently computable. When each $F_{i}$ is smooth and has bounded gradients, Jakovetic et al. (2011) developed a fast distributed gradient methods with $\mathcal{O}(1/\sqrt{\epsilon})$ convergence rate. Note that for the quadratic loss, which is one of the most commonly used loss functions, the gradient is not bounded. Chen & Ozdaglar (2012) proposed an inexact proximal-gradient method for distributed minimization of (3) that is able to compute $\epsilon$-feasible and $\epsilon$-optimal solution in $\mathcal{O}(\epsilon^{-1/2})$ iterations which require $\mathcal{O}(\epsilon^{-1})$ communications per node over a time-varying network topology when $F_{i}=\rho+\gamma_{i}$, assuming that the non-smooth term $\rho$ is the same at all nodes, and $\nabla\gamma_{i}$ is bounded for all $i\in\mathcal{N}$. In contrast, DFAL proposed in this paper is able to asynchronously compute an $\epsilon$-optimal $\epsilon$-feasible solution in $\mathcal{O}(\epsilon^{-1})$ communications per node, allowing node specific non-smooth functions $\rho_{i}$, and without assuming bounded $\nabla\gamma_{i}$ for any $i\in\mathcal{N}$.

Methodology

For all $i\in\mathcal{N}$, we assume that $\gamma_{i}\in\Gamma$ and $\rho_{i}\in\mathcal{R}$ with corresponding constants $L_{\gamma_{i}},\underline{\gamma_{i}},B_{i}$ and $\tau_{i}$.

Consider the centralized version (3) where all the functions $F_{i}$ are available at a central node, and all computations are carried out at this node. Suppose $\{\rho_{i}\}_{i\in\mathcal{N}}$ and $\{\gamma_{i}\}_{i\in\mathcal{N}}$ satisfy Assumption 1. Let $\rho(x):=\sum_{i=1}^{N}\rho_{i}(x)$ and $\gamma(x):=\sum_{i=1}^{N}\gamma_{i}(x)$. Lipschitz continuity of each $\nabla\gamma_{i}$ with constant $L_{\gamma_{i}}$ implies that $\nabla\gamma$ is also Lipschitz continuous with constant $L_{\gamma}=\sum_{i=1}^{N}L_{\gamma_{i}}$. When $\textbf{prox}_{{\rho/L_{\gamma}}}$ can be computed efficiently, the accelerated proximal gradient (APG) algorithm proposed in (Beck & Teboulle, 2009; Tseng, 2008) guarantees that

2 DFAL Algorithm for the Decentralized Model

We propose to solve (6) by inexactly solving the following sequence of subproblems in a distributed manner:

for appropriately chosen sequences of penalty parameters $\{\lambda^{(k)}\}$ and dual variables $\{\theta^{(k)}\}$ such that $\lambda^{(k)}\searrow 0$. In particular, given $\{\alpha^{(k)},\xi^{(k)}\}$ satisfying $\alpha^{(k)}\searrow 0$ and $\xi^{(k)}\searrow 0$, the iterate sequence $\{\mathbf{x}^{(k)}\}$ is constructed such that every $\mathbf{x}^{(k)}$ satisfies one of the following conditions:

In Section 2.2.1, we show that DFAL can compute an $\epsilon$-optimal and $\epsilon$-feasible $\mathbf{x}_{\epsilon}$ to (6), i.e., $\|A{\mathbf{x}}_{\epsilon}-b\|_{2}\leq\epsilon$ and $|\bar{F}({\mathbf{x}}_{\epsilon})-F^{*}|\leq\epsilon$, in at most $\mathcal{O}(\log(1/\epsilon))$ iterations.

Next, in Section 2.2.2, we show that computing an $\epsilon$-optimal, $\epsilon$-feasible solution $x_{\epsilon}$ requires at most $\mathcal{O}\left(\frac{\sigma^{3}_{\max}(A)}{\min_{i\in\mathcal{N}}\sigma^{2}_{\min}(A_{i})}\epsilon^{-1}\right)$ floating point operations. Using this result, in Section 2.2.3 we establish that DFAL can compute $x_{\epsilon}$ in a distributed manner within $\mathcal{O}(\epsilon^{-1})$ communication steps, i.e., the Main Result stated in Section 1. Finally, in Section 2.2.4 we show how to modify DFAL for an asynchronous computation setting.

We first show that $\{\mathbf{x}^{(k)}\}$ is a bounded sequence, and then argue that this also implies boundedness of $\{\theta^{(k)}\}$. First, we start with a technical lemma that will be used in establishing the main results of this section.

In Lemma 2 we show that function $f^{(k)}$ defined in (8) satisfies the condition given in Lemma 1.

The function $f^{(k)}$ in (7) satisfies the condition in Lemma 1 with the constants $L_{i}=L^{(k)}_{i}$, where $L^{(k)}_{i}:=\lambda^{(k)}L_{\gamma_{i}}+\sigma_{\max}^{2}(A)$ for all $i\in\mathcal{N}$.

Lemma 1 and Lemma 2 allow us to bound $\|\theta^{(k+1)}\|_{2}$ in terms of $\{\|\nabla_{x_{i}}\gamma(x_{i}^{(k)})\|_{2}\}_{i\in\mathcal{N}}$. We later use this bound in an inductive argument to establish that the sequence $\{\mathbf{x}^{(k)}\}$ is bounded.

Let $\{\mathbf{x}^{(k)}\}$ be the DFAL iterate sequence, i.e., at least one of the conditions in (9) hold for all $k\geq 1$. Define $\Theta_{i}^{(k)}:=\max\left\{\sqrt{2L^{(k)}_{i}\frac{\alpha^{(k)}}{(\lambda^{(k)})^{2}}},~{}\frac{1}{\sqrt{N}}\frac{\xi^{(k)}}{\lambda^{(k)}}\right\}+B_{i}+\|\nabla\gamma_{i}(x^{(k)}_{i})\|_{2}$. Then for all $k\geq 1$, we have

Theorem 1 establishes that the DFAL iterate sequence $\{\mathbf{x}^{(k)}\}$ is bounded whenever $\{\rho_{i},\gamma_{i}\}_{i\in\mathcal{N}}$ satisfy Assumption 1; therefore, the sequence of dual variables $\{\theta^{(k)}\}$ is bounded according to Lemma 3.

Suppose Assumption 1 holds. Then there exist constants $B_{x},\ B_{\theta},\ \bar{\lambda}>0$ such that $\max\{\|\mathbf{x}_{*}^{(k)}\|_{2},\|\mathbf{x}^{(k)}\|_{2}\}\leq B_{x}$ and $\|\theta^{(k)}\|_{2}\leq B_{\theta}$ for all $k\geq 1$, whenever $\lambda^{(1)}$ and $\xi^{(1)}$ are chosen such that $0<\lambda^{(1)}\leq\bar{\lambda}$ and $\frac{\xi^{(1)}}{\lambda^{(1)}}<\bar{\tau}$.

We are now ready to state a key result that will imply the iteration complexity of DFAL.

Suppose Assumption 1 holds and $\lambda^{(1)}$ and $\xi^{(1)}$ are chosen according to Theorem 1. Then the primal-dual iterate sequence $\{\mathbf{x}^{(k)},\theta^{(k)}\}$ generated by DFAL satisfy

$\|A\mathbf{x}^{(k)}-b\|_{2}\leq 2B_{\theta}\lambda^{(k)}$,

$\bar{F}(\mathbf{x}^{(k)})-\bar{F}^{*}\geq-\lambda^{(k)}\frac{\left(\|\theta^{*}\|_{2}+B_{\theta}\right)^{2}}{2}$

$\bar{F}(\mathbf{x}^{(k)})-\bar{F}^{*}\leq\lambda^{(k)}\left(\frac{B_{\theta}^{2}}{2}+\frac{\max\left\{\alpha^{(1)},~{}\xi^{(1)}B_{x}\right\}}{\left(\lambda^{(1)}\right)^{2}}\right)$,

where $\theta^{*}$ denotes any optimal dual solution to (6).

The DFAL iterates $\mathbf{x}^{(k)}$ are $\epsilon$-feasible, i.e., $\|A\mathbf{x}^{(k)}-b\|_{2}\leq\epsilon$, and $\epsilon$-optimal, i.e., $|\bar{F}(\mathbf{x}^{(k)})-\bar{F}^{*}|\leq\epsilon$, for all $k\geq N(\epsilon)$ and $N(\epsilon)=\log_{\frac{1}{c}}(\frac{\bar{C}}{\epsilon})$ for some $\bar{C}>0$.

2.2 Overall computational complexity for the synchronous algorithm

Efficiency of DFAL depends on the complexity of the oracle for Step 1 in Fig. 1. In this section, we construct an oracle MS-APG that computes an $\mathbf{x}^{(k)}$ satisfying (9) within $\mathcal{O}(1/\lambda^{(k)})$ gradient and prox computations. This result together with Theorem 2 guarantees that for any $\epsilon>0$, DFAL can compute an $\epsilon$-optimal and $\epsilon$-feasible iterate within $\mathcal{O}\left(\epsilon^{-1}\right)$ floating point operations. Following lemma gives the iteration complexity of the oracle MS-APG displayed in Fig. 2.

(10) follows from adapting the proof of Theorem 4.4 in Beck & Teboulle (2009) for the case here. ∎

Consider the problem $\Phi^{*}=\min\Phi(\mathbf{y}):=\bar{\rho}(\mathbf{y})+f(\mathbf{y})$ defined in Lemma 4. Note that $\nabla f$ is Lipschitz continuous with constant $L=\max_{i\in\mathcal{N}}L_{i}$. In MS-APG algorithm, the step length $1/L_{i}\geq 1/L$ is different for each $i\in\mathcal{N}$. Instead, if one were to use the APG algorithm (Beck & Teboulle, 2009; Tseng, 2008), then the step length would have been $1/L$ for all $i\in\mathcal{N}$. When $\{L_{i}\}_{i\in\mathcal{N}}$ are close to each other, the performances of MS-APG and APG are on par; however, when $\frac{\max_{i\in\mathcal{N}}L_{i}}{\min_{i\in\mathcal{N}}L_{i}}\gg 1$, APG can only take very tiny steps for all $i\in\mathcal{N}$; hence, MS-APG is likely to converge much faster in practice.

Since the subproblem (7) is in the form given in Lemma 4, the following result immediately follows.

where $\Theta=\frac{\sigma_{\max}(A)}{\min_{i\in\mathcal{N}}\sigma_{\min}(A_{i})}$.

2.3 Synchronous Algorithm for distributed optimization

In this section, we show that the decentralized optimization problem (4) is a special case of (6); therefore, Theorem 3 establishes the Main Result stated in the Introduction. We also show that the steps in DFAL can be further simplified in this context.

where $\otimes$ denotes the Kronecker product. Let $\psi_{\max}:=\psi_{1}\geq\psi_{2}\geq\ldots\geq\psi_{N}$ be the eigenvalues of $\Omega$. Since $\mathcal{G}$ is connected, $\mathop{\bf rank}(\Omega)=N-1$, i.e., $\psi_{N-1}>0$ and $\psi_{N}=0$. From the structure of $\Psi$ it follows that that $\{\psi_{i}\}_{i=1}^{N}$ are also the eigenvalues of $\Psi$, each with algebraic multiplicity $n$. Hence, $\mathop{\bf rank}(C)=n(N-1)$.

We now show that we do not have to compute the SVD of $C$, or $A$, or even the dual multipliers $\theta^{(k)}$ when DFAL is used to solve (4). In DFAL the matrix $A$ is used in Step 1 (i.e. within the oracle MS-APG) to compute $\nabla f^{(k)}$, and in Step 2 to compute $\theta^{(k+1)}$. Since $\theta^{(1)}=\mathbf{0}$, Step 2 in DFAL and (8) imply that $\theta^{(k+1)}=-\sum_{t=1}^{k}\frac{Ax^{(t)}}{\lambda^{(t)}}$, and $\nabla f^{(k)}(\mathbf{x})=\lambda^{(k)}\nabla\bar{\gamma}(\mathbf{x})+A^{\mathsf{T}}(A\mathbf{x}-\lambda^{(k)}\theta^{(k)})=\lambda^{(k)}\nabla\bar{\gamma}(\mathbf{x})+\Psi\left(\mathbf{x}+\lambda^{(k)}\sum_{t=1}^{k-1}\frac{1}{\lambda^{(t)}}\mathbf{x}^{(t)}\right)$. Moreover, from the definition of $\Psi$, it follows that

where $\bar{\mathbf{x}}^{(k)}:=\sum_{t=1}^{k-1}\frac{\lambda^{(k)}}{\lambda^{(t)}}\mathbf{x}^{(t)}$, and $\mathcal{O}_{i}$ denotes the set of nodes adjacent to $i\in\mathcal{N}$. Thus, it follows that Step 1 of MS-APG can be computed in a distributed manner by only communicating with the adjacent nodes without explicitly computing $\theta^{(k)}$ in Step 2 of DFAL.

2.4 Asynchronous implementation

Here we propose an asynchronous version of DFAL. Due to limited space, and for the sake of simplicity of the exposition, we only consider a simple randomized block coordinate descent (RBCD) method, which will lead to an asynchronous implementation of DFAL that can compute an $\epsilon$-optimal and $\epsilon$-feasible solution to (4) with probability $1-p$ within $\mathcal{O}\left(\frac{1}{\epsilon^{2}}\log\left(\frac{1}{p}\right)\right)$ RBCD iterations. In Section 4.9 of the appendix, we discuss how to improve this rate to $\mathcal{O}\left(\frac{1}{\epsilon}\log\left(\frac{1}{p}\right)\right)$ using an accelerated RBCD.

where $N(\epsilon)=\log_{\frac{1}{c}}\left(\frac{\bar{C}}{\epsilon}\right)$ defined in Corollary 1. Since \big{(}1-p\big{)}^{\frac{1}{N(\epsilon)}}\leq 1-\frac{p}{N(\epsilon)} for $p\in(0,1)$, the total number of RBCD iterarions for the $k$-th subproblem is bounded: N^{(k)}\leq\mathcal{O}\big{(}\frac{1}{\alpha^{(k)}}\log\big{(}\frac{N(\epsilon)}{p}\big{)}\big{)}=\mathcal{O}\big{(}\frac{1}{\alpha^{(k)}}\big{(}\log\big{(}\frac{1}{p}\big{)}+\log\log\big{(}\frac{1}{\epsilon}\big{)}\big{)}\big{)}. Hence, Corollary 1 and (11) imply that asynchronous DFAL, i.e., (9)(a) replaced with (12), can compute an $\epsilon$-optimal and $\epsilon$-feasible solution to (4) with probability $1-p$ within $\mathcal{O}\left(\frac{1}{\epsilon^{2}}\log\left(\frac{1}{p}\right)\right)$ RBCD iterations. These results can be extended to the case where each node has different clock rates using (Qu & Richtárik, 2014).

Numerical results

In this section, we compared DFAL with an ADMM method proposed in (Makhdoumi & Ozdaglar, 2014) on the sparse group LASSO problem with Huber loss:

respectively; and $r_{i}^{(k+1)}=r_{i}^{(k)}+(x_{i}^{(k+1)}-y_{i}^{(k+1)})/2$.

2 Implementation details and numerical results

where $\odot$ denotes componentwise multiplication, and $\eta_{g(k)}=-\operatorname*{sgn}\left(\nabla_{x_{g(k)}}f(\bar{x})\right)\odot\min\left\{|\nabla_{x_{g(k)}}f(\bar{x})|,~{}\lambda\beta_{1}\right\}$.

Both DFAL and SADMM call for $\mathbf{prox}_{\rho_{i}}$. In Lemma 7, we show that it can be computed in closed form. On the other hand, when ADMM, and SADMM are implemented on (13), one needs to compute $\mathbf{prox}_{F_{i}}$ and $\mathbf{prox}_{\gamma_{i}}$, respectively; however, these proximal operations do not assume closed form solutions. Therefore, in order to be fair, we computed them using an efficient interior point solver MOSEK (ver. 7.1.0.12).

In Table 2, ’xxx (C)’ stands for “algorithm xxx is used to solve the centralized problem”. Similarly, ’xxx (D)’ for the decentralized one. For the results separated by comma, the left and right ones are for the star tree and clique, resp. Table 2 displays the means over 5 replications for each case. The number of iterations in each case clearly illustrates the topology of the network plays an important role in the convergence speed of DFAL, which coincides to our analysis in Section 2.2.2.

References

Appendix

Let $\mathcal{I}:=\{i\in\mathcal{N}:\ \|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}\leq\lambda B_{i}\}$. For each $i\in\mathcal{N}$, there are two possibilities.

Case 2: Suppose that $i\in\mathcal{I}^{c}:=\mathcal{N}\setminus\mathcal{I}$, i.e., $\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}>\lambda B_{i}$. In this case, $\bar{x}^{*}_{i}\neq\bar{x}_{i}$. From the first-order optimality condition, we have $\nabla_{x_{i}}f(\mathbf{\bar{x}})+L_{i}(\bar{x}^{*}_{i}-\bar{x}_{i})+\lambda B_{i}\frac{\bar{x}^{*}_{i}-\bar{x}_{i}}{\|\bar{x}^{*}_{i}-\bar{x}_{i}\|_{2}}=0$. Let $s_{i}:=\frac{\bar{x}^{*}_{i}-\bar{x}_{i}}{\|\bar{x}^{*}_{i}-\bar{x}_{i}\|_{2}}$ and $t_{i}:=\|\bar{x}^{*}_{i}-\bar{x}_{i}\|_{2}$, then $s_{i}=\frac{-\nabla_{x_{i}}f(\mathbf{\bar{x}})}{L_{i}t_{i}+\lambda B_{i}}$. Since $\|s_{i}\|_{2}=1$, it follows that $t_{i}=\frac{\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}-\lambda B_{i}}{L_{i}}>0$, and $s_{i}=\frac{-\nabla_{x_{i}}f(\mathbf{\bar{x}})}{\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}}$. Hence, $\bar{x}^{*}_{i}=\bar{x}_{i}-\frac{\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}-\lambda B_{i}}{L_{i}}\frac{\nabla_{x_{i}}f(\mathbf{\bar{x}})}{\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}}$, and $h_{i}(\bar{x}^{*}_{i})=-\frac{(\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}-\lambda B_{i})^{2}}{2L_{i}}$.

From the $\alpha$-optimality of $\mathbf{\bar{x}}$, it follows that

which implies that $\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}\leq\sqrt{2L_{i}\alpha}+\lambda B_{i}$ for all $i\in\mathcal{I}$. Moreover, $\|\nabla_{x_{i}}f(\mathbf{\bar{x}})\|_{2}\leq\lambda B_{i}$ for all $i\in\mathcal{I}^{c}$. Hence, the result follows from these two inequalities. ∎

2 Proof of Lemma 2

Let $h^{(k)}(\mathbf{x})=\tfrac{1}{2}\|A\mathbf{x}-b-\lambda^{(k)}\theta^{(k)}\|_{2}^{2}$. It follows that $\nabla h^{(k)}$ is Lipschitz continuous with constant $\sigma_{\max}^{2}(A)$. Since $f^{(k)}=\lambda^{(k)}\bar{\gamma}+h^{(k)}$, the result follows from (15). ∎

3 Proof of Lemma 3

Fix $k\geq 1$. Suppose that $\mathbf{x}^{(k)}$ satisfies (9)(a). Then Lemma 1 implies that for all $i\in\mathcal{N}$

Now, suppose that $\mathbf{x}^{(k)}$ satisfies (9)(b). Then triangular inequality immediately implies that $\|\nabla_{x_{i}}f^{(k)}(\mathbf{x}^{(k)})\|_{2}\leq\xi^{(k)}/\sqrt{N}+\lambda^{(k)}B_{i}$ for all $i\in\mathcal{N}$. Combining the two inequalities, and further using triangular Cauchy-Schwarz inequalities, it follows for all $i\in\mathcal{N}$ that \|A\mathbf{x}^{(k)}-b-\lambda^{(k)}\theta^{(k)}\|_{2}\leq\frac{\max\left\{\sqrt{2L^{(k)}_{i}\alpha_{k}},~{}\xi^{(k)}/\sqrt{N}\right\}+\lambda^{(k)}\big{(}B_{i}+\|\nabla\gamma(x^{(k)}_{i})\|_{2}\big{)}}{{\sigma_{\min}(A_{i})}}. Hence, we conclude by diving the above inequality by $\lambda^{(k)}$ and using the definition of $\theta^{(k+1)}$. ∎

4 Proof of Theorem 1

We prove the theorem using induction. We show that, for an appropriately chosen bound $R$, $\|\mathbf{x}^{(k)}-\mathbf{x}^{*}\|_{2}\leq R$ implies that $\|\mathbf{x}^{(k+1)}-\mathbf{x}^{\ast}\|_{2}\leq R$, for all $k\geq 1$. Fix $k\geq 1$. First, suppose that $\mathbf{x}^{(k+1)}$ satisfies (9)(a), i.e. $P^{(k+1)}(\mathbf{x}^{(k+1)})\leq P^{(k+1)}(\mathbf{x}^{*})+\alpha^{(k+1)}$. By dividing both sides by $\lambda^{(k+1)}$, it follows from Assumption 1, $A\mathbf{x}^{*}=b$, and $f^{(k+1)}(\cdot)\geq 0$ that

Next, suppose $\mathbf{x}^{(k+1)}$ satisfies (9)(b). It follows from convexity of $P^{(k+1)}$ and Cauchy-Schwarz inequality that $P^{(k+1)}(\mathbf{x}^{(k+1)})\leq P^{(k+1)}(\mathbf{x}^{*})+\xi^{(k+1)}\|\mathbf{x}^{(k+1)}-\mathbf{x}^{*}\|_{2}$. Again, dividing both sides by $\lambda^{(k+1)}$, we get

Combining the bounds for both cases, (17) and (18), and using triangular inequality, we have

for all $k\geq 0$. Note that $\{\lambda^{(k)},\alpha^{(k)},\xi^{(k)}\}$ is chosen in DFAL such that $\frac{\alpha^{(k)}}{(\lambda^{(k)})^{2}}=\frac{\alpha^{(1)}}{(\lambda^{(1)})^{2}}$ for all $k>1$, and both $\frac{\xi^{(k)}}{\lambda^{(k)}}\searrow 0$ and $\lambda^{(k)}\searrow 0$ monotonically. Since $\sigma_{\min}(A_{i})\geq 1$ for all $i\in\mathcal{N}$, the inductive assumption $\|\mathbf{x}^{(k)}-\mathbf{x}^{*}\|_{2}\leq R$, (16), and Lemma 3 together imply that

To simplify bounds further, choose $\alpha^{(1)}=\tfrac{1}{4N}\left(\lambda^{(1)}\bar{\tau}\right)^{2}$, and $\xi^{(1)}=\tfrac{1}{2}\lambda^{(1)}\bar{\tau}$ for $\lambda^{(1)}\leq\sigma^{2}_{\max}(A)/\bar{L}$, where $\bar{L}=\max_{i\in\mathcal{N}}\{L_{\gamma_{i}}\}$. Let $\bar{B}:=\max_{i\in\mathcal{N}}B_{i}$ and $\bar{G}:=\max\{\|\nabla\gamma_{i}(x_{i}^{*})\|_{2}:\ i\in\mathcal{N}\}$. Together with (19), (20) and $\sigma_{\max}(A)\geq 1$, this choice of parameters implies that

Define $\beta_{1}:=\frac{2}{\bar{\tau}}\left(\bar{F}^{*}+\bar{\tau}\|\mathbf{x}^{*}\|_{2}\right)$, $\beta_{2}:=\frac{\bar{\tau}\sigma_{\max}(A)/\sqrt{N}+\bar{B}+\bar{G}}{\sqrt{\bar{\tau}}}$, $\beta_{3}:=\frac{\bar{L}}{\sqrt{\bar{\tau}}}$, and $\beta_{4}:=\frac{\bar{\tau}}{4N}$. Then we have that \|\mathbf{x}^{(k+1)}-\mathbf{x}^{*}\|_{2}\leq\beta_{1}+\lambda^{(1)}\left[\Big{(}\beta_{2}+\beta_{3}R\Big{)}^{2}+\beta_{4}\right].

Note that we are free to choose any $\lambda^{(1)}>0$ satisfying $\lambda^{(1)}\leq\sigma^{2}_{\max}(A)/\bar{L}$. Our objective is to show that by appropriately choosing $\lambda^{(1)}$, we can guarantee that \beta_{1}+\lambda^{(1)}\left[\big{(}\beta_{2}+\beta_{3}R\big{)}^{2}+\beta_{4}\right]\leq R, which would then complete the inductive proof. This is indeed true if the above quadratic inequality in $R$, has a solution, or equivalently if the discriminant

is non-negative. Note that $\Delta$ is continuous in $\lambda^{(1)}$, and $\lim_{\lambda^{(1)}\rightarrow 0}\Delta=1$. Thus, for all sufficiently small $\lambda^{(1)}>0$, we have $\Delta\geq 0$. Hence, we can set $R=\frac{1-2\lambda^{(1)}\beta_{2}\beta_{3}-\sqrt{\Delta}}{2\lambda^{(1)}{\beta_{3}}^{2}}$ for some $\lambda^{(1)}>0$ such that $\Delta\geq 0$, and this will imply that $\|\mathbf{x}^{(k+1)}-\mathbf{x}^{*}\|_{2}\leq R$ whenever $\|\mathbf{x}^{(k)}-\mathbf{x}^{*}\|_{2}\leq R$ for all $k\geq 1$.

The induction will be complete if we can show that $\|\mathbf{x}^{(1)}-\mathbf{x}^{*}\|_{2}\leq R$. Note that in DFAL we set $\theta^{(1)}=\mathbf{0}$. Hence, for $k=0$, (19) implies that $\|\mathbf{x}^{(1)}-\mathbf{x}^{*}\|_{2}\leq\beta_{1}+\lambda^{(1)}\beta_{4}$. Hence, our choice of $R$ guarantees that $\|\mathbf{x}^{(1)}-\mathbf{x}^{*}\|_{2}\leq R$. This completes the induction.

Following the same arguments leading to (19), it can also be shown that for all $k\geq 0$

Therefore, we can conclude that $\|\mathbf{x}_{*}^{(k)}-\mathbf{x}^{*}\|\leq R$ for all $k\geq 1$ holds for the same $R$ we selected above.

Note that $\Delta$ is a concave quadratic of $\lambda^{(1)}$ such that $\Delta=1$ when $\lambda^{(1)}=0$; hence, one of its roots is positive and the other one is negative. Moreover, $R\leq\frac{1}{2\lambda^{(1)}{\beta_{3}}^{2}}-\frac{\beta_{2}}{\beta_{3}}$ and the bound on $R$ is decreasing in $\lambda^{(1)}>0$. Hence, in order to get a smaller bound on $R$, we will choose $\lambda^{(1)}$ as the positive root of $\Delta$. In particular, we set $\lambda^{(1)}=\frac{\sqrt{\left(\beta_{2}+\beta_{3}\beta_{1}\right)^{2}+\beta_{4}}-\left(\beta_{2}+\beta_{3}\beta_{1}\right)}{2\beta_{3}\beta_{4}}$. ∎

5 Proof of Theorem 2

The proof directly follows from Theorem 3.3 in (Aybat & Iyengar, 2012). For the sake of completeness, we also provide the proof here. Let $\mathbf{x}^{*}$ denote an optimal solution to (6).

Note that (a) follows immediately from Cauchy-Schwarz and the definition of $\theta^{(k+1)}$.

First, we prove the second inequality in (b). Suppose that $\mathbf{x}^{(k)}$ satisfies (9)(a), which implies that $\bar{F}(\mathbf{x}^{(k)})+\tfrac{\lambda^{(k)}}{2}\|\theta^{(k+1)}\|_{2}^{2}\leq\bar{F}(\mathbf{x}^{*})+\tfrac{\lambda^{(k)}}{2}\|\theta^{(k)}\|_{2}^{2}+\tfrac{\alpha^{(k)}}{\lambda^{(k)}}$. Now, suppose that $\mathbf{x}^{(k)}$ satisfies (9)(b). From the convexity of $P^{(k)}$ and Cauchy-Schwarz, it follows that $P^{(k)}(\mathbf{x}^{(k)})\leq P^{(k)}(\mathbf{x}^{*})+\xi^{(k)}\|\mathbf{x}^{(k)}-\mathbf{x}^{*}\|_{2}$. Hence, dividing it by $\lambda^{(k)}$, we have $\bar{F}(\mathbf{x}^{(k)})+\tfrac{\lambda^{(k)}}{2}\|\theta^{(k+1)}\|_{2}^{2}\leq\bar{F}(\mathbf{x}^{*})+\tfrac{\lambda^{(k)}}{2}\|\theta^{(k)}\|_{2}^{2}+\tfrac{\xi^{(k)}}{\lambda^{(k)}}$. Therefore, for all $k\geq 1$, $\mathbf{x}^{(k)}$ satisfies the second inequality in (b) since it also satisfies

Now, in order to prove the first inequality in (b), we will exploit the primal-dual relations of the following two pairs of problems:

where $b_{k}:=b+\lambda^{(k)}\theta^{(k)}$, $h(\theta):=\|\theta-\theta^{(k)}\|_{2}^{2}-\|\theta^{(k)}\|_{2}^{2}$, and $\bar{F}^{*}$ denotes the convex conjugate of $\bar{F}$. Note that problem $(\mathcal{P}_{k})$ is nothing but the subproblem in (7). Therefore, from weak-duality between $(\mathcal{P}_{k})$ and $(\mathcal{D}_{k})$, it follows that

Note that from strong duality between $(\mathcal{P})$ and $(\mathcal{D})$, it follows that $\bar{F}^{*}=\bar{F}(\mathbf{x}^{*})=b^{\mathsf{T}}\theta^{*}-\bar{F}^{*}(A^{\mathsf{T}}\theta^{*})$. Therefore, dividing the above inequality by $\lambda^{(k)}$, we obtain

6 Proof of Theorem 3

We assume that $\sigma_{\max}(A)\geq\sqrt{\max_{i\in\mathcal{N}}d_{i}+1}$, and $\sigma_{\min}(A_{i})=\sqrt{d_{i}}\geq 1$ for all $i\in\mathcal{N}$, where $d_{i}$ denotes the degree of $i\in\mathcal{N}$. As discussed in the proof of Theorem 1, this is a valid assumption for distributed optimization problem in (4). Let $\theta^{*}$ denote an optimal dual solution to (6). Note that from the first-order optimality conditions for (6), we have $\mathbf{0}\in\nabla\gamma_{i}(x^{*}_{i})+A_{i}^{\mathsf{T}}\theta^{*}+\partial\rho_{i}(x_{i})|_{x_{i}=x^{*}_{i}}$; hence, $\|A_{i}^{\mathsf{T}}\theta^{*}\|_{2}\leq B_{i}+G_{i}$. Therefore, $\|\theta^{*}\|_{2}\leq\min_{i\in\mathcal{N}}\frac{B_{i}+G_{i}}{\sigma_{\min}(A_{i})}$.

Given $0<\lambda^{(1)}\leq\sigma^{2}_{\max}(A)/\bar{L}$, choose $\alpha^{(1)},\xi^{(1)}>0$ such that $\alpha^{(1)}=\tfrac{1}{4N}\left(\lambda^{(1)}\bar{\tau}\right)^{2}$, and $\xi^{(1)}=\tfrac{1}{2}\lambda^{(1)}\bar{\tau}$. Then Lemma 3 and $\sigma_{\max}(A)\geq 1$ together imply that for all $k\geq 1$

Hence, note that $\|\theta^{*}\|_{2}\leq B_{\theta}$.

To simplify notation, suppose that $\lambda^{(1)}=\min\left\{1,\sigma^{2}_{\max}(A)/\bar{L}\right\}=1$. (19) implies that for all $k\geq 1$

Note that (22) implies that $\frac{\xi^{(1)}}{(\lambda^{(1)})^{2}}B_{x}=\frac{1}{\lambda^{(1)}}\frac{\bar{\tau}}{2}B_{x}\geq\frac{1}{2}B^{2}_{\theta}+\frac{\bar{\tau}^{2}}{8N}\geq\frac{5}{8N}\bar{\tau}^{2}\geq\frac{\alpha^{(1)}}{(\lambda^{(1)})^{2}}$, where we used the fact $B_{\theta}\geq\frac{\sigma_{\max}(A)}{\max_{i\in\mathcal{N}}\{\sigma_{\min}(A_{i})\}}~{}\frac{\bar{\tau}}{\sqrt{N}}\geq\frac{\bar{\tau}}{\sqrt{N}}$. Note that the last inequality follows from our assumption on $A$ stated at the beginning of the proof, i.e. $\sigma_{\max}(A)\geq\sqrt{\max_{i\in\mathcal{N}}d_{i}+1}$ and $\sigma_{\min}(A_{i})=d_{i}$ for all $i\in\mathcal{N}$. Hence, Theorem 2, $\lambda^{(1)}=1$, and $\|\theta^{*}\|_{2}\leq B_{\theta}$ imply that

Since $\alpha^{(1)}=\tfrac{1}{4N}\left(\lambda^{(1)}\bar{\tau}\right)^{2}$, we have $\sqrt{\alpha^{(k)}}=\frac{\bar{\tau}}{\sqrt{4N}}c^{k}$. Hence, Lemma 5 implies that

Hence, (23) and (25) imply that the total number of MS-APG iterations to compute an $\epsilon$-feasible solution can be bounded above:

Similarly, (24) and (25) imply that the total number of MS-APG iterations to compute an $\epsilon$-optimal solution can be bounded above:

7 Proof of Lemma 6

where $\prod$ denotes the Cartesian product. Since the groups $\{g(k)\}_{k=1}^{K}$ are not overlapping with each other, the minimization problem is separable in groups. Hence, for all $k\in[1,K]$, we have $\nu^{*}_{g(k)}=\pi^{*}_{g(k)}+\omega^{*}_{g(k)}+\nabla_{x_{g(k)}}f(\bar{x})$ such that

Hence, $\|\pi^{*}_{g(k)}+\omega^{*}_{g(k)}+\nabla_{x_{g(k)}}f(\bar{x})\|_{2}=\max\{0,~{}\|\pi^{*}_{g(k)}+\nabla_{x_{g(k)}}f(\bar{x})\|_{2}-\lambda\beta_{2}\}$. Therefore,

Now, suppose that $\bar{x}_{g(k)}\neq\mathbf{0}$. This implies that $\partial\|\bar{x}_{g(k)}\|_{2}=\{\bar{x}_{g(k)}/\|\bar{x}_{g(k)}\|_{2}\}$. Hence, when $\bar{x}_{g(k)}\neq\mathbf{0}$, we have $\omega^{*}_{g(k)}=\lambda\beta_{2}\bar{x}_{g(k)}/\|\bar{x}_{g(k)}\|_{2}$, and the structure of $\partial\|\cdot\|_{1}$ implies that $\pi^{*}_{j}=\lambda\beta_{1}\operatorname*{sgn}\left(\bar{x}_{j}\right)$ for all $j\in g(k)$ such that $|\bar{x}_{j}|>0$; and it follows from (28) that for all $j\in g(k)$ such that $\bar{x}_{j}=0$, we have

8 Proof of Lemma 7

Let $(u_{1}^{*},u_{2}^{*})$ be the optimal solution of (32). Since $x^{p}_{g(k)}$ is the optimal solution to (30), it follows from (31) that

Note that (32) can be equivalently written as $\min\{\|u_{1}+u_{2}-\frac{1}{t}\bar{x}_{g(k)}\|_{2}^{2}:\ \|u_{1}\|_{\infty}\leq\beta_{1},\|u_{2}\|_{2}\leq\beta_{2}\}$. Minimizing over $u_{2}$, we have

Clearly, $u_{1}^{*}=\mathop{\rm argmin}_{\|u_{1}\|_{\infty}\leq\beta_{1}}\|(u_{1}-\frac{1}{t}\bar{x}_{g(k)})\|_{2}=\operatorname*{sgn}(\bar{x}_{g(k)})\min\left\{\frac{1}{t}|\bar{x}_{g(k)}|,\beta_{1}\right\}$. The final result follows from combining (33) and (34). ∎

9 Improved rate for asynchronous DFAL

and $\mathcal{Y}^{*}$ denotes the set of optimal solutions.

In the following result, we establish that the bound (36) can be exploited for designing an accelerated version of asynchronous DFAL.

Fix $\epsilon>0$ and $p\in(0,1)$. Consider a asynchronous variant of DFAL where (9)(a) in Figure 1 is replaced by

where $N(\epsilon)=\log_{\frac{1}{c}}\left(\frac{\bar{C}}{\epsilon}\right)$ is defined in Corollary 1. Then $\{x_{i}^{\left(N(\epsilon)\right)}\}_{i\in\mathcal{N}}$, satisfies

and $\mathcal{O}\left(\frac{1}{\epsilon}\log\left(\frac{1}{p}\right)\right)$ ARBCD iterations are required to compute $\{x_{i}^{\left(N(\epsilon)\right)}\}_{i\in\mathcal{N}}$.

Clearly, for all random sequences $\{\mathbf{x}^{(k)}\}_{k=1}^{N(\epsilon)}$ satisfying random event $\Delta$, Corollary 1 implies that \big{|}\sum_{i\in\mathcal{N}}F_{i}\left(x^{\left(N(\epsilon)\right)}_{i}\right)-F^{*}\big{|}\leq\epsilon and \max_{(i,j)\in\mathcal{E}}\big{\{}\|x^{\left(N(\epsilon)\right)}_{i}-x^{\left(N(\epsilon)\right)}_{j}\|_{2}\big{\}}\leq\epsilon. Hence, we have

In the rest, we bound the total number of ARBCD iterations required by asynchronous variant of DFAL to compute $\mathbf{x}^{(N(\epsilon))}$. Note that $(1-p)^{\frac{1}{N(\epsilon)}}$ is a concave function for $p\in(0,1)$, and we have $(1-p)^{\frac{1}{N(\epsilon)}}\leq 1-\frac{p}{N(\epsilon)}$. Therefore, Lemma 8 and the discussion after Lemma 8 together imply that the number of ARBCD iterations, $N^{(k)}$, to compute $\mathbf{x}^{(k)}$ satisfying either (39) or (9)(b) is bounded above for $1\leq k\leq N(\epsilon)$ as follows

Convexity of $\{\rho_{i}\}_{i\in\mathcal{N}}$, and Lemma 2 imply that

Since $N(\epsilon)=\log_{\frac{1}{c}}(\bar{C}/\epsilon)$, and $\sum_{k=1}^{N(\epsilon)}c^{-k}=\frac{\left(\frac{1}{c}\right)^{N(\epsilon)}-1}{1-c}=\bar{C}\epsilon^{-1}/(1-c)$. Hence, we can conclude that $\sum_{k=1}^{N(\epsilon)}N^{(k)}=\mathcal{O}\left(\frac{1}{\epsilon}\left(\log\left(\frac{1}{p}\right)+\log\log\left(\frac{1}{\epsilon}\right)\right)\right)$