A Decentralized Second-Order Method with Exact Linear Convergence Rate for Consensus Optimization

I Introduction

Dual domain methods build on the fact that the dual function of (1) has a gradient with separable structure. The use of plain dual gradient descent is possible but generally slow to converge . In centralized optimization, better convergence speeds are attained by the method of multipliers (MM) that adds a quadratic augmentation term to the Lagrangian , or the proximal (P)MM that adds an additional term to keep iterates close. In either case, the quadratic term that is added to construct the augmented Lagrangian makes distributed computation of primal gradients impossible. This issue is most often overcome with the use of decentralized (D) versions of the alternating direction method of multipliers (ADMM). Besides the ADMM, other methods that use different alternatives to approximate the gradients of the dual function have also been proposed . The convergence rates of these methods have not been studied except for the DADMM and its variants that are known to converge linearly to the optimal argument when the local functions are strongly convex and their gradients are Lipschitz continuous . An important observation here is that while all of these methods try to approximate the MM or the PMM, the performance penalty entailed by the approximation has not been studied.

This paper introduces the exact second order method (ESOM) which uses quadratic approximations of the augmented Lagrangians of (1) and leads to a set of separable subproblems. Similar to other second order methods, implementation of ESOM requires computation of Hessian inverses. Distributed implementation of this operation is infeasible because while the Hessian of the proximal augmented Lagrangian is neighbor sparse, its inverse is not. ESOM resolves this issue by using the Hessian inverse approximation technique introduced in . This technique consists of truncating the Taylor’s series of the Hessian inverse to order $K$ to obtain the family of methods ESOM-$K$. Implementation of this expansion in terms of local operations is possible. A remarkable property of all ESOM-$K$ methods is that they can be shown to pay a performance penalty relative to (centralized) PMM that vanishes with increasing iterations.

We begin the paper by reformulating (1) in a form more suitable for decentralized implementation (Proposition 1) and proceed to describe the PMM (Section II). ESOM is a variation of PMM that substitutes the proximal augmented Lagrangian with its quadratic approximation (Section III). Implementation of ESOM requires computing the inverse of the Hessian of the proximal augmented Lagrangian. Since this inversion cannot be computed using local and neighboring information, ESOM-$K$ approximates the Hessian inverse with the $K$-order truncation of the Taylor’s series expansion of the Hessian inverse. This expansion can be carried out using an inner loop of local operations. This and other details required for decentralized implementation of ESOM-$K$ are discussed in Section III-A along with a discussion of how ESOM can be interpreted as a saddle point generalization of the Network Newton methods proposed in (Remark 1) or a second order version of the EXTRA method proposed in (Remark 2).

Convergence analyses of PMM and ESOM are then presented (Section IV). Linear convergence of PMM is established (Section IV-A) and linear convergence factors explicitly derived to use as benchmarks (Theorem 1). In the ESOM analysis (Section IV-B) we provide an upper bound for the error of the proximal augmented Lagrangian approximation (Lemma 3). We leverage this result to prove linear convergence of ESOM (Theorem 2) and to show that ESOM’s linear convergence factor approaches the corresponding PMM factor as time grows (Section IV-C). This indicates that the convergence paths of (distributed) ESOM-$K$ and (centralized) PMM are very close. We also study the dependency of the convergence constant with the algorithm’s order $K$.

ESOM tradeoffs and comparisons with other decentralized methods for solving consensus optimization problems are illustrated in numerical experiments (Section V) for a decentralized least squares problem (Section V-A) and a decentralized logistic regression classification problem (Section V-B). Numerical results in both settings verify that larger $K$ leads to faster convergence in terms of number of iterations. However, we observe that all version of ESOM-$K$ exhibit similar convergence rates in terms of the number of communication exchanges. This implies that ESOM- is preferable with respect to the latter metric and that larger $K$ is justified when computational cost is of interest. Faster convergence relative to EXTRA, Network Newton, and DADMM is observed. We close the paper with concluding remarks (Section VI).

II Proximal method of multipliers

The first condition implies that the weights are symmetric, i.e., $w_{ij}=w_{ji}$. The second condition ensures that the weights of a given node sum up to 1, i.e., $\sum_{j=1}^{n}w_{ij}=1$ for all $i$. Since ${\mathbf{W}}{\mathbf{1}}={\mathbf{1}}$ we have that ${\mathbf{I}}-{\mathbf{W}}$ is rank deficient. The last condition $\text{null}({\mathbf{I}}-{\mathbf{W}})=\text{span}({\mathbf{1}})$ makes the rank of ${\mathbf{I}}-{\mathbf{W}}$ exactly equal to $n-1$ .

The matrix ${\mathbf{W}}$ can be used to reformulate (II) as we show in the following proposition.

I.e., ${\mathbf{x}}^{*}=[{\mathbf{x}}_{1}^{*};\dots;{\mathbf{x}}_{n}^{*}]$ with $\{{\mathbf{x}}_{i}^{*}\}_{i=1}^{n}$ the solution of (II).

