DQM: Decentralized Quadratically Approximated Alternating Direction Method of Multipliers

I Introduction

Problems of this form arise in, e.g., decentralized control , wireless communication , sensor networks , and large scale machine learning . In this paper we assume that the local costs $f_{i}$ are twice differentiable and strongly convex.

There are different algorithms to solve (1) in a decentralized manner which can be divided into two major categories. The ones that operate in the primal domain and the ones that operate in the dual domain. Among primal domain algorithms, decentralized (sub)gradient descent (DGD) methods are well studied . They can be interpreted as either a mix of local gradient descent steps with successive averaging or as a penalized version of (1) with a penalty term that encourages agreement between adjacent nodes. This latter interpretation has been exploited to develop the network Newton (NN) methods that attempt to approximate the Newton step of this penalized objective in a distributed manner . The methods that operate in the dual domain consider a constraint that enforces equality between nodes’ variables. They then ascend on the dual function to find optimal Lagrange multipliers with the solution of (1) obtained as a byproduct . Among dual descent methods, decentralized implementation of the alternating directions method of multipliers (ADMM), known as DADMM, is proven to be very efficient with respect to convergence time .

If a first order approximation of the objective is useful, a second order approximation should decrease convergence times further. The decentralized quadratically approximated ADMM (DQM) algorithm that we propose here minimizes a quadratic approximation of the Lagrangian minimization of each ADMM step. This quadratic approximation requires computation of local Hessians but results in an algorithm with convergence properties that are: (i) better than the convergence properties of DLM; (ii) asymptotically identical to the convergence behavior of DADMM. The technical contribution of this paper is to prove that (i) and (ii) are true from both analytical and practical perspectives.

We begin the paper by discussing solution of (1) with DADMM and its linearized version DLM (Section II). Both of these algorithms perform updates on dual and primal auxiliary variables that are identical and computationally simple. They differ in the manner in which principal primary variables are updated. DADMM solves a convex optimization problem and DLM solves a regularized linear approximation. We follow with an explanation of DQM that differs from DADMM and DLM in that it minimizes a quadratic approximation of the convex problem that DADMM solves exactly and DLM approximates linearly (Section III). We also explain how DQM can be implemented in a distributed manner (Proposition 1 and Algorithm 1). Convergence properties of DQM are then analyzed (Section IV) where linear convergence is established (Theorem 1 and Corollary 1). Key in the analysis is the error incurred when approximating the exact minimization of DADMM with the quadratic approximation of DQM. This error is shown to decrease as iterations progress (Proposition 2) faster than the rate that the error of DLM approaches zero (Proposition 3). This results in DQM having a guaranteed convergence constant strictly smaller than the DLM constant that approaches the guaranteed constant of DADMM for large iteration index (Section IV-A). We corroborate analytical results with numerical evaluations in a logistic regression problem (Section V). We show that DQM does outperform DLM and show that convergence paths of DQM and DADMM are almost identical (Section V-A). Overall computational cost of DQM is shown to be smaller, as expected.

II Distributed Alternating Directions Method of Multipliers

Then, the augmented Lagrangian is minimized with respect to the auxiliary variable ${\mathbf{z}}$ using the updated variable ${\mathbf{x}}_{k+1}$ to obtain

After updating the variables ${\mathbf{x}}$ and ${\mathbf{z}}$, the Lagrange multiplier $\boldsymbol{\lambda}_{k}$ is updated through the dual ascent iteration

The DADMM algorithm is obtained by observing that the structure of the matrices ${\mathbf{A}}$ and ${\mathbf{B}}$ is such that (6)-(8) can be implemented in a distributed manner .

The updates for the auxiliary variable ${\mathbf{z}}$ and the Lagrange multiplier $\boldsymbol{\lambda}$ are not costly in terms of computation time. However, updating the primal variable ${\mathbf{x}}$ can be expensive as it entails the solution of an optimization problem [cf. (6)]. The DLM algorithm avoids this cost with an inexact update of the primal variable iterate ${\mathbf{x}}_{k+1}$. This inexact update relies on approximating the aggregate function value $f({\mathbf{x}}_{k+1})$ in (6) through a regularized linearization of the aggregate function $f$ in a neighborhood of the current variable ${\mathbf{x}}_{k}$. This regularized approximation takes the form $f({\mathbf{x}})\approx f({\mathbf{x}}_{k})+\nabla f({\mathbf{x}}_{k})^{T}({\mathbf{x}}-{\mathbf{x}}_{k})+(\rho/2)\|{\mathbf{x}}-{\mathbf{x}}_{k}\|^{2}$ for a given positive constant $\rho>0$. Consequently, the update formula for the primal variable ${\mathbf{x}}$ in DLM replaces the DADMM exact minimization in (6) by the minimization of the quadratic form

The first order optimality condition for (II) implies that the updated variable ${\mathbf{x}}_{k+1}$ satisfies

According to (10), the updated variable ${\mathbf{x}}_{k+1}$ can be computed by inverting the positive definite matrix $\rho{\mathbf{I}}+c{\mathbf{A}}^{T}{\mathbf{A}}$. This update can also be implemented in a distributed manner.

The sequence of variables ${\mathbf{x}}_{k}$ generated by DLM converges linearly to the optimal argument ${\mathbf{x}}^{*}$ . Although this is the same rate of DADMM, linear convergence constant of DLM is smaller than the one for DADMM (see Section IV-A), and can be much smaller depending on the condition number of the local functions $f_{i}$ (see Section V-A). To close the gap between these constants we can use a second order approximation of (6). This is the idea of DQM that we introduce in the following section.

III DQM: Decentralized Quadratically Approximated ADMM

DQM uses a local quadratic approximation of the primal function $f({\mathbf{x}})$ around the current iterate ${\mathbf{x}}_{k}$. If we let ${\mathbf{H}}_{k}:=\nabla^{2}f({\mathbf{x}}_{k})$ denote the primal function Hessian evaluated at ${\mathbf{x}}_{k}$ the quadratic approximation of $f$ at ${\mathbf{x}}_{k}$ is $f({\mathbf{x}})\approx f({\mathbf{x}}_{k})+\nabla f({\mathbf{x}}_{k})^{T}({\mathbf{x}}-{\mathbf{x}}_{k})+(1/2)({\mathbf{x}}-{\mathbf{x}}_{k})^{T}{\mathbf{H}}_{k}({\mathbf{x}}-{\mathbf{x}}_{k})$. Using this approximation in (6) yields the DQM update that we therefore define as

Comparison of (II) and (11) shows that in DLM the quadratic term $(\rho/2)\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|^{2}$ is added to the first-order approximation of the primal objective function, while in DQM the second order approximation of the primal objective function is used to reach a more accurate approximation for $f({\mathbf{x}})$. Since (11) is a quadratic program, the first order optimality condition yields a system of linear equations that can be solved to find ${\mathbf{x}}_{k+1}$,

This update can be solved by inverting the matrix ${\mathbf{H}}_{k}+c{\mathbf{A}}^{T}{\mathbf{A}}$ which is invertible if, as we are assuming, $f({\mathbf{x}})$ is strongly convex.

The DADMM updates in (7) and (8) are used verbatim in DQM, which is therefore defined by recursive application of (12), (7), and (8). It is customary to consider the first order optimality conditions of (7) and to reorder terms in (8) to rewrite the respective updates as

DQM is then equivalently defined by recursive solution of the system of linear equations in (12) and (III). This system, as is the case of DADMM and DLM, can be reworked into a simpler form that reduces communication cost. To derive this simpler form we assume a specific structure for the initial vectors $\boldsymbol{\lambda}_{0}=[\boldsymbol{\alpha}_{0};\boldsymbol{\beta}_{0}]$, ${\mathbf{x}}_{0}$, and ${\mathbf{z}}_{0}$ as introduced in the following assumption.