Proof : We just show that the constraint $(({\mathbf{I}}_{n}-{\mathbf{W}})\otimes{\mathbf{I}}_{p}){\mathbf{x}}=({\mathbf{I}}_{np}-{\mathbf{Z}}){\mathbf{x}}={\mathbf{0}}$ is also a consensus constraint. To do so begin by noticing that since ${\mathbf{I}}-{\mathbf{W}}$ is positive semidefinite, ${\mathbf{I}}-{\mathbf{Z}}=({\mathbf{I}}-{\mathbf{W}})\otimes{\mathbf{I}}_{p}$ is also positive semidefinite. Therefore, the null space of the square root matrix $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$ is equal to the null space of ${\mathbf{I}}-{\mathbf{Z}}$ and we conclude that satisfying the condition $({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{x}}$ is equivalent to the consensus condition ${\mathbf{x}}_{1}=\dots={\mathbf{x}}_{n}$. This observation in conjunction with the definition of the aggregate function $f({\mathbf{x}})=\sum_{i=1}^{n}f_{i}({\mathbf{x}}_{i})$ shows that the programs in (4) and (3) are equivalent. In particular, the optimal solution of (4) is ${\mathbf{x}}^{*}=[{\mathbf{x}}_{1}^{*};\dots;{\mathbf{x}}_{n}^{*}]$ with $\{{\mathbf{x}}_{i}^{*}\}_{i=1}^{n}$ the solution of (II). $\blacksquare$

where $\alpha$ is a positive constant. Given the properties of the matrix ${\mathbf{Z}}$, the augmentation term $(\alpha/2){\mathbf{x}}^{T}({\mathbf{I}}-{\mathbf{Z}}){\mathbf{x}}$ is null when the variable ${\mathbf{x}}$ is a feasible solution of (4). Otherwise, the inner product is positive and behaves as a penalty for the violation of the consensus constraint.

where the proximal coefficient $\epsilon>0$ is a strictly positive constant. The dual variable ${\mathbf{v}}_{t}$ is updated by ascending through the gradient of the augmented Lagrangian with respect to the dual variable $\nabla_{{\mathbf{v}}}{\mathcal{L}}({\mathbf{x}}_{t+1},{\mathbf{v}}_{t})$ with stepsize $\alpha$

The updates in (6) and (7) for PMM can be considered as a generalization of the method of multipliers (MM), because setting the proximal coefficient $\epsilon=0$ recovers the updates of MM. The proximal term $({\epsilon}/{2})\|{\mathbf{x}}-{\mathbf{x}}_{t}\|^{2}$ is added to keep the updated variable ${\mathbf{x}}_{t+1}$ close to the previous iterate ${\mathbf{x}}_{t}$. This does not affect convergence guarantees but improves computational stability.

The primal update in (6) may be computationally costly – because it requires solving a convex program – and cannot be implemented in a decentralized manner – because the augmentation term $({1}/{2\alpha)}{\mathbf{x}}^{T}({\mathbf{I}}-{\mathbf{Z}}){\mathbf{x}}$ in (5) is not separable. In the following section we propose an approximation of PMM that makes the minimization in (6) computationally economic and separable over nodes of the network. This leads to the set of decentralized updates that define the ESOM algorithm.

III ESOM: Exact Second-Order Method

To reduce the computational complexity of (6) and obtain a separable update we introduce a second order approximation of the augmented Lagrangian in (5). Consider then the second order Taylor’s expansion ${\mathcal{L}}({\mathbf{x}},{\mathbf{v}}_{t})\approx{\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})+\nabla_{\mathbf{x}}{\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})^{T}({\mathbf{x}}-{\mathbf{x}}_{t})+({1/2})({\mathbf{x}}-{\mathbf{x}}_{t})^{T}\nabla^{2}_{\mathbf{x}}{\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})({\mathbf{x}}-{\mathbf{x}}_{t})$ of the augmented Lagrangian with respect to ${\mathbf{x}}$ centered around $({\mathbf{x}}_{t},{\mathbf{v}}_{t})$. Using this approximation in lieu of ${\mathcal{L}}({\mathbf{x}},{\mathbf{v}}_{t})$ in (6) leads to the primal update

and considering the explicit form of the augmented Lagrangian gradient $\nabla_{\mathbf{x}}{\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})$ [cf. (5)] it follows that the variable ${\mathbf{x}}_{t+1}$ in (8) is given by

To resolve this issue, we use a Hessian inverse approximation that is built on truncating the Taylor’s series of the Hessian inverse ${\mathbf{H}}_{t}^{-1}$ as in . To do so, we try to decompose the Hessian as ${\mathbf{H}}_{t}={\mathbf{D}}_{t}-{\mathbf{B}}$ where ${\mathbf{D}}_{t}$ is a block diagonal positive definite matrix and ${\mathbf{B}}$ is a neighbor sparse positive semidefinite matrix. In particular, define ${\mathbf{D}}_{t}$ as

where ${\mathbf{Z}}_{d}:=\text{diag}({\mathbf{Z}})$. Observing the definitions of the matrices ${\mathbf{H}}_{t}$ and ${\mathbf{D}}_{t}$ and considering the relation ${\mathbf{B}}={\mathbf{D}}_{t}-{\mathbf{H}}_{t}$ we conclude that ${\mathbf{B}}$ is given by

We introduce the Exact Second-Order Method (ESOM) as a second order method for solving decentralized optimization problems which substitutes the Hessian inverse in update (10) by its $K$ block neighbor sparse approximation ${\hat{\mathbf{H}}}_{k}^{-1}(K)$ defined in (13). Therefore, the primal update of ESOM is

The ESOM dual update is identical to the update in (7),

Notice that ESOM is different from PMM in approximating the augmented Lagrangian in the primal update of PMM by a second order approximation. Further, ESOM approximates the Hessian inverse of the augmented Lagrangian by truncating the Taylor’s series of the Hessian inverse which is not necessarily neighbor sparse. In the following subsection we study the implantation details of the updates in (14) and (15).

The updates in (14) and (15) show that ESOM is a second order approximation of PMM. Although these updates are necessary for understanding the rationale behind ESOM, they are not implementable in a decentralized fashion since the matrix $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$ is not neighbor sparse. To resolve this issue, define the sequence of variables ${\mathbf{q}}_{t}$ as ${\mathbf{q}}_{t}:=({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{v}}_{t}$. Considering the definition of ${\mathbf{q}}_{t}$, the primal update in (14) can be written as

By multiplying the dual update in (15) by $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$ from the left hand side and using the definition ${\mathbf{q}}_{t}:=({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{v}}_{t}$ we obtain that

Notice that the system of updates in (16) and (17) is equivalent to the updates in (14) and (15), i.e., the sequences of variables ${\mathbf{x}}_{t}$ generated by them are identical. Nodes can implement the primal-dual updates in (16) and (17) in a decentralized manner, since the squared root matrix $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$ is eliminated from the updates and nodes can compute the products $({\mathbf{I}}-{\mathbf{Z}}){\mathbf{x}}_{t}$ and $({\mathbf{I}}-{\mathbf{Z}}){\mathbf{x}}_{t+1}$ by exchanging information with their neighbors.

To characterize the local update of each node for implementing the updates in (16) and (17), define

as the gradient of the augmented Lagrangian in (5). Further, define the primal descent direction ${\mathbf{d}}_{t}(K)$ with $K$ levels of approximation as

which implies that the update in (16) can be written as ${\mathbf{x}}_{t+1}={\mathbf{x}}_{t}+{\mathbf{d}}_{t}(K)$. Based on the mechanism of the Hessian inverse approximation in (13), the descent directions ${\mathbf{d}}_{t}(k)$ and ${\mathbf{d}}_{t}(k+1)$ satisfy the condition

Define ${\mathbf{d}}_{i,t}{(k)}$ as the descent direction of node $i$ at step $t$ which is the $i$th element of the global descent direction ${\mathbf{d}}_{t}{(k)}=[{\mathbf{d}}_{1,t}{(k)};\dots;{\mathbf{d}}_{n,t}{(k)}]$. Therefore, the localized version of the relation in (20) at node $i$ is given by

The update in (21) shows that node $i$ can compute its $(k+1)$th descent direction ${\mathbf{d}}_{i,t}{(k+1)}$ if it has access to the $k$th descent direction ${\mathbf{d}}_{i,t}(k)$ of itself and its neighbors ${\mathbf{d}}_{j,t}(k)$ for $j\in{\mathcal{N}}_{i}$. Thus, if nodes initialize with the ESOM- descent direction ${\mathbf{d}}_{i,t}{(0)}=-{\mathbf{D}}_{ii,t}^{-1}{\mathbf{g}}_{i,t}$ and exchange their descent directions with their neighbors for $K$ rounds and use the update in (21), they can compute their local ESOM-$K$ descent direction ${\mathbf{d}}_{i,t}{(K)}$. Notice that the $i$th diagonal block ${\mathbf{D}}_{t}$ is given by ${\mathbf{D}}_{ii,t}:=\nabla^{2}f_{i}({\mathbf{x}}_{i,t})+(2\alpha(1-w_{ii})+\epsilon){\mathbf{I}}$, where ${\mathbf{x}}_{i,t}$ is the primal variable of node $i$ at step $t$. Thus, the block ${\mathbf{D}}_{ii,t}$ is locally available at node $i$. Moreover, node $i$ can evaluate the blocks ${\mathbf{B}}_{ii}=\alpha(1-w_{ii}){\mathbf{I}}$ and ${\mathbf{B}}_{ij}=\alpha w_{ij}{\mathbf{I}}$ without extra communication. In addition, nodes can compute the gradient ${\mathbf{g}}_{t}$ by communicating with their neighbors. To confirm this claim observe that the $i$th element of ${\mathbf{g}}_{t}=[{\mathbf{g}}_{1,t};\dots;{\mathbf{g}}_{n,t}]$ associated with node $i$ is given by

which requires access to the local primal variable ${\mathbf{x}}_{j,t+1}$ of the neighboring nodes $j\in{\mathcal{N}}_{i}$.

The steps of ESOM-$K$ are summarized in Algorithm 1. The core steps are Steps 5-9 which correspond to computing the ESOM-$K$ primal descent direction ${\mathbf{d}}_{i,t}(K)$. In Step 5, Each node computes its initial descent direction ${\mathbf{d}}_{i,t}(0)$ using the block ${\mathbf{D}}_{ii,t}$ and the local gradient ${\mathbf{g}}_{i,t}$ computed in Steps 3 and 4, respectively. Steps 7 and 8 correspond to the recursion in (21). In step 7, nodes exchange their $k$th level descent direction ${\mathbf{d}}_{i,t}(k)$ with their neighboring nodes to compute the $(k+1)$th descent direction ${\mathbf{d}}_{i,t}(k+1)$ in Step 8. The outcome of this recursion is the $K$th level descent direction ${\mathbf{d}}_{i,t}(K)$ which is required for the update of the primal variable ${\mathbf{x}}_{i,t}$ in Step 10. Notice that the blocks of the neighbor sparse matrix ${\mathbf{B}}$, which are required for step 8, are computed and stored in Step 1. After updating the primal variables in Step 10, nodes exchange their updated variables ${\mathbf{x}}_{i,t+1}$ with their neighbors $j\in{\mathcal{N}}_{i}$ in Step 11. By having access to the decision variable of neighboring nodes, nodes update their local dual variable ${\mathbf{q}}_{i,t}$ in Step 12.

The proposed ESOM algorithm solves problem (4) in the dual domain by defining the proximal augmented Lagrangian. It is also possible to solve problem (4) in the primal domain by solving a penalty version of (4). In particular, by using the quadratic penalty function $(1/2)\|.\|^{2}$ for the constraint $({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{x}}$ with penalty coefficient $\alpha$, we obtain the penalized version of (4)

where ${\hat{\mathbf{x}}}^{*}$ is the optimal argument of the penalized objective function. Notice that ${\hat{\mathbf{x}}}^{*}$ is not equal to the optimal argument ${\mathbf{x}}^{*}$ and the distance $\|{\mathbf{x}}^{*}-{\hat{\mathbf{x}}}^{*}\|$ is in the order of $O(1/\alpha)$. The objective function in (24) can be minimized by descending through the gradient descent direction which leads to the update of decentralized gradient descent (DGD) . The convergence of DGD can be improved by using Newton’s method. Notice that the Hessian of the objective function in (24) is given by

The Hessian ${\hat{\mathbf{H}}}$ in (25) is identical to the Hessian ${\mathbf{H}}$ in (9) except for the term $\epsilon{\mathbf{I}}$. Therefore, the same technique for approximating the Hessian inverse ${\hat{\mathbf{H}}}^{-1}$ can be used to approximate the Newton direction of the penalized objective function in (24) which leads to the update of the Network Newton (NN) methods . Thus, ESOM and NN use an approximate decentralized variation of Newton’s method for solving two different problems. In other words, ESOM uses the approximate Newton direction for minimizing the augmented Lagrangian of (4), while NN solves a penalized version of (4) using this approximation. This difference justifies the reason that the sequence of iterates generated by ESOM converges to the optimal argument ${\mathbf{x}}^{*}$ (Section IV), while NN converges to a neighborhood of ${\mathbf{x}}^{*}$.

ESOM approximates the augmented Lagrangian ${\mathcal{L}}({\mathbf{x}},{\mathbf{v}})$ in (6) by its second order approximation. If we substitute the augmented Lagrangian by its first order approximation we can recover the update of EXTRA proposed in . To be more precise, we can substitute ${\mathcal{L}}({\mathbf{x}},{\mathbf{v}}_{t})$ by its first order approximation ${\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})+\nabla{\mathcal{L}}({\mathbf{x}}_{t},{\mathbf{v}}_{t})^{T}({\mathbf{x}}-{\mathbf{x}}_{t})$ near the point $({\mathbf{x}}_{t},{\mathbf{v}}_{t})$ to update the primal variable ${\mathbf{x}}$. Considering this substitution and the definition of the augmented Lagrangian in (5) It follows that the update for the primal variable ${\mathbf{x}}$ can be written as

By subtracting the update at step $t-1$ from the update at step $t$ and using the dual variables relation that ${\mathbf{v}}_{t+1}={\mathbf{v}}_{t}+\alpha({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{x}}_{t+1}$ we obtain the update

The update in (27) shows a first-order approximation of the PMM. It is not hard to show that for specific choices of $\alpha$ and $\epsilon$, the update in (27) is equivalent to the update of EXTRA in . Thus, we expect to observe faster convergence for ESOM relative to EXTRA as it incorporates second-order information. This advantage is studied in Section V.

IV Convergence Analysis

In this section we study convergence rates of PMM and ESOM. First, we show that the sequence of iterates ${\mathbf{x}}_{t}$ generated by PMM converges linearly to the optimal argument ${\mathbf{x}}^{*}$. Although, PMM cannot be implemented in a decentralized fashion, its convergence rate can be used as a benchmark for evaluating performance of ESOM. We then follow the section by analyzing convergence properties ESOM. We show that ESOM exhibits a linear convergence rate and compare its factor of linear convergence with the linear convergence factor of PMM. In proving these results we consider the following assumptions.

The local objective functions $f_{i}({\mathbf{x}})$ are twice differentiable and the eigenvalues of the local objective functions Hessian $\nabla^{2}f({\mathbf{x}})$ are bounded by positive constants $0<m\leq M<\infty$, i.e.

The lower bound in (28) is equivalent to the condition that the local objective functions $f_{i}$ are strongly convex with constant $m>0$. The upper bound for the eigenvalues of the Hessians $\nabla^{2}f_{i}$ implies that the gradients of the local objective functions $\nabla f_{i}$ are Lipschitz continuous with constant $M$. Notice that the global objective function $\nabla^{2}f({\mathbf{x}})$ is a block diagonal matrix where its $i$th diagonal block is $\nabla^{2}f_{i}({\mathbf{x}}_{i})$. Therefore, the bounds on the eigenvalues of the local Hessians $\nabla^{2}f_{i}({\mathbf{x}}_{i})$ in (28) also hold for the global objective function Hessian $\nabla^{2}f({\mathbf{x}})$. I.e.,

Convergence rate of PMM can be considered as a benchmark for the convergence rate of ESOM. To establish linear convergence of PMM, We first study the relationship between the primal ${\mathbf{x}}$ and dual ${\mathbf{v}}$ iterates generated by PMM and the optimal arguments ${\mathbf{x}}^{*}$ and ${\mathbf{v}}^{*}$ in the following lemma.

Consider the updates for the proximal method of multipliers in (6) and (7). The sequences of primal and dual iterates generated by PMM satisfy

Notice that the sequence ${\mathbf{u}}_{t}$ is the concatenation of the dual variable ${\mathbf{v}}_{t}$ and primal variable ${\mathbf{x}}_{t}$. Likewise, we can define ${\mathbf{u}}^{*}$ as the concatenation of the optimal arguments ${\mathbf{v}}^{*}$ and ${\mathbf{x}}^{*}$. We proceed to prove that the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ converges linearly to null. Observe that $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ can be simplified as $\|{\mathbf{v}}_{t}-{\mathbf{v}}^{*}\|^{2}+\alpha\epsilon\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}$. This observation shows that $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ is a Lyapunov function of the primal $\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}$ and dual $\|{\mathbf{v}}_{t}-{\mathbf{v}}^{*}\|^{2}$ errors. Therefore, linear convergence of the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ implies linear convergence of the sequence $\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}$. In the following theorem, we show that the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ converges to zero at a linear rate.