Define the oriented incidence matrix as ${\mathbf{E}}_{o}:={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$ and the unoriented incidence matrix as ${\mathbf{E}}_{u}:={\mathbf{A}}_{s}+{\mathbf{A}}_{d}$. The initial Lagrange multipliers $\boldsymbol{\alpha}_{0}$ and $\boldsymbol{\beta}_{0}$, and the initial variables ${\mathbf{x}}_{0}$ and ${\mathbf{z}}_{0}$ are chosen such that:

The multipliers are opposites of each other, $\boldsymbol{\alpha}_{0}=-\boldsymbol{\beta}_{0}$.

The initial primal variables satisfy ${\mathbf{E}}_{u}{\mathbf{x}}_{0}=2{\mathbf{z}}_{0}$.

The initial multiplier $\boldsymbol{\alpha}_{0}$ lies in the column space of ${\mathbf{E}}_{o}$.

Assumption 1 is minimally restrictive. The only non-elementary condition is (c) but that can be satisfied by $\boldsymbol{\alpha}_{0}={\mathbf{0}}$. Nulling all other variables, i.e., making $\boldsymbol{\beta}_{0}={\mathbf{0}}$, ${\mathbf{x}}_{0}={\mathbf{0}}$, and ${\mathbf{z}}_{0}={\mathbf{0}}$ is a trivial choice to comply with conditions (a) and (b) as well. An important consequence of the initialization choice in (1) is that if the conditions in Assumption 1 are true at time $k=0$ they stay true for all subsequent iterations $k>0$ as we state next.

Consider the DQM algorithm as defined by (12)-(III). If Assumption 1 holds, then for all $k\geq 0$ the Lagrange multipliers $\boldsymbol{\alpha}_{k}$ and $\boldsymbol{\beta}_{k}$, and the variables ${\mathbf{x}}_{k}$ and ${\mathbf{z}}_{k}$ satisfy:

The multipliers are opposites of each other, $\boldsymbol{\alpha}_{k}=-\boldsymbol{\beta}_{k}$.

The primal variables satisfy ${\mathbf{E}}_{u}{\mathbf{x}}_{k}=2{\mathbf{z}}_{k}$.

The multiplier $\boldsymbol{\alpha}_{k}$ lies in the column space of ${\mathbf{E}}_{o}$.

The validity of (c) in Lemma 1 is important for the convergence analysis of Section IV. The validity of (a) and (b) means that maintaining multipliers $\boldsymbol{\alpha}_{k}$ and $\boldsymbol{\beta}_{k}$ is redundant because they are opposites and that maintaining variables ${\mathbf{z}}_{k}$ is also redundant because they can be computed as ${\mathbf{z}}_{k}={\mathbf{E}}_{u}{\mathbf{x}}_{k}/2$. It is then possible to replace (12)-(III) by a simpler system of linear equations as we explain in the following proposition.

Consider the DQM algorithm as defined by (12)-(III) and define the sequence $\boldsymbol{\phi}_{k}:={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k}$. Further define the unoriented Laplacian as ${\mathbf{L}}_{u}:=(1/2){\mathbf{E}}_{u}^{T}{\mathbf{E}}_{u}$, the oriented Laplacian as ${\mathbf{L}}_{o}=(1/2){\mathbf{E}}_{o}^{T}{\mathbf{E}}_{o}$, and the degree matrix as ${\mathbf{D}}:=({\mathbf{L}}_{u}+{\mathbf{L}}_{o})/2$. If Assumption 1 holds true, the DQM iterates ${\mathbf{x}}_{k}$ can be generated as

Proposition 1 states that by introducing the sequence of variables $\boldsymbol{\phi}_{k}$, the DQM primal iterates ${\mathbf{x}}_{k}$ can be computed through the recursive expressions in (1). These recursions are simpler than (12)-(III) because they eliminate the auxiliary variables ${\mathbf{z}}_{k}$ and reduce the dimensionality of $\boldsymbol{\lambda}_{k}$ – twice the number of edges – to that of $\boldsymbol{\phi}_{k}$ – the number of nodes. Further observe that if (1) is used for implementation we don’t have to make sure that the conditions of Assumption 1 are satisfied. We just need to pick $\boldsymbol{\phi}_{0}:={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{0}$ for some $\boldsymbol{\alpha}_{0}$ in the column space of ${\mathbf{E}}_{0}$ – which is not difficult, we can use, e.g., $\boldsymbol{\phi}_{0}={\mathbf{0}}$. The role of Assumption 1 is to state conditions for which the expressions in (12)-(III) are an equivalent representation of (1) that we use for convergence analyses.

The structure of the primal objective function Hessian ${\mathbf{H}}_{k}$, the degree matrix ${\mathbf{D}}$, and the oriented and unoriented Laplacians ${\mathbf{L}}_{o}$ and ${\mathbf{L}}_{u}$ make distributed implementation of (1) possible. Indeed, the matrix $2c{\mathbf{D}}+{\mathbf{H}}_{k}$ is block diagonal and its $i$-th diagonal block is given by $2cd_{i}{\mathbf{I}}+\nabla^{2}f_{i}({\mathbf{x}}_{i})$ which is locally available for node $i$. Likewise, the inverse matrix $(2c{\mathbf{D}}+{\mathbf{H}}_{k})^{-1}$ is block diagonal and locally computable since the $i$-th diagonal block is $(2cd_{i}{\mathbf{I}}+\nabla^{2}f_{i}({\mathbf{x}}_{i}))^{-1}$. Computations of the products ${\mathbf{L}}_{u}{\mathbf{x}}_{k}$ and ${\mathbf{L}}_{o}{\mathbf{x}}_{k+1}$ can be implemented in a decentralized manner as well, since the Laplacian matrices ${\mathbf{L}}_{u}$ and ${\mathbf{L}}_{o}$ are block neighbor sparse in the sense that the ${(i,j)}$-th block is not null if and only if nodes $i$ and $j$ are neighbors or $j=i$. Therefore, nodes can compute their local parts for the products ${\mathbf{L}}_{u}{\mathbf{x}}_{k}$ and ${\mathbf{L}}_{o}{\mathbf{x}}_{k+1}$ by exchanging information with their neighbors. By defining components of the vector $\boldsymbol{\phi}_{k}$ as $\boldsymbol{\phi}_{k}:=[\boldsymbol{\phi}_{1,k},\dots,\boldsymbol{\phi}_{n,k}]$, the update formula in (1) for the individual agents can then be written block-wise as

where ${\mathbf{x}}_{i,k}$ corresponds to the iterate of node $i$ at step $k$. Notice that the defintion ${\mathbf{L}}_{u}:=(1/2){\mathbf{E}}_{u}^{T}{\mathbf{E}}_{u}=(1/2)({\mathbf{A}}_{s}+{\mathbf{A}}_{d})^{T}({\mathbf{A}}_{s}+{\mathbf{A}}_{d})$ is used to simplify the $i$-th component of $c{\mathbf{L}}_{u}{\mathbf{x}}_{k}$ as $c\sum_{j\in{\mathcal{N}}_{i}}({\mathbf{x}}_{i,k}+{\mathbf{x}}_{j,k})$ which is equivalent to $cd_{i}{\mathbf{x}}_{i,k}+c\sum_{j\in{\mathcal{N}}_{i}}{\mathbf{x}}_{j,k}$. Further, using the definition ${\mathbf{L}}_{o}=(1/2){\mathbf{E}}_{o}^{T}{\mathbf{E}}_{o}=(1/2)({\mathbf{A}}_{s}-{\mathbf{A}}_{d})^{T}({\mathbf{A}}_{s}-{\mathbf{A}}_{d})$, the $i$-th component of the product $c{\mathbf{L}}_{o}{\mathbf{x}}_{k+1}$ in (16) can be simplified as $c\sum_{j\in{\mathcal{N}}_{i}}({\mathbf{x}}_{i,k}-{\mathbf{x}}_{j,k})$. Therefore, the second update formula in (1) can be locally implemented at each node $i$ as

DADMM, DQM, and DLM occupy different points in a tradeoff curve of computational cost per iteration and number of iterations needed to achieve convergence. The computational cost of each DADMM iteration is large in general because it requires solution of the optimization problem in (6). The cost of DLM iterations is minimal because the solution of (10) can be reduced to the inversion of a block diagonal matrix; see . The cost of DQM iterations is larger than the cost of DLM iterations because they require evaluation of local Hessians as well as inversion of the matrices $2cd_{i}{\mathbf{I}}+\nabla^{2}f_{i}({\mathbf{x}}_{i,k})$ to implement (III). But the cost is smaller than the cost of DADMM iterations except in cases in which solving (6) is easy. In terms of the number of iterations required until convergence, DADMM requires the least and DLM the most. The foremost technical conclusions of the convergence analysis presented in the following section are: (i) convergence of DQM is strictly faster than convergence of DLM; (ii) asymptotically in the number of iterations, the per iteration improvements of DADMM and DQM are identical. It follows from these observations that DQM achieves target optimality in a number of iterations similar to DADMM but with iterations that are computationally cheaper.

IV Convergence Analysis

The network is such that any singular value of the unoriented incidence matrix ${\mathbf{E}}_{u}$, defined as $\sigma({\mathbf{E}}_{u})$, satisfies $0<\gamma_{u}\leq\sigma({\mathbf{E}}_{u})\leq\Gamma_{u}$ where $\gamma_{u}$ and $\Gamma_{u}$ are constants; the smallest non-zero singular value of the oriented incidence matrix ${\mathbf{E}}_{o}$ is $\gamma_{o}>0$.

Assumption 4 also implies an analogous condition for the aggregate function Hessian ${\mathbf{H}}({\mathbf{x}})$ as we show in the following lemma.

DQM can be interpreted as an attempt to approximate the primal update of DADMM. Therefore, we evaluate the performance of DQM by studying a measure of the error of the approximation in the DQM update relative to the DADMM update. In the primal update of DQM, the gradient $\nabla f({\mathbf{x}}_{k+1})$ is estimated by the approximation $\nabla f({\mathbf{x}}_{k})+{\mathbf{H}}_{k}({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})$. Therefore, we can define the DQM error vector ${\mathbf{e}}_{k}^{DQM}$ as

Based on the definition in (21), the approximation error of DQM vanishes when the difference of two consecutive iterates ${\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}$ approaches zero. This observation is formalized in the following proposition by introducing an upper bound for the error vector norm $\|{\mathbf{e}}_{k}^{DQM}\|$ in terms of the difference norm $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$.

Consider the DQM method as introduced in (12)-(III) and the error ${\mathbf{e}}_{k}^{DQM}$ defined in (21). If Assumptions 1-4 hold true, the DQM error norm $\|{\mathbf{e}}_{k}^{DQM}\|$ is bounded above by

Proposition 2 asserts that the error norm $\|{\mathbf{e}}_{k}^{DQM}\|$ is bounded above by the minimum of a linear and a quadratic term of the iterate difference norm $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. Hence, the approximation error vanishes as the sequence of iterates ${\mathbf{x}}_{k}$ converges. We will show in Theorem 1 that the sequence $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ converges to zero which implies that the error vector ${\mathbf{e}}_{k}^{DQM}$ converges to the null vector ${\mathbf{0}}$. Notice that after a number of iterations the term $(L/2)\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ becomes smaller than $2M$, which implies that the upper bound in (22) can be simplified as $(L/2)\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|^{2}$ for sufficiently large $k$. This is important because it implies that the error vector norm $\|{\mathbf{e}}_{k}^{DQM}\|$ eventually becomes proportional to the quadratic term $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|^{2}$ and, as a consequence, it vanishes faster than the term $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$.

Utilize now the definition in (21) to rewrite the primal variable DQM update in (12) as

Comparison of (23) with the optimality condition for the DADMM update in (6) shows that they coincide except for the gradient approximation error term ${\mathbf{e}}_{k}^{DQM}$. The DQM and DADMM updates for the auxiliary variables ${\mathbf{z}}_{k}$ and the dual variables $\boldsymbol{\lambda}_{k}$ are identical [cf. (7), (8), and (III)], as already observed.

Further let the pair $({\mathbf{x}}^{*},{\mathbf{z}}^{*})$ stand for the unique solution of (2) with uniqueness implied by the strong convexity assumption and define $\boldsymbol{\alpha}^{*}$ as the unique optimal multiplier that lies in the column space of ${\mathbf{E}}_{o}$ – see Lemma 1 of for a proof that such optimal dual variable exists and is unique. To study convergence properties of DQM we modify the system of DQM equations defined by (III) and (23), which is equivalent to the system (12) – (III), to include terms that involve differences between current iterates and the optimal arguments ${\mathbf{x}}^{*}$, ${\mathbf{z}}^{*}$, and $\boldsymbol{\alpha}^{*}$. We state this reformulation in the following lemma.

Consider the DQM method as defined by (12)-(III) and its equivalent formulation in (III) and (23). If Assumption 1 holds true, then the optimal arguments ${\mathbf{x}}^{*}$, ${\mathbf{z}}^{*}$, and $\boldsymbol{\alpha}^{*}$ satisfy

Based on the definitions in (28), the energy function in (27) can be alternatively written $V({\mathbf{z}},\boldsymbol{\alpha})=V({\mathbf{u}})=\|{\mathbf{u}}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$, where ${\mathbf{u}}^{*}=[{\mathbf{z}}^{*};\boldsymbol{\alpha}^{*}]$. The energy sequence $V({\mathbf{u}}_{k})=\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}$ converges to zero at a linear rate as we state in the following theorem.

Consider the DQM method as defined by (12)-(III), let the constant $c$ be such that $c>4M^{2}/({m\gamma_{u}^{2}})$, and define the sequence of non-negative variables $\zeta_{k}$ as

Further, consider arbitrary constants $\mu$, $\mu^{\prime}$, and $\eta$ with $\mu,\mu^{\prime}>1$ and $\eta_{k}\in({\zeta_{k}}/{m},{c\gamma_{u}^{2}}/{\zeta_{k}})$. If Assumptions 1-4 hold true, then the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$ generated by DQM satisfies

where the sequence of positive scalars $\delta_{k}$ is given by

Notice that $\delta_{k}$ is a decreasing function of $\zeta_{k}$ and that $\zeta_{k}$ is bounded above by $2M$. Therefore, if we substitute $\zeta_{k}$ by $2M$ in (31), the inequality in (30) is still valid. This substitution implies that the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$ converges linearly to zero with a coefficient not larger than $1-\delta$ with $\delta=\delta_{k}$ following from (30) with $\zeta_{k}=2M$. The more generic definition of $\zeta_{k}$ in (29) is important for the rate comparisons in Section IV-A. Observe that in order to guarantee that $\delta_{k}>0$ for all $k\geq 0$, $\eta_{k}$ is chosen from the interval $({\zeta_{k}}/{m},{c\gamma_{u}^{2}}/{\zeta_{k}})$. This interval is non-empty since the constant $c$ is chosen as $c>{4M^{2}}/({m\gamma_{u}^{2}})\geq{\zeta_{k}^{2}}/({m\gamma_{u}^{2}})$.

The linear convergence in Theorem 1 is for the vector ${\mathbf{u}}_{k}$ which includes the auxiliary variable ${\mathbf{z}}_{k}$ and the multipliers $\boldsymbol{\alpha}_{k}$. Linear convergence of the primal variables ${\mathbf{x}}_{k}$ to the optimal argument ${\mathbf{x}}^{*}$ follows as a corollary that we establish next.

Under the assumptions in Theorem 1, the sequence of squared norms $\|{\mathbf{x}}_{k}-{\mathbf{x}}^{*}\|^{2}$ generated by the DQM algorithm converges R-linearly to zero, i.e.,

Proof : Notice that according to (26) we can write $\|{\mathbf{E}}_{u}({\mathbf{x}}_{k}-{\mathbf{x}}^{*})\|^{2}=4\|{\mathbf{z}}_{k}-{\mathbf{z}}^{*}\|^{2}$. Since $\gamma_{u}$ is the smallest singular value of ${\mathbf{E}}_{u}$, we obtain that $\|{\mathbf{x}}_{k}-{\mathbf{x}}^{*}\|^{2}\leq({4}/{\gamma_{u}^{2}})\|{\mathbf{z}}_{k}-{\mathbf{z}}^{*}\|^{2}.$ Moreover, according to the relation $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}=c\|{\mathbf{z}}_{k}-{\mathbf{z}}^{*}\|^{2}+({1}/{c})\|\boldsymbol{\alpha}_{k}-\boldsymbol{\alpha}^{*}\|^{2}$ we can write $c\|{\mathbf{z}}_{k}-{\mathbf{z}}^{*}\|^{2}\leq\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}.$ Combining these two inequalities yields the claim in (32). $\blacksquare$