Consider the proximal method of multipliers as introduced in (6) and (7). Consider $\beta>1$ as an arbitrary constant strictly larger than $1$ and define ${\hat{\lambda}_{\min}}({\mathbf{I}}-{\mathbf{Z}})$ as the smallest non-zero eigenvalue of the matrix ${\mathbf{I}}-{\mathbf{Z}}$. Further, recall the definitions of the vector ${\mathbf{u}}$ and matrix $\mathcal{G}$ in (32). If Assumption 1 holds, then the sequence of Lyapunov functions $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ generated by PMM satisfies

The result in Theorem 1 shows linear convergence of the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ generated by PMM where the factor of linear convergence is $1/(1+\delta)$. Observe that larger $\delta$ implies smaller linear convergence factor $1/(1+\delta)$ and faster convergence. Notice that all the terms in the minimization in (34) are positive and therefore the constant $\delta$ is strictly larger than 0. In addition, the result in Theorem 1 holds for any feasible set of parameters $\beta>1$, $\epsilon>0$, and $\alpha>0$; however, maximizing the parameter $\delta$ requires properly choosing the set of parameters $\beta$, $\epsilon$, and $\alpha$.

Observe that when the first positive eigenvalue ${\hat{\lambda}_{\min}}({\mathbf{I}}-{\mathbf{Z}})$ of the matrix ${\mathbf{I}}-{\mathbf{Z}}$ , which is the second smallest eigenvalue of ${\mathbf{I}}-{\mathbf{Z}}$, is small the constant $\delta$ becomes close to zero and convergence becomes slow. Notice that small ${\hat{\lambda}_{\min}}({\mathbf{I}}-{\mathbf{Z}})$ shows that the graph is not highly connected. This observation matches the intuition that when the graph has less edges the speed of convergence is slower. Additionally, the upper bounds in (34) show that when the condition number $M/m$ of the global objective function $f$ is large, $\delta$ becomes small and the linear convergence becomes slow.

Although PMM enjoys a fast linear convergence rate, each iteration of PMM requires infinite rounds of communications which makes it infeasible. In the following section, we study convergence properties of ESOM as a second order approximation of PMM that is implementable in decentralized settings.

IV-B Convergence of ESOM

Notice that ESOM is built on a second order approximation of the proximal augmented Lagrangian used in the update of PMM. To guarantee that the second order approximation suggested in ESOM is feasible, the local objective functions $f_{i}$ are required to be twice differentiable as assumed in Assumption 1. The twice differentiability of the local objective functions $f_{i}$ implies that the aggregate function $f$, which is the sum of a set of twice differentiable functions, is also twice differentiable. This observation shows that the global objective function $\nabla^{2}f({\mathbf{x}})$ is definable. Considering this observation, we prove some preliminary results for the iterates generated by ESOM in the following lemma.

where the error vector ${\mathbf{e}}_{t}$ is defined as

The observation that the vector ${\mathbf{e}}_{t}$ characterizes the error of second order approximation in ESOM, motivates analyzing an upper bound for the error vector norm $\|{\mathbf{e}}_{t}\|$. To prove that the norm $\|{\mathbf{e}}_{t}\|$ is bounded above we assume the following condition is satisfied.

The global objective function Hessian $\nabla^{2}f({\mathbf{x}})$ is Lipschitz continuous with constant $L$, i.e.,

The conditions imposed by Assumption 2 is customary in the analysis of second order methods; see, e.g., . In the following lemma we use the assumption in (38) to prove an upper bound for the error norm $\|{\mathbf{e}}_{t}\|$ in terms of the distance $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|$.

Consider ESOM as introduced in (8)-(15) and recall the definition of the error vector ${\mathbf{e}}_{t}$ in (37). Further, define $c>0$ as a lower bound for the local weights ${\mathbf{w}}_{ii}$. If Assumptions 1-2 hold, then the error vector norm $\|{\mathbf{e}}_{t}\|$ is bounded above by

and $\rho:={2\alpha(1-c)}/({2\alpha(1-c)+m+\epsilon})$.

First, note that the lower bound $c>0$ on the local weights $w_{ii}$ is implied from the fact that all the local weights are positive. In particular, we can define the lower bound $c$ as $c:=\min_{i}{w_{ii}}$. The result in (39) shows that the error of second order approximation in ESOM vanishes as the sequence of iterates ${\mathbf{x}}_{t}$ approaches the optimal argument ${\mathbf{x}}^{*}$. We will show in Theorem 2 that $\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|$ converges to zero which implies that the limit of the sequence $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|$ is zero.

Consider ESOM as introduced in (8)-(15). Consider $\beta>1$ and $\phi>1$ as arbitrary constants that are strictly larger than $1$, and $\zeta$ as a positive constant that is chosen from the interval $\zeta\in((m+M)/2mM,\epsilon/\Gamma_{t}^{2})$. Further, recall the definitions of the vector ${\mathbf{u}}$ and matrix $\mathcal{G}$ in (32) and consider ${\hat{\lambda}_{\min}}({\mathbf{I}}-{\mathbf{Z}})$ as the smallest non-zero eigenvalue of the matrix ${\mathbf{I}}-{\mathbf{Z}}$. If Assumptions 1-2 hold, then the sequence of Lyapunov functions $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ generated by ESOM satisfies

where the sequence $\delta^{\prime}_{t}$ is given by

The result in Theorem 2 shows linear convergence of the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ generated by ESOM where the factor of linear convergence is $1/(1+\delta^{\prime})$. Notice that the positive constant $\xi$ is chosen from the interval $((m+M)/2mM,\epsilon/\Gamma_{t}^{2})$. This interval is non-empty if and only if the proximal parameter $\epsilon$ satisfies the condition $\epsilon>\Gamma_{t}^{2}(m+M)/2mM$. It follows from the result in Theorem 2 that the sequence of primal variables ${\mathbf{x}}_{t}$ converges to the optimal argument ${\mathbf{x}}^{*}$ defined in (4).

Under the assumptions in Theorem 2, the sequence of squared errors $\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}$ generated by ESOM converges to zero at a linear rate, i.e.,

Proof : According to the definition of the sequence ${\mathbf{u}}_{t}$ and matrix $\mathcal{G}$, we can write $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}=\alpha\epsilon\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}+\|{\mathbf{v}}_{t}-{\mathbf{v}}^{*}\|^{2}$ which implies that $\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}\leq(1/\alpha\epsilon)\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$. Considering this result and linear convergence of the sequence $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ in (41), the claim in (43) follows. $\blacksquare$

IV-C Convergence rates comparison

The expression for $\delta^{\prime}_{t}$ in (42) verifies the intuition that the convergence rate of ESOM is slower than PMM. This is true, since the upper bounds for $\delta$ in PMM are larger than their equivalent upper bounds for $\delta^{\prime}_{t}$ in ESOM. We obtain that $\delta_{t}^{\prime}$ is smaller than $\delta$ which implies that the linear convergence factor $1/(1+\delta)$ of PMM is smaller than $1/(1+\delta^{\prime}_{t})$ for ESOM. Therefore, for all steps $t$, the linear convergence of PMM is faster than ESOM. Although, linear convergence factor of ESOM $1/(1+\delta^{\prime}_{t})$ is larger than $1/(1+\delta)$ for PMM, as time passes the gap between these two constants becomes smaller. In particular, notice that after a number of iterations $({L}/{2})\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|$ becomes smaller than $2M$ and $\Gamma_{t}$ can be simplified as

The term $(L/2)\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|$ eventually approaches zero, while the second term $({2(1-c)}/{\alpha}+M+\epsilon)\rho^{K+1}$ is constant. Although, the second term is not approaching zero, by proper choice of $\rho$ and $K$, this term can become arbitrary close to zero. Notice that when $\Gamma_{t}$ approaches zero, if we set $\zeta=1/\Gamma_{t}$ the upper bounds in (42) for $\delta_{t}^{\prime}$ approach the upper bounds for $\delta$ of PMM in (34).

Therefore, as time passes $\Gamma_{t}$ becomes smaller and the factor of linear convergence for ESOM $1/(1+\delta^{\prime}_{t})$ becomes closer to the linear convergence factor of PMM $1/(1+\delta)$.

V Numerical Experiments

In this section we compare the performances of ESOM, EXTRA, Decentralized (D)ADMM, and Network Newton (NN). First we consider a linear least squares problem and then we use the mentioned methods to solve a logistic regression problem.