As per Corollary 1, convergence of the sequence ${\mathbf{x}}_{k}$ to ${\mathbf{x}}^{*}$ is dominated by a linearly decreasing sequence. Notice that the sequence of squared norms $\|{\mathbf{x}}_{k}-{\mathbf{x}}^{*}\|^{2}$ need not be monotonically decreasing as the energy sequence $\|{\mathbf{u}}_{k+1}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$ is.

Based on the result in Corollary 1, the sequence of iterates ${\mathbf{x}}_{k}$ generated by DQM converges. This observation implies that the sequence $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ approaches zero. Hence, the sequence of scalars $\zeta_{k}$ defined in (29) converges to 0 as time passes, since $\zeta_{k}$ is bounded above by $(L/2)\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. Using this fact that $\lim_{k\to\infty}\zeta_{k}=0$ to compute the limit of $\delta_{k}$ in (31) and further making $\mu^{\prime}\rightarrow 1$ in the resulting limit we have that

Notice that the limit of $\delta_{k}$ in (33) is identical to the constant of linear convergence for DADMM . Therefore, we conclude that as time passes the constant of linear convergence for DQM approaches the one for DADMM.

To compare the convergence rates of DLM, DQM and DADMM we define the error of the gradient approximation for DLM as

which is the difference of exact gradient $\nabla f({\mathbf{x}}_{k+1})$ and the DLM gradient approximation $\nabla f({\mathbf{x}}_{k})+\rho({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})$. Similar to the result in Proposition 2 for DQM we can show that the DLM error vector norm $\|{\mathbf{e}}_{k}^{DLM}\|$ is bounded by a factor of $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$.