The network in this experiment is randomly generated with connectivity ratio $r={3}/{n}$, where $r$ is defined as the number of edges divided by the number of all possible ones, ${n(n-1)}/{2}$. We set $n=20$, $p=5$, and $m_{i}=5\ \text{for all}\ i=1,\dots,n$. The vectors ${\mathbf{y}}_{i}$ and matrices ${\mathbf{M}}_{i}$ as well as the noise vectors $\boldsymbol{\nu}_{(i)}$, $\text{for all}\ i$ are generated following the standard normal distribution. We precondition the aggregated data matrices ${\mathbf{M}}_{i}$ so that the condition number of the problem is $10$. The decision variables ${\mathbf{x}}_{i}$ are initialized as ${\mathbf{x}}_{i,0}=0$ for all nodes $i=1,\dots,n$ and the initial distance to the optimal is $\|{\mathbf{x}}_{i,0}-{\mathbf{x}}^{*}\|=100$.

We use Metropolis constant edge weight matrix as the mixing matrix ${\mathbf{W}}$ in all experiments. We run PMM, EXTRA, and ESOM-$K$ with fixed hand-optimized stepsizes $\alpha$. The best choices of $\alpha$ for ESOM-0, ESOM-1, and ESOM-2 are $\alpha=0.03$, $\alpha=0.04$, and $\alpha=0.05$, respectively. The stepsize $\alpha=0.1$ leads to the best performance for EXTRA which is considered in the numerical experiments. Notice that for variations of NN-$K$, there is no optimal choice of stepsize – smaller stepsize leads to more accurate but slow convergence, while large stepsize accelerates the convergence but to a less accurate neighborhood of the optimal solution. Therefore, for NN-0, NN-1, and NN-2 we set $\alpha=0.001$, $\alpha=0.008$, and $\alpha=0.02$, respectively. Although the PMM algorithm is not implementable in a decentralized fashion, we use its convergence path – which is generated in a centralized manner – as our benchmark. The choice of stepsize for PMM is $\alpha=2$.

EXTRA requires one round of communications per iteration, while NN-$K$ and ESOM-$K$ require $K+1$ rounds of local communications per iteration. Thus, convergence paths of these methods in terms of rounds of communications might be different from the ones in Fig. 1. The convergence paths of NN, ESOM, EXTRA in terms of rounds of local communications are shown in Fig. 2. In this plot we ignore PMM, since it requires infinite rounds of communications per iteration. The main difference between Figs. 1 and 2 is in the performances of ESOM-, ESOM-$1$, and ESOM-$2$. All of the variations of ESOM outperform EXTRA in terms of rounds of communications, while the best performance belongs to ESOM-. This observation shows that increasing the approximation level $K$ does not necessary improve the performance of ESOM-$K$ in terms of communication cost.

V-B Decentralized logistic regression

We consider the application of ESOM for solving a logistic regression problem in a form

Fig. 3 and Fig 4 showcase the convergence paths of ESOM-, ESOM-$1$, ESOM-$2$, EXTRA, and DADMM versus number of iterations and rounds of communications, respectively. The results match the observations for the least squares problem in Fig. 1 and Fig. 2. Different versions of ESOM-$K$ converge faster than EXTRA both in terms of communication cost and number of iterations. Moreover, ESOM-$2$ converges faster than ESOM-$1$ and ESOM- in terms of number of iterations, while ESOM- has the best performance in terms of communication cost for achieving a target accuracy. Comparing the convergence paths of ESOM-, ESOM-$1$, and ESOM-$2$ with DADMM shows that number of iterations required for the convergence of DADMM is larger than the required iterations for ESOM-, ESOM-$1$, and ESOM-$2$. In terms of communication cost, DADMM has a better performance relative to ESOM-$1$ and ESOM-$2$, while ESOM- is the most efficient algorithm.

VI Conclusions

We studied the consensus optimization problem where the components of a global objective function are available at different nodes of a network. We proposed an Exact Second-Order Method (ESOM) that converges to the optimal argument of the global objective function at a linear rate. We developed the update of ESOM by substituting the primal update of Proximal Method of Multipliers (PMM) with its second order approximation. Moreover, we approximated the Hessian inverse of the proximal augmented Lagrangian by truncating its Taylor’s series. This approximation leads to a class of algorithms ESOM-$K$ where $K+1$ indicates the number of Taylor’s series terms that are used for Hessian inverse approximation. Convergence analysis of ESOM-$K$ shows that the sequence of iterates converges to the optimal argument linearly irrespective to the choice of $K$. We showed that the linear convergence factor of ESOM-$K$ is a function of time and the choice of $K$. The linear convergence factor of ESOM approaches the linear convergence factor of PMM as time passes. Moreover, larger choice of $K$ makes the factor of linear convergence for ESOM closer to the one for PMM. Numerical results verify the theoretical linear convergence and the relation between the linear convergence factor of ESOM-$K$ and PMM. Further, we observed that larger choice of $K$ for ESOM-$K$ leads to faster convergence in terms of number of iterations, while the most efficient version of ESOM-$K$ in terms of communication cost is ESOM-.

Appendix A Proof of Lemma 1

Consider the updates of PMM in (6) and (7). According to (4), the optimal argument ${\mathbf{x}}^{*}$ satisfies the condition $({\mathbf{I}}-{\mathbf{Z}})^{1/2}{\mathbf{x}}^{*}={\mathbf{0}}$. This observation in conjunction with the dual variable update in (7) yields the claim in (30).

To prove the claim in (31), note that the optimality condition of (6) implies $\nabla_{\mathbf{x}}{\mathcal{L}}({\mathbf{x}}_{t+1},{\mathbf{v}}_{t})+\epsilon({\mathbf{x}}_{t+1}-{\mathbf{x}}_{t})={\mathbf{0}}$. Based on the definition of the Lagrangian ${\mathcal{L}}({\mathbf{x}},{\mathbf{v}})$ in (5), the optimality condition for the primal update of PMM can be written as

Further, notice that one of the KKT conditions of the optimization problem in (4) is

Subtracting the equalities in (49) and (50) from (48) yields

Regrouping the terms in (30) implies that ${\mathbf{v}}_{t}$ is equivalent to

Substituting ${\mathbf{v}}_{t}$ in (51) by the expression in the right hand side of (52) follows the claim in (31).

Appendix B Proof of Theorem 1