Consider the DLM algorithm with updates in (7)-(II) and the error vector ${\mathbf{e}}_{k}^{DLM}$ defined in (34). If Assumptions 1-4 hold true, the DLM error vector norm $\|{\mathbf{e}}_{k}^{DLM}\|$ satisfies

The result in Proposition 3 differs from Proposition 2 in that the DLM error $\|{\mathbf{e}}_{k}^{DLM}\|$ vanishes at a rate of $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ whereas the DQM error $\|{\mathbf{e}}_{k}^{DQM}\|$ eventually becomes proportional to $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|^{2}$. This results in DLM failing to approach the convergence behavior of DADMM as we show in the following theorem.

Consider the DLM method as introduced in (7)-(II). Assume that the constant $c$ is chosen such that $c>(\rho+M)^{2}/({m\gamma_{u}^{2}})$. Moreover, consider $\mu,\mu^{\prime}>1$ as arbitrary constants and $\eta$ as a positive constant chosen from the interval $((\rho+M)/{m},{c\gamma_{u}^{2}}/{(\rho+M)})$. If Assumptions 1-4 hold true, then the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$ generated by DLM satisfies

Based on the result in Theorem 2, the sequence $\|{\mathbf{u}}_{k+1}-{\mathbf{u}}^{*}\|_{{\mathbf{C}}}^{2}$ generated by DLM converges linearly to 0. This result is similar to the convergence properties of DQM as shown in Theorem 1; however, the constant of linear convergence $1/(1+\delta)$ in (36) is smaller than the constant $1/(1+\delta_{k})$ in (33).

V Numerical analysis

The optimization problem in (38) can be written in the form (1). To do so, simply define the local objective functions $f_{i}$ as

We compare the convergence paths of the DLM, DQM, and DADMM algorithms for solving the logistic regression problem in (38). Edges between the nodes are randomly generated with the connectivity ratio $r_{c}$. Observe that the connectivity ratio $r_{c}$ is the probability of two nodes being connected.

Observe that the computational complexity of DQM is lower than DADMM. Therefore, DQM outperforms DADMM in terms of convergence time or number of required operations until convergence. This phenomenon is shown in Fig 2 by comparing the relative of errors of DLM, DQM, and DADMM versus CPU runtime. According to Fig 2, DADMM achieves the relative error ${\|{\mathbf{x}}_{k}-{\mathbf{x}}^{*}\|}/{\|{\mathbf{x}}_{0}-{\mathbf{x}}^{*}\|}=10^{-10}$ after running for $3.6$ seconds, while DLM and DQM require $1.3$ and $0.4$ seconds, respectively, to achieve the same accuracy.

Notice that in large scale logistic regression problems we expect larger condition number for the objective function $f$. In these scenarios we expect to observe a poor performance by the DLM algorithm that only operates on first-order information. This expectation is satisfied by comparing the relative errors of DLM, DQM, and DADMM versus runtime for the large scale problem in Fig. 4. In this case, DLM is even worse than DADMM that has a very high computational complexity. Similar to the result in Fig. 3, DQM has the best performance among these three methods.

V-B Effect of the regularization parameter c𝑐c

The parameter $c$ has a significant role in the convergence of DADMM. Likewise, choosing the optimal choice of $c$ is critical in the convergence of DQM. We study the effect of $c$ by tuning this parameter for a fixed network and training set. We use all the parameters in Fig. 1 and we compare performance of the DQM algorithm for the values $c=0.2$, $c=0.4$, $c=0.8$, and $c=1$. Fig. 5 illustrates the convergence paths of the DQM algorithm for different choices of the parameter $c$. The best performance among these choices is achieved for $c=0.8$. The comparison of the plots in Fig. 5 shows that increasing or decreasing the parameter $c$ is not necessarily leads to a faster convergence. We can interpret $c$ as the stepsize of DQM which the optimal choice may vary for the problems with different network sizes, network topologies, condition numbers of objective functions, etc.

V-C Effect of network topology

VI Conclusions

A decentralized quadratically approximated version of the alternating direction method of multipliers (DQM) is proposed for solving decentralized optimization problems where components of the objective function are available at different nodes of a network. DQM minimizes a quadratic approximation of the convex problem that DADMM solves exactly at each step, and hence reduces the computational complexity of DADMM. Under some mild assumptions, linear convergence of the sequence generated by DQM is proven. Moreover, the constant of linear convergence for DQM approaches that of DADMM asymptotically. Numerical results for a logistic regression problem verify the analytical results that convergence paths of DQM and DADMM are similar for large iteration index, while the computational complexity of DQM is significantly smaller than DADMM.