According to Assumption 1, the global objective function $f$ is strongly convex with constant $m$ and its gradients $\nabla f$ are Lipschitz continuous with constant $M$. Considering these assumptions, we obtain that the inner product $({\mathbf{x}}_{t+1}-{\mathbf{x}}^{*})^{T}({\nabla f}({\mathbf{x}}_{t+1})-{\nabla f}({\mathbf{x}}^{*}))$ is lower bounded by

The result in (31) shows that the difference ${\nabla f}({\mathbf{x}}_{t+1})-{\nabla f}({\mathbf{x}}^{*})$ is equal to $-({\mathbf{I}}-{\mathbf{Z}})^{1/2}({\mathbf{v}}_{t+1}-{\mathbf{v}}^{*})-\epsilon({\mathbf{x}}_{t+1}-{\mathbf{x}}_{t})$. Apply this substitution into (53) and multiply both sides of the resulted inequality by $2$ to obtain

Based on the result in (30), we can substitute $({\mathbf{x}}_{t+1}-{\mathbf{x}}^{*})^{T}({\mathbf{I}}-{\mathbf{Z}})^{1/2}$ by $(1/\alpha)({\mathbf{v}}_{t+1}-{\mathbf{v}}_{t})^{T}$. Thus, we can rewrite (B) as

Notice that for any vectors ${\mathbf{a}}$, ${\mathbf{b}}$, and ${\mathbf{c}}$ we can write

By setting ${\mathbf{a}}={\mathbf{v}}_{t+1}$, ${\mathbf{b}}={\mathbf{v}}_{t}$, and ${\mathbf{c}}={\mathbf{v}}^{*}$ we obtain that the inner product $2({\mathbf{v}}_{t+1}-{\mathbf{v}}_{t})^{T}({\mathbf{v}}_{t+1}-{\mathbf{v}}^{*})$ in (55) can be written as $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}_{t}\|^{2}+\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}-\|{\mathbf{v}}_{t}-{\mathbf{v}}^{*}\|^{2}$. Likewise, setting ${\mathbf{a}}={\mathbf{x}}_{t+1}$, ${\mathbf{b}}={\mathbf{x}}_{t}$, and ${\mathbf{c}}={\mathbf{x}}^{*}$ implies that the inner product $2({\mathbf{x}}_{t+1}-{\mathbf{x}}_{t})^{T}({\mathbf{x}}_{t+1}-{\mathbf{x}}^{*})$ in (55) is equal to $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|^{2}+\|{\mathbf{x}}_{t+1}-{\mathbf{x}}^{*}\|^{2}-\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}$. Applying these simplifications into (55) yields

Now using the definitions of the variable ${\mathbf{u}}$ and matrix $\mathcal{G}$ in (32) we can substitute $\|{\mathbf{v}}_{t}-{\mathbf{v}}^{*}\|^{2}-\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}+\alpha\epsilon\|{\mathbf{x}}_{t}-{\mathbf{x}}^{*}\|^{2}-\alpha\epsilon\|{\mathbf{x}}_{t+1}-{\mathbf{x}}^{*}\|^{2}$ by $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$. Moreover, the squared norm $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}_{t}\|^{2}$ is equivalent to $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}^{*}\|_{\alpha^{2}({\mathbf{I}}-{\mathbf{Z}})}^{2}$ based on the result in (30). By applying these substitutions we can rewrite (B) as

Regrouping the terms in (B) leads to the following lower bound for the difference $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$,

Observe that the result in (B) provides a lower bound for the decrement $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$. To prove the claim in (33), we need to show that for a positive constant $\delta$ we have $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}\geq\delta\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$. Therefore, the inequality in (33) is satisfied if we can show that the lower bound in (B) is greater than $\delta\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ or equivalently

To prove that the inequality in (B) for some $\delta>0$, we first find an upper bound for the squared norm $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}$ in terms of the summands in the right hand side of (B). To do so, consider the relation (31) along with the fact that ${\mathbf{v}}_{t+1}$ and ${\mathbf{v}}^{*}$ both lying in the column space of $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$. It follows that $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}$ is bounded above by

where $\beta>1$ is a tunable free parameter and ${\hat{\lambda}_{\min}}({\mathbf{I}}-{\mathbf{Z}})$ is the smallest non-zero eigenvalue of ${\mathbf{I}}-{\mathbf{Z}}$. Considering the result in (61) to satisfy the inequality in (B), which is a sufficient condition for the claim in (33), it remains to show that

To enable (B) and consequently enabling (B), we only need to verify that there exists $\delta>0$ such that

The conditions in (63) are satisfied if the constant $\delta$ is chosen as in (34). Therefore, for $\delta$ in (34) the claim in (B) holds, which implies the claim in (33).

Appendix C Proof of Lemma 2

Consider the primal update of ESOM in (14). By regrouping the terms we obtain that

Now using the definition of the error vector ${\mathbf{e}}_{t}$ in (37) we can rewrite (65) as

Notice that the result in (66) is identical to the expression for PMM in (48) except for the error term ${\mathbf{e}}_{t}$. To prove the claim in (36) from (66), it remains to follow the steps in (49)-(52).

Appendix D Proof of Lemma 3

To prove the result in (39), we first use the result in Proposition 2 of . It shows that when the eigenvalues of the Hessian $\nabla^{2}f({\mathbf{x}})$ are bounded above by $M$ and the Hessian is Lipschitz continuous with constant $L$ we can write

Observe that the matrices ${\mathbf{B}}$ and ${\mathbf{D}}_{t}$ in this paper are different from the ones in , but the analyses of them are very similar. Similar to the proof of Proposition 2 in we define ${\hat{\mathbf{D}}}:=2\alpha({\mathbf{I}}-{\mathbf{Z}}_{d})$. Notice that the matrix ${\hat{\mathbf{D}}}$ is bock diagonal where its $i$th diagonal block is $2\alpha(1-w_{ii}){\mathbf{I}}_{p}$. Thus, ${\hat{\mathbf{D}}}$ is positive definite and invertible. Hence, We are allowed to write the product ${\mathbf{B}}{\mathbf{D}}_{t}^{-1}$ as

The next step is to find an upper bound for the eigenvalues of ${\mathbf{B}}{\hat{\mathbf{D}}}^{-1}$ in (70). Based on the definitions of matrices ${\mathbf{B}}$ and ${\hat{\mathbf{D}}}$, the product ${\mathbf{B}}{\hat{\mathbf{D}}}^{-1}$ is given by

According to the result in Proposition 2 of , the eigenvalues of the matrix $({\mathbf{I}}-2{\mathbf{Z}}_{d}+{\mathbf{Z}})(2({\mathbf{I}}-{\mathbf{Z}}_{d}))^{-1}$ are uniformly bounded by and $1$. Thus, we obtain that

According to the definitions of the matrices ${\hat{\mathbf{D}}}$ and ${\mathbf{D}}_{t}$, the product ${\hat{\mathbf{D}}}^{1/2}{\mathbf{D}}_{t}^{-1/2}$ is block diagonal and the $i$th diagonal block is given by

Based on Assumption 1, the eigenvalues of the local Hessians $\nabla^{2}f_{i}({\mathbf{x}}_{i})$ are bounded by $m$ and $M$. Further, notice that the diagonal elements $w_{ii}$ of the weight matrix ${\mathbf{W}}$ are bounded below by $c$. Considering these bounds, we can show that the eigenvalues of the matrices $(1/2\alpha(1-w_{ii}))(\nabla^{2}f_{i}({\mathbf{x}}_{i,t})+\epsilon{\mathbf{I}})+{\mathbf{I}}$ for all $i=1,\dots,n$ are bounded below by

By considering the bounds in (74), the eigenvalues of each block of the matrix ${\hat{\mathbf{D}}}{\mathbf{D}}_{t}^{-1}$, introduced in (73), are bounded above as

The upper bound in (75) for the eigenvalues of each diagonal block of the matrix ${\hat{\mathbf{D}}}{\mathbf{D}}_{t}^{-1}$ implies that the matrix norm $\|{\hat{\mathbf{D}}}{\mathbf{D}}_{t}^{-1}\|$ is bounded above by

Considering the upper bounds in (72) and (76) and the relation in (70) we obtain that

Notice that according to the result in Proposition 1 of , the matrix $\left({\mathbf{I}}-2{\mathbf{Z}}_{d}+{\mathbf{Z}}\right)$ is positive semidefinite which implies that ${\mathbf{B}}=\alpha\left({\mathbf{I}}-2{\mathbf{Z}}_{d}+{\mathbf{Z}}\right)$ is also positive semidefinite. Thus, all the $K$ summands in (79) are positive semidefinite and as a result we obtain that

The eigenvalues of ${\mathbf{I}}-{\mathbf{Z}}_{d}$ are bounded above by $1-c$, since all the local weights $w_{ii}$ are larger than $c$. This observation in conjunction with the strong convexity of the global objective function $f$ implies that the eigenvalues of ${\mathbf{D}}_{t}=\nabla^{2}f({\mathbf{x}}_{t})+\epsilon{\mathbf{I}}+2\alpha({\mathbf{I}}-{\mathbf{Z}}_{d})$ are bounded above by $M+\epsilon+2\alpha(1-c)$. Therefore,

Observing the inequalities in (67) and (83) and using the triangle inequality the claim in (39) follows.

Appendix E Proof of Theorem 2

Notice that in proving the claim in (41) we use some of the steps in the proof of Theorem 1 to avoid rewriting similar equations. First, note that according to the result in (36), the difference $\nabla f({\mathbf{x}}_{t+1})-\nabla f({\mathbf{x}}^{*})$ for the ESOM method can be written as

Now recall the the inequality in (53) and substitute the gradients difference $\nabla f({\mathbf{x}}_{t+1})-\nabla f({\mathbf{x}}^{*})$ in the inner product $({\mathbf{x}}_{t+1}-{\mathbf{x}}^{*})^{T}({\nabla f}({\mathbf{x}}_{t+1})-{\nabla f}({\mathbf{x}}^{*}))$ by the expression in the right hand side of (84). Applying this substitution and multiplying both sides of the implied inequality by $2\alpha$ follows

By following the steps in (B)-(B), the result in (E) leads to a lower bound for the difference $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ as

Notice that the inner product $2({\mathbf{x}}_{t+1}-{\mathbf{x}}^{*})^{T}{\mathbf{e}}_{t}$ is bounded below by $-(1/\zeta)\|{\mathbf{x}}_{t+1}-{\mathbf{x}}^{*}\|^{2}-\zeta\|{\mathbf{e}}_{t}\|^{2}$ for any positive constant $\zeta>0$. Therefore, the lower bound in (E) can be updated as

In order to establish (41), we need to show that the difference $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ is bounded below by $\delta_{t}^{\prime}\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$. To do so, we show that the lower bound for $\|{\mathbf{u}}_{t}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}-\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$ in (E) is larger than $\delta_{t}^{\prime}\|{\mathbf{u}}_{t+1}-{\mathbf{u}}^{*}\|_{\mathcal{G}}^{2}$, i.e.,

We proceed to find an upper bound for the squared norm $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}$ in terms of the summands in the right hand side of (E). Consider the relation (66) as well as the fact that ${\mathbf{v}}_{t+1}$ and ${\mathbf{v}}^{*}$ both lie in the column space of $({\mathbf{I}}-{\mathbf{Z}})^{1/2}$. It follows that $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}$ is bounded above by

By substituting the upper bound in (E) for the squared norm $\|{\mathbf{v}}_{t+1}-{\mathbf{v}}^{*}\|^{2}$ in (E) we obtain a sufficient condition for the result in (E) which is given by

Substitute the squared norm $\|{\mathbf{e}}_{t}\|^{2}$ terms in (E) by the upper bound in (39). It follows from this substitution and regrouping the terms that

Notice that if the inequality in (E) is satisfied, then the result in (E) holds which implies the result in (E) and the linear convergence claim in (41). To satisfy the inequality in (E) we need to make sure that the coefficients of the terms $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}_{t}\|^{2}$, $\|{\mathbf{x}}_{t+1}-{\mathbf{x}}^{*}\|^{2}$, and $\|{\nabla f}({\mathbf{x}}_{t+1})-{\nabla f}({\mathbf{x}}^{*})\|^{2}$ are non-negative. Therefore, the inequality in (E) holds if $\delta_{t}^{\prime}$ satisfies

The conditions in (92) are satisfied if $\delta_{t}^{\prime}$ is chosen as in (42). Thus, $\delta_{t}^{\prime}$ in (42) satisfies the conditions in (92) and the claim in (41) holds.

References