Appendix A Proof of Lemma 1

According to the update for the Lagrange multiplier $\boldsymbol{\lambda}$ in (III), we can substitute $\boldsymbol{\lambda}_{k}$ by $\boldsymbol{\lambda}_{k+1}-c\left({\mathbf{A}}{\mathbf{x}}_{k+1}+{\mathbf{B}}{\mathbf{z}}_{k+1}\right)$. Applying this substitution into the first equation of (III) leads to

Observing the definitions ${\mathbf{B}}=[-{\mathbf{I}}_{mp};-{\mathbf{I}}_{mp}]$ and $\boldsymbol{\lambda}=[\boldsymbol{\alpha};\boldsymbol{\beta}]$, and the result in (40), we obtain $\boldsymbol{\alpha}_{k+1}=-\boldsymbol{\beta}_{k+1}$ for $k\geq 0$. Considering the initial condition $\boldsymbol{\alpha}_{0}=-\boldsymbol{\beta}_{0}$, we obtain that $\boldsymbol{\alpha}_{k}=-\boldsymbol{\beta}_{k}$ for $k\geq 0$ which follows the first claim in Lemma 1.

Based on the definitions ${\mathbf{A}}=[{\mathbf{A}}_{s};{\mathbf{A}}_{d}]$, ${\mathbf{B}}=[-{\mathbf{I}}_{mp};-{\mathbf{I}}_{mp}]$, and $\boldsymbol{\lambda}=[\boldsymbol{\alpha};\boldsymbol{\beta}]$, we can split the update for the Lagrange multiplier $\boldsymbol{\lambda}$ in (8) as

Observing the result that $\boldsymbol{\alpha}_{k}=-\boldsymbol{\beta}_{k}$ for $k\geq 0$, summing up the equations in (41) and (42) yields

Considering the definition of the oriented incidence matrix ${\mathbf{E}}_{u}={\mathbf{A}}_{s}+{\mathbf{A}}_{d}$, we obtain that ${\mathbf{E}}_{u}{\mathbf{x}}_{k}=2{\mathbf{z}}_{k}$ holds for $k>0$. According to the initial condition ${\mathbf{E}}_{u}{\mathbf{x}}_{0}=2{\mathbf{z}}_{0}$, we can conclude that the relation ${\mathbf{E}}_{u}{\mathbf{x}}_{k}=2{\mathbf{z}}_{k}$ holds for $k\geq 0$.

Subtract the update for $\boldsymbol{\beta}_{k}$ in (42) from the update for $\boldsymbol{\alpha}_{k}$ in (41) and consider the relation $\boldsymbol{\beta}_{k}=-\boldsymbol{\alpha}_{k}$ to obtain

Substituting ${\mathbf{A}}_{s}-{\mathbf{A}}_{d}$ in (44) by ${\mathbf{E}}_{o}$ implies that

Hence, if $\boldsymbol{\alpha}_{k}$ lies in the column space of matrix ${\mathbf{E}}_{o}$, then $\boldsymbol{\alpha}_{k+1}$ also lies in the column space of ${\mathbf{E}}_{o}$. According to the third condition of Assumption 1, $\boldsymbol{\alpha}_{0}$ satisfies this condition, therefore $\boldsymbol{\alpha}_{k}$ lies in the column space of matrix ${\mathbf{E}}_{o}$ for all $k\geq 0$.

Appendix B Proof of Proposition 1

The update for the multiplier $\boldsymbol{\lambda}$ in (8) implies that we can substitute $\boldsymbol{\lambda}_{k}$ by $\boldsymbol{\lambda}_{k+1}-c({\mathbf{A}}{\mathbf{x}}_{k+1}+{\mathbf{B}}{\mathbf{z}}_{k+1})$ to simplify (12) as

Considering the first result of Lemma 1 that $\boldsymbol{\alpha}_{k}=-\boldsymbol{\beta}_{k}$ for $k\geq 0$ in association with the definition ${\mathbf{A}}=[{\mathbf{A}}_{s};{\mathbf{A}}_{d}]$ implies that the product ${\mathbf{A}}^{T}\boldsymbol{\lambda}_{k+1}$ is equivalent to

According to the definition ${\mathbf{E}}_{o}:={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$, the right hand side of (47) can be simplified as

Based on the structures of the matrices ${\mathbf{A}}$ and ${\mathbf{B}}$, and the definition ${\mathbf{E}}_{u}:={\mathbf{A}}_{s}+{\mathbf{A}}_{d}$, we can simplify ${\mathbf{A}}^{T}{\mathbf{B}}$ as

Substituting the results in (48) and (49) into (46) leads to

The second result in Lemma 1 states that ${\mathbf{z}}_{k}={\mathbf{E}}_{u}{\mathbf{x}}_{k}/2$. Multiplying both sides of this equality by ${\mathbf{E}}_{u}^{T}$ from left we obtain that ${\mathbf{E}}_{u}^{T}{\mathbf{z}}_{k}={\mathbf{E}}_{u}^{T}{\mathbf{E}}_{u}{\mathbf{x}}_{k}/2$ for $k\geq 0$. Observing the definition of the unoriented Laplacian ${\mathbf{L}}_{u}:={\mathbf{E}}_{u}^{T}{\mathbf{E}}_{u}/2$, we obtain that the product ${\mathbf{E}}_{u}^{T}{\mathbf{z}}_{k}$ is equal to ${\mathbf{L}}_{u}{\mathbf{x}}_{k}$ for $k\geq 0$. Therefore, in (50) we can substitute ${\mathbf{E}}_{u}^{T}\left({\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\right)$ by ${\mathbf{L}}_{u}({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})$ and write

Observe that the new variables $\boldsymbol{\phi}_{k}$ are defined as $\boldsymbol{\phi}_{k}:={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k}$. Multiplying both sides of (45) by ${\mathbf{E}}_{o}^{T}$ from the left hand side and considering the definition of oriented Laplacian ${\mathbf{L}}_{o}={\mathbf{E}}_{o}^{T}{\mathbf{E}}_{o}/2$ follows the update rule of $\boldsymbol{\phi}_{k}$ in (1), i.e.,

According to the definition $\boldsymbol{\phi}_{k}={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k}$ and the update formula in (52), we can conclude that ${\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k+1}=\boldsymbol{\phi}_{k+1}=\boldsymbol{\phi}_{k}+c{\mathbf{L}}_{o}{\mathbf{x}}_{k+1}$. Substituting ${\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k+1}$ by $\boldsymbol{\phi}_{k}+c{\mathbf{L}}_{o}{\mathbf{x}}_{k+1}$ in (51) yields

Observing the definition ${\mathbf{D}}=({\mathbf{L}}_{u}+{\mathbf{L}}_{o})/2$ we rewrite (53) as

Multiplying both sides of (54) by $\left({\mathbf{H}}_{k}+2c{\mathbf{D}}\right)^{-1}$ from the left hand side yields the first update in (1).

Appendix C Proof of Lemma 2

Using the Cauchy-Schwarz inequality we can write

Substituting the upper bound in (57) into (56) implies that the squared norm $\left\|{\mathbf{H}}({\mathbf{x}})-{\mathbf{H}}({\hat{\mathbf{x}}})\right\|^{2}$ is bounded above as

Observe that Assumption 3 states that local objective functions Hessian $\nabla^{2}f_{i}({\mathbf{x}}_{i})$ are Lipschitz continuous with constant $L$, i.e. $\|\nabla^{2}f_{i}({\mathbf{x}}_{i})-\nabla^{2}f_{i}({\hat{\mathbf{x}}}_{i})\|\leq L\|{\mathbf{x}}_{i}-{\hat{\mathbf{x}}}_{i}\|$. Considering this inequality the upper bound in (58) can be changed by replacing $\|\nabla^{2}f_{i}({\mathbf{x}}_{i})-\nabla^{2}f_{i}({\hat{\mathbf{x}}}_{i})\|$ by $L\|{\mathbf{x}}_{i}-{\hat{\mathbf{x}}}_{i}\|$ which yields

Note that for any sequences of scalars such as $a_{i}$ and $b_{i}$, the inequality $\sum_{i=1}^{n}a_{i}^{2}b_{i}^{2}\leq(\sum_{i=1}^{n}a_{i}^{2})(\sum_{i=1}^{n}b_{i}^{2})$ holds. If we divide both sides of this relation by $\sum_{i=1}^{n}b_{i}^{2}$ and set $a_{i}=\|{\mathbf{x}}_{i}-{\hat{\mathbf{x}}}_{i}\|$ and $b_{i}=\|{\mathbf{v}}_{i}\|$, we obtain

Combining the two inequalities in (59) and (60) leads to

Since the right hand side of (61) does not depend on ${\mathbf{v}}$ we can eliminate the maximization with respect to ${\mathbf{v}}$. Further, note that according to the structure of vectors ${\mathbf{x}}$ and ${\hat{\mathbf{x}}}$, we can write $\left\|{\mathbf{x}}-{\hat{\mathbf{x}}}\right\|^{2}=\sum_{i=1}^{n}\left\|{\mathbf{x}}_{i}-{\hat{\mathbf{x}}}_{i}\right\|^{2}$. These two observations in association with (61) imply that

Computing the square roots of terms in (62) yields (20).

Appendix D Proofs of Propositions 2 and 3

The fundamental theorem of calculus implies that the difference of gradients $\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}_{k})$ can be written as

By computing norms of both sides of (63) and considering that norm of integral is smaller than integral of norm we obtain that

The upper bound $M$ for the eigenvalues of the Hessians as in (19), implies that $\|{\mathbf{H}}\left(s{\mathbf{x}}+(1-s){\hat{\mathbf{x}}}\right)({\mathbf{x}}-{\hat{\mathbf{x}}})\|\leq M\|{\mathbf{x}}-{\hat{\mathbf{x}}}\|$. Substituting this upper bound into (64) leads to

The error vector norm $\|{\mathbf{e}}_{k}^{DLM}\|$ in (34) is bounded above as

By substituting the upper bound for $\|\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}_{k})\|$ in (65) into (66), the claim in (35) follows.

To prove (22), first we show that $\|{\mathbf{e}}_{k}^{DQM}\|\leq 2M\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ holds. Observe that the norm of error vector ${\mathbf{e}}_{k}^{DQM}$ defined (21) can be upper bounded using the triangle inequality as

Based on the Cauchy-Schwarz inequality and the upper bound $M$ for the eigenvalues of Hessians as in (19), we obtain $\|{\mathbf{H}}_{k}({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})\|\leq M\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. Further, as mentioned in (65) the difference of gradients $\|\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}_{k})\|$ is upper bounded by $M\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. Substituting these upper bounds for the terms in the right hand side of (67) yields

The next step is to show that $\|{\mathbf{e}}_{k}^{DQM}\|\leq(L/2)\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|^{2}$. Adding and subtracting the integral $\int_{0}^{1}{\mathbf{H}}({\mathbf{x}}_{k})({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})\ ds$ to the right hand side of (63) results in

First observe that the integral $\int_{0}^{1}{\mathbf{H}}({\mathbf{x}}_{k})({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})\ ds$ can be simplified as ${\mathbf{H}}({\mathbf{x}}_{k})({\mathbf{x}}_{k+1}-{\mathbf{x}}_{k})$. Observing this simplification and regrouping the terms yield

Computing norms of both sides of (D), considering the fact that norm of integral is smaller than integral of norm, and using Cauchy-Schwarz inequality lead to

Lipschitz continuity of the Hessian as in (20) implies that $\left\|{\mathbf{H}}(s{\mathbf{x}}_{k+1}+(1-s){\mathbf{x}}_{k})-{\mathbf{H}}({\mathbf{x}}_{k})\right\|\leq sL\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. By substituting this upper bound into the integral in (71) and substituting the left hand side of (71) by $\|{\mathbf{e}}_{k}^{DQM}\|$ we obtain

Simplification of the integral in (72) follows

The results in (68) and (73) follow the claim in (22).

Appendix E Proof of Lemma 3

In this section we first introduce an equivalent version of Lemma 3 for the DLM algorithm. Then, we show the validity of both lemmata in a general proof.

Consider DLM as defined by (7)-(II). If Assumption 1 holds true, then the optimal arguments ${\mathbf{x}}^{*}$, ${\mathbf{z}}^{*}$, and $\boldsymbol{\alpha}^{*}$ satisfy

Notice that the claims in Lemmata 3 and 4 are identical except in the error term of the first equalities. To provide a general framework to prove the claim in these lemmata we introduce ${\mathbf{e}}_{k}$ as the general error vector. By replacing ${\mathbf{e}}_{k}$ with ${\mathbf{e}}_{k}^{DQM}$ we obtain the result of DQM in Lemma 3 and by setting ${\mathbf{e}}_{k}={\mathbf{e}}_{k}^{DLM}$ the result in Lemma 4 follows. We start with the following Lemma that captures the KKT conditions of optimization problem (4).

Consider the optimization problem (4). The optimal Lagrange multiplier $\boldsymbol{\alpha}^{*}$, primal variable ${\mathbf{x}}^{*}$ and auxiliary variable ${\mathbf{z}}^{*}$ satisfy the following system of equations

Proof : First observe that the KKT conditions of the decentralized optimization problem in (4) are given by

Based on the definitions of the matrix ${\mathbf{B}}=[-{\mathbf{I}}_{mp};-{\mathbf{I}}_{mp}]$ and the optimal Lagrange multiplier $\boldsymbol{\lambda}^{*}:=[\boldsymbol{\alpha}^{*};\boldsymbol{\beta}^{*}]$, we obtain that ${\mathbf{B}}^{T}{\boldsymbol{\lambda}^{*}}={\mathbf{0}}$ in (78) is equivalent to $\boldsymbol{\alpha}^{*}=-\boldsymbol{\beta}^{*}$. Considering this result and the definition ${\mathbf{A}}=[{\mathbf{A}}_{s};{\mathbf{A}}_{d}]$, we obtain

The definition ${\mathbf{E}}_{o}:={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$ implies that the right hand side of (79) can be simplified as ${\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}^{*}$ which shows ${\mathbf{A}}^{T}{\boldsymbol{\lambda}^{*}}={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}^{*}$. Substituting ${\mathbf{A}}^{T}{\boldsymbol{\lambda}^{*}}$ by ${\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}^{*}$ into the first equality in (78) follows the first claim in (77).

Decompose the KKT condition ${\mathbf{A}}{\mathbf{x}}^{*}+{\mathbf{B}}{\mathbf{z}}^{*}={\mathbf{0}}$ in (78) based on the definitions of ${\mathbf{A}}$ and ${\mathbf{B}}$ as

Subtracting the equalities in (80) implies that $({\mathbf{A}}_{s}-{\mathbf{A}}_{d}){\mathbf{x}}^{*}={\mathbf{0}}$ which by considering the definition ${\mathbf{E}}_{o}={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$, the second equation in (77) follows. Summing up the equalities in (80) yields $({\mathbf{A}}_{s}+{\mathbf{A}}_{d}){\mathbf{x}}^{*}=2{\mathbf{z}}$. This observation in association with the definition ${\mathbf{E}}_{u}={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$ follows the third equation in (77). $\blacksquare$

Proofs of Lemmata 3 and 4: First note that the results in Lemma 1 are also valid for DLM . Now, consider the first order optimality condition for primal updates of DQM and DLM in (12) and (10), respectively. Further, recall the definitions of error vectors ${\mathbf{e}}_{k}^{DQM}$ and ${\mathbf{e}}_{k}^{DLM}$ in (21) and (34), respectively. Combining these observations we obtain that

Notice that by setting ${\mathbf{e}}_{k}={\mathbf{e}}_{k}^{DQM}$ we obtain the update for primal variable of DQM; likewise, setting ${\mathbf{e}}_{k}={\mathbf{e}}_{k}^{DLM}$ yields to the update of DLM.

Observe that the relation $\boldsymbol{\lambda}_{k}=\boldsymbol{\lambda}_{k+1}-c({\mathbf{A}}{\mathbf{x}}_{k+1}+{\mathbf{B}}{\mathbf{z}}_{k+1})$ holds for both DLM and DQM according to to the update formula for Lagrange multiplier in (8) and (III). Substituting $\boldsymbol{\lambda}_{k}$ by $\boldsymbol{\lambda}_{k+1}-c({\mathbf{A}}{\mathbf{x}}_{k+1}+{\mathbf{B}}{\mathbf{z}}_{k+1})$ in (81) follows

Based on the result in Lemma 1, the components of the Lagrange multiplier $\boldsymbol{\lambda}=[\boldsymbol{\alpha};\boldsymbol{\beta}]$ satisfy $\boldsymbol{\alpha}_{k+1}=-\boldsymbol{\beta}_{k+1}$. Hence, the product ${\mathbf{A}}^{T}{\boldsymbol{\lambda}_{k+1}}$ can be simplified as ${\mathbf{A}}_{s}^{T}\boldsymbol{\alpha}_{k+1}-{\mathbf{A}}_{d}^{T}\boldsymbol{\alpha}_{k+1}={\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}_{k+1}$ considering the definition that ${\mathbf{E}}_{o}={\mathbf{A}}_{s}-{\mathbf{A}}_{d}$. Furthermore, note that according to the definitions we have that ${\mathbf{A}}=[{\mathbf{A}}_{s};{\mathbf{A}}_{d}]$ and ${\mathbf{B}}=[-{\mathbf{I}};-{\mathbf{I}}]$ which implies that ${\mathbf{A}}^{T}{\mathbf{B}}=-({\mathbf{A}}_{s}+{\mathbf{A}}_{d})^{T}=-{\mathbf{E}}_{u}^{T}$. By making these substitutions into (82) we can write

The first result in Lemma 5 is equivalent to $\nabla f({\mathbf{x}}^{*})+{\mathbf{E}}_{o}^{T}\boldsymbol{\alpha}^{*}={\mathbf{0}}$. Subtracting both sides of this equation from the relation in (83) follows the first claim of Lemmata 3 and 4.

We proceed to prove the second and third claims in Lemmata 3 and 4. The update formula for $\boldsymbol{\alpha}_{k}$ in (45) and the second result in Lemma 5 that ${\mathbf{E}}_{o}{\mathbf{x}}^{*}=0$ imply that the second claim of Lemmata 3 and 4 are valid. Further, the result in Lemma 1 guaranteaes that ${\mathbf{E}}_{u}{\mathbf{x}}_{k}=2{\mathbf{z}}_{k}$. This result in conjunction with the result in Lemma 5 that ${\mathbf{E}}_{u}{\mathbf{x}}^{*}=2{\mathbf{z}}^{*}$ leads to the third claim of Lemmata 3 and 4.

Appendix F Proofs of Theorems 1 and 2

To prove Theorems 1 and 2 we show a sufficient condition for the claims in these theorems. Then, we prove these theorems by showing validity of the sufficient condition. To do so, we use the general coefficient $\beta_{k}$ which is equivalent to $\zeta_{k}$ in the DQM algorithm and equivalent to $\rho+M$ in the DLM method. These definitions and the results in Propositions 2 and 3 imply that

where ${\mathbf{e}}_{k}$ is ${\mathbf{e}}_{k}^{DQM}$ in DQM and ${\mathbf{e}}_{k}^{DLM}$ in DLM. The sufficient condition of Theorems 1 and 2 is studied in the following lemma.

Consider the DLM and DQM algorithms as defined in (7)-(II) and (12)-(III), respectively. Further, conducer $\delta_{k}$ as a sequence of positive scalars. If Assumptions 1-4 hold true then the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}$ converges linearly as

Proof : Proving linear convergence of the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}$ as mentioned in (85) is equivalent to showing that

According to the definition $\|{\mathbf{a}}\|_{\mathbf{C}}^{2}:={\mathbf{a}}^{T}{\mathbf{C}}{\mathbf{a}}$ we can show that

The relation in (F) shows that the right hand side of (87) can be substituted by $2({\mathbf{u}}_{k}-{\mathbf{u}}_{k+1})^{T}{\mathbf{C}}({\mathbf{u}}_{k+1}-{\mathbf{u}}^{*})+\|{\mathbf{u}}_{k}-{\mathbf{u}}_{k+1}\|_{\mathbf{C}}^{2}$. Applying this substitution into (87) leads to

This observation implies that to prove the linear convergence as claimed in (85), the inequality in (89) should be satisfied.

We proceed by finding a lower bound for the term $2({\mathbf{u}}_{k}-{\mathbf{u}}_{k+1})^{T}{\mathbf{C}}({\mathbf{u}}_{k+1}-{\mathbf{u}}^{*})$ in (89). By regrouping the terms in (83) and multiplying both sides of equality by $({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}$ from the left hand side we obtain that the inner product $({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}(\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}^{*}))$ is equivalent to

Based on (25), we can substitute $({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}{\mathbf{E}}_{o}^{T}(\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}^{*})$ in (F) by $(2/c)(\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}_{k})^{T}(\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}^{*})$. Further, the result in (26) implies that the term $c({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}{\mathbf{E}}_{u}^{T}\left({\mathbf{z}}_{k}-{\mathbf{z}}_{k+1}\right)$ in (F) is equivalent to $2c\left({\mathbf{z}}_{k}-{\mathbf{z}}_{k+1}\right)^{T}({\mathbf{z}}_{k+1}-{\mathbf{z}}^{*})$. Applying these substitutions into (F) leads to

Based on the definitions of matrix ${\mathbf{C}}$ and vector ${\mathbf{u}}$ in (28), the last two summands in the right hand side of (91) can be simplified as

Considering the simplification in (F) we can rewrite (91) as

Observe that the objective function $f$ is strongly convex with constant $m$ which implies the inequality $m\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|^{2}\leq({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}(\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}^{*}))$ holds true. Considering this inequality from the strong convexity of objective function $f$ and the simplification for the inner product $({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}(\nabla f({\mathbf{x}}_{k+1})-\nabla f({\mathbf{x}}^{*}))$ in (93), the following inequality holds

Substituting the lower bound for the term $2({\mathbf{u}}_{k}-{\mathbf{u}}_{k+1})^{T}{\mathbf{C}}({\mathbf{u}}_{k+1}-{\mathbf{u}}^{*})$ in (94) into (89), it follows that the following condition is sufficient to have (85),

We emphasize that inequality (F) implies the linear convergence result in (85). Therefore, our goal is to show that if (6) holds, the relation in (F) is also valid and consequently the result in (85) holds. According to the definitions of matrix ${\mathbf{C}}$ and vector ${\mathbf{u}}$ in (28), we can substitute $\|{\mathbf{u}}_{k+1}-{\mathbf{u}}^{*}\|_{\mathbf{C}}^{2}$ by $c\|{\mathbf{z}}_{k+1}-{\mathbf{z}}^{*}\|^{2}+({1}/{c})\|\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}^{*}\|^{2}$ and $\|{\mathbf{u}}_{k}-{\mathbf{u}}_{k+1}\|_{\mathbf{C}}^{2}$ by $c\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|^{2}+({1}/{c})\|\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}_{k}\|^{2}$. Making these substitutions into (F) yields

The inequality in (84) implies that $-\|{\mathbf{e}}_{k}\|$ is lower bounded by $-\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$. This lower bound in conjunction with the fact that inner product of two vectors is not smaller than the negative of their norms product leads to

Substituting $({\mathbf{x}}_{k+1}-{\mathbf{x}}^{*})^{T}{\mathbf{e}}_{k}$ in (96) by its lower bound in (97) leads to a sufficient condition for (96) as in (6), i.e.,

Observe that if (F) holds true, then (96) and its equivalence (F) are valid and as a result the inequality in (85) is also satisfied. $\blacksquare$

According to the result in Lemma 6, the sequence $\|{\mathbf{u}}_{k}-{\mathbf{u}}^{*}\|^{2}$ converges linearly as mentioned in (85) if the inequality in (6) holds true. Therefore, in the following proof we show that for

the inequality in (6) holds and consequently (85) is valid.

Proofs of Theorems 1 and 2: we show that if the constant $\delta_{k}$ is chosen as in (99), then the inequality in (6) holds true. To do this first we should find an upper bound for $\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ regarding the terms in the right hand side of (6). Observing the result of Lemma 1 that ${\mathbf{E}}_{u}{\mathbf{x}}_{k}=2{\mathbf{z}}_{k}$ for times $k$ and $k+1$, we can write

The singular values of ${\mathbf{E}}_{u}$ are bounded below by $\gamma_{u}$. Hence, equation (100) implies that $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ is upper bounded by

Multiplying both sides of (101) by $\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|$ yields

Notice that for any vectors ${\mathbf{a}}$ and ${\mathbf{b}}$ and positive constant $\eta_{k}>0$ the inequality $2\|{\mathbf{a}}\|\|{\mathbf{b}}\|\leq(1/\eta_{k})\|{\mathbf{a}}\|^{2}+\eta_{k}\|{\mathbf{b}}\|^{2}$ holds true. By setting ${\mathbf{a}}={\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}$ and ${\mathbf{b}}=(1/\gamma_{u}^{2})({\mathbf{z}}_{k+1}-{\mathbf{z}}_{k})$ the inequality $2\|{\mathbf{a}}\|\|{\mathbf{b}}\|\leq(1/\eta_{k})\|{\mathbf{a}}\|^{2}+\eta_{k}\|{\mathbf{b}}\|^{2}$ is equivalent to

Substituting the upper bound for $({2}/{\gamma_{u}})\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|$ in (103) into (102) yields

Notice that inequality (104) provides an upper bound for $\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ in (6) regarding the terms in the right hand side of inequality which are $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|^{2}$ and $\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|^{2}$. The next step is to find upper bounds for the other two terms in the left hand side of (6) regarding the terms in the right hand side of (6) which are $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|^{2}$, $\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|^{2}$, and $\|\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}_{k}\|^{2}$. First we start with $\|{\mathbf{z}}_{k+1}-{\mathbf{z}}^{*}\|^{2}$. The relation in (26) and the upper bound $\Gamma_{u}$ for the singular values of matrix ${\mathbf{E}}_{u}$ yield

The next step is to bound $(\delta_{k}/c)\|\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}^{*}\|$ in terms of the term in the right hand side of (47). First, note that for any vector ${\mathbf{a}}$, ${\mathbf{b}}$, and ${\mathbf{c}}$, and constants $\mu$ and $\mu^{\prime}$ which are larger than 1, i.e. $\mu,\mu^{\prime}>1$, we can write

Set ${\mathbf{a}}=c{\mathbf{E}}_{u}^{T}({\mathbf{z}}_{k}-{\mathbf{z}}_{k+1})$, ${\mathbf{b}}=\nabla f({\mathbf{x}}^{*})-\nabla f({\mathbf{x}}_{k+1})$, and ${\mathbf{c}}={\mathbf{E}}_{o}^{T}(\boldsymbol{\alpha}^{*}-\boldsymbol{\alpha}_{k+1})$. By choosing these values and observing equality (24) we obtain ${\mathbf{a}}+{\mathbf{b}}+{\mathbf{c}}={\mathbf{e}}_{k}$. Hence, by making these substitutions for ${\mathbf{a}}$, ${\mathbf{b}}$, ${\mathbf{c}}$, and ${\mathbf{a}}+{\mathbf{b}}+{\mathbf{c}}$ into (F) we can write

Observe that the error norm $\|{\mathbf{e}}_{k}\|$ is bounded above by $\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ as in (84) and the norm $\|c{\mathbf{E}}_{u}^{T}({\mathbf{z}}_{k}-{\mathbf{z}}_{k+1})\|^{2}$ is upper bounded by $c^{2}\Gamma_{u}^{2}\|{\mathbf{z}}_{k}-{\mathbf{z}}_{k+1}\|^{2}$ since all the singular values of the unoriented matrix ${\mathbf{E}}_{u}$ are smaller than $\Gamma_{u}$. Substituting these upper bounds and the lower bound in (108) into (107) implies

Considering the result in (101), $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ is upper by $({2}/{\gamma_{u}})\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|$. Therefore, we can substitute $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$ in the right hand side of (109) by its upper bound $({2}/{\gamma_{u}})\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|$. Making this substitution, dividing both sides by $(1-{1}/{\mu^{\prime}})(1-{1}/{\mu})\gamma_{o}^{2}$, and regrouping the terms lead to

Considering the upper bounds for $\beta_{k}\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|\|{\mathbf{x}}_{k+1}-{\mathbf{x}}_{k}\|$, $\|{\mathbf{z}}_{k+1}-{\mathbf{z}}^{*}\|^{2}$, and $\|\boldsymbol{\alpha}_{k+1}-\boldsymbol{\alpha}_{k}\|^{2}$, in (104), (105), and (110), respectively, we obtain that if the inequality

holds true, (6) is satisfied. Hence, the last step is to show that for the specific choice of $\delta_{k}$ in (99) the result in (111) is satisfied. In order to make sure that (111) holds, it is sufficient to show that the coefficients of $\|{\mathbf{x}}_{k+1}-{\mathbf{x}}^{*}\|^{2}$ and $\|{\mathbf{z}}_{k+1}-{\mathbf{z}}_{k}\|^{2}$ in the left hand side of (111) are smaller than the ones in the right hand side. Hence, we should verify the validity of inequalities

Considering the inequality for $\delta_{k}$ in (99) we obtain that (112) and (113) are satisfied. Hence, if $\delta_{k}$ satisfies condition in (99), (111) and consequently (6) are satisfied. Now recalling the result of Lemma 6 that inequality (6) is a sufficient condition for the linear convergence in (85), we obtain that the linear convergence holds. By setting $\beta_{k}=\zeta_{k}$ we obtain the linear convergence of DQM in Theorem 1 is valid and the linear coefficient in (99) can be simplified as (31). Moreover, setting $\beta_{k}=\rho+M$ follows the linear convergence of DLM as in Theorem 2 with the linear constant in (37).

References