EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization

Introduction

This paper focuses on decentralized consensus optimization, a problem defined on a connected network and solved by $n$ agents cooperatively

Problems of the form (1) that require decentralized computation are found widely in various scientific and engineering areas including sensor network information processing, multiple-agent control and coordination, as well as distributed machine learning. Examples and works include decentralized averaging , learning , estimation , sparse optimization , and low-rank matrix completion problems. Functions $f_{i}$ can take forms of least squares , regularized least squares , as well as more general ones . The solution $x$ can represent, for example, the average temperature of a room , frequency-domain occupancy of spectra , states of a smart grid system , sparse vectors , and a matrix factor and so on. In general, decentralized optimization fits the scenarios in which the data is collected and/or stored in a distributed network, a fusion center is either infeasible or not economical, and/or computing is required to be performed in a decentralized and collaborative manner by multiple agents.

Existing first-order decentralized methods for solving (1) include the (sub)gradient method , the (sub)gradient-push method , the fast (sub)gradient method , and the dual averaging method . Compared to classical centralized algorithms, decentralized algorithms encounter more restrictive assumptions and typically worse convergence rates. Most of the above algorithms are analyzed under the assumption of bounded (sub)gradients. Work assumes bounded Hessian for strongly convex functions. Recent work relaxes such assumptions for decentralized gradient descent. When (1) has additional constraints that force $x$ in a bounded set, which also leads to bounded (sub)gradients and Hessian, projected first-order algorithms are applicable .

When using a fixed step size, these algorithms do not converge to a solution $x^{*}$ of problem (1) but a point in its neighborhood no matter whether $f_{i}$’s are differentiable or not . This motivates the use of certain diminishing step sizes in to guarantee convergence to $x^{*}$. The rates of convergence are generally weaker than their analogues in centralized computation. For the general convex case and under the bounded (sub)gradient (or Lipschitz–continuous objective) assumption, shows that diminishing step sizes $\alpha_{k}=\frac{1}{\sqrt{k}}$ lead to a convergence rate of $O\left(\frac{\ln{k}}{\sqrt{k}}\right)$ in terms of the running best of objective error, and shows that the dual averaging method has a rate of $O\left(\frac{\ln k}{\sqrt{k}}\right)$ in the ergodic sense in terms of objective error. For the general convex case, under assumptions of fixed step size and Lipschitz continuous, bounded gradient, shows an outer–loop convergence rate of $O\left(\frac{1}{k^{2}}\right)$ in terms of objective error, utilizing Nesterov’s acceleration, provided that the inner loop performs substantial consensus computation, without which diminishing step sizes $\alpha_{k}=\frac{1}{k^{1/3}}$ lead to a reduced rate of $O\left(\frac{\ln{k}}{k}\right)$. The (sub)gradient-push method can be implemented in a dynamic digraph and, under the bounded (sub)gradient assumption and diminishing step sizes $\alpha_{k}=O\left(\frac{1}{\sqrt{k}}\right)$, has a rate of $O\left(\frac{\ln{k}}{\sqrt{k}}\right)$ in the ergodic sense in terms of objective error. A better rate of $O\left(\frac{\ln{k}}{k}\right)$ is proved for the (sub)gradient-push method in under the strong convexity and Lipschitz gradient assumptions, in terms of expected objective error plus squared consensus residual.

Some of other related algorithms are as follows. For general convex functions and assuming closed and bounded feasible sets, the decentralized asynchronous ADMM is proved to have a rate of $O\left(\frac{1}{k}\right)$ in terms of expected objective error and feasibility violation. The augmented Lagrangian based primal-dual methods have linear convergence under strong convexity and Lipschitz gradient assumptions or under the positive-definite bounded Hessian assumption .

Our proposed algorithm is a synchronous gradient-based algorithm that has a rate of $O\left(\frac{1}{k}\right)$ for general convex objectives with Lipschitz differentials and has a linear rate once the sum of, rather than individual, functions $f_{i}$ is also (restricted) strongly convex.

2 Notation

The gradient of ${\mathbf{f}}({\mathbf{x}})$ is defined by

Each row $i$ of ${\mathbf{x}}$ and ${\nabla\mathbf{f}}({\mathbf{x}})$ is associated with agent $i$. We say that ${\mathbf{x}}$ is consensual if all of its rows are identical, i.e., $x_{(1)}=\cdots=x_{(n)}$. The analysis and results of this paper hold for all $p\geq 1$. The reader can assume $p=1$ for convenience (so ${\mathbf{x}}$ and ${\nabla\mathbf{f}}$ become vectors) without missing any major point.

3 Summary of Contributions

This paper introduces a novel gradient-based decentralized algorithm EXTRA, establishes its convergence conditions and rates, and presents numerical results in comparison to decentralized gradient descent. EXTRA can use a fixed step size independent of the network size and quickly converges to the solution to (1). It has a rate of convergence $O\left(\frac{1}{k}\right)$ in terms of best running violation to the first-order optimality condition when $\bar{f}$ is Lipschitz differentiable, and has a linear rate of convergence if $\bar{f}$ is also (restricted) strongly convex. Numerical simulations verify the theoretical results and demonstrate its competitive performance.

4 Paper Organization

The rest of this paper is organized as follows. Section 2 develops and interprets EXTRA. Section 3 presents its convergence results. Then, Section 4 presents three sets of numerical results. Finally, Section 5 concludes this paper.

Algorithm Development

This section derives the proposed algorithm EXTRA. We start by briefly reviewing decentralized gradient descent (DGD) and discussing the dilemma that DGD converges slowly to an exact solution when it uses a sequence of diminishing step sizes, yet it converges faster using a fixed step size but stalls at an inaccurate solution. We then obtain the update formula of EXTRA by taking the difference of two formulas of the DGD update. Provided that the sequence generated by the new update formula with a fixed step size converges to a point, we argue that the point is consensual and optimal. Finally, we briefly discuss the choice of mixing matrices in EXTRA. Formal convergence results and proofs are left to Section 3.

Following our notation, we rewrite (2) for all the agents together as

With a fixed step size $\alpha^{k}\equiv\alpha$, DGD has inexact convergence. For each agent $i$, $x_{(i)}^{k}$ converges to a point in the $O(\alpha)$-neighborhood of a solution to (1), and these points for different agents can be different. On the other hand, properly reducing $\alpha^{k}$ enables exact convergence, namely, that each $x^{k}_{(i)}$ converges to the same exact solution. However, reducing $\alpha^{k}$ causes slower convergence, both in theory and in practice.

Paper assumes that $\nabla f_{i}$’s are Lipschitz continuous, and studies DGD with a constant $\alpha^{k}\equiv\alpha$. Before the iterates reach the $O(\alpha)$-neighborhood, the objective value reduces at the rate $O\left(\frac{1}{k}\right)$, and this rate improves to linear if $f_{i}$’s are also (restricted) strongly convex. In comparison, paper studies DGD with diminishing $\alpha^{k}=\frac{1}{k^{1/3}}$ and assumes that $\nabla f_{i}$’s are Lipschitz continuous and bounded. The objective convergence rate slows down to $O\left(\frac{1}{k^{2/3}}\right)$. Paper studies DGD with diminishing $\alpha^{k}=\frac{1}{k^{1/2}}$ and assumes that $f_{i}$’s are Lipschitz continuous; a slower rate $O\left(\frac{\ln{k}}{\sqrt{k}}\right)$ is proved. A simple example of decentralized least squares in Section 4.1 gives a rough comparison of these three schemes (and how they compare to the proposed algorithm).

To see the cause of inexact convergence with a fixed step size, let ${\mathbf{x}}^{\infty}$ be the limit of ${\mathbf{x}}^{k}$ (assuming the step size is small enough to ensure convergence). Taking the limit over $k$ on both sides of iteration (3) gives us

When $\alpha$ is fixed and nonzero, assuming the consensus of ${\mathbf{x}}^{\infty}$ (namely, it has identical rows $x^{\infty}_{(i)}$) will mean ${\mathbf{x}}^{\infty}=W{\mathbf{x}}^{\infty}$, as a result of $W\mathbf{1}=\mathbf{1}$, and thus ${\nabla\mathbf{f}}({\mathbf{x}}^{\infty})=\mathbf{0}$, which is equivalent to $\nabla f_{i}(x^{\infty}_{(i)})=0,~{}\forall i$, i.e., the same point $x^{\infty}_{(i)}$ simultaneously minimizes $f_{i}$ for all agents $i$. This is impossible in general and is different from our objective to find a point that minimizes $\sum_{i=1}^{n}f_{i}$.

2 Development of EXTRA

The next proposition provides simple conditions for the consensus and optimality for problem (1).

${\mathbf{x}}^{*}=W{\mathbf{x}}^{*}$ (consensus),

then $x^{*}=x_{(i)}^{*}$, for any $i$, is a solution to the consensus optimization problem (1).

Next, we construct the update formula of EXTRA, following which the iterate sequence will converge to a point satisfying the two conditions in Proposition 1.

Consider the DGD update (3) written at iterations $k+1$ and $k$ as follows

where the former uses the mixing matrix $W$ and the latter uses

Given ${\mathbf{x}}^{k}$ and ${\mathbf{x}}^{k+1}$, the next iterate ${\mathbf{x}}^{k+2}$ is generated by (7).

Let us assume that $\{{\mathbf{x}}^{k}\}$ converges for now and let ${\mathbf{x}}^{*}=\lim_{k\rightarrow\infty}{\mathbf{x}}^{k}$. Let us also assume that ${\nabla\mathbf{f}}$ is continuous. We first establish condition 1 of Proposition 1. Taking $k\rightarrow\infty$ in (7) gives us

Therefore, ${\mathbf{x}}^{*}$ is consensual.

3 The Algorithm EXTRA and its Assumptions

We present EXTRA — an exact first-order algorithm for decentralized consensus optimization — in Algorithm 1.

Breaking to the individual agents, Step 1 of EXTRA performs updates

and Step 2 at each iteration $k$ performs updates

4 Mixing Matrices

The role of $W$ is the similar as that in DGD and average consensus . It has a few common choices, which can significantly affect performance.

Laplacian-based constant edge weight matrix ,

Symmetric fastest distributed linear averaging (FDLA) matrix. It is a symmetric $W$ that achieves fastest information diffusion and can be obtained by a semidefinite program .

It is worth noting that the optimal choice for average consensus, FDLA, no longer appears optimal in decentralized consensus optimization, which is more general.

5 EXTRA as Corrected DGD

Convergence Analysis

To establish convergence of EXTRA, this paper makes two additional but common assumptions as follows. Unless otherwise stated, the results in this section are given under Assumptions 1–3.

(Convex objective with Lipschitz continuous gradient) Objective functions $f_{i}$ are proper closed convex and Lipschitz differentiable:

Following Assumption 2, function ${\mathbf{f}}({\mathbf{x}})=\sum_{i=1}^{n}f_{i}(x_{(i)})$ is proper closed convex, and ${\nabla\mathbf{f}}$ is Lipschitz continuous

with constant ${L_{{\mathbf{f}}}}=\max_{i}\{L_{f_{i}}\}.$

(Solution existence) Problem (1) has a nonempty set of optimal solutions: $\mathcal{X}^{*}\neq\emptyset$.

We first state a lemma that gives the first-order optimality conditions of (1).

According to Assumption 1 and the definition of $U$, we have

Hence from Proposition 1, condition 1, ${\mathbf{x}}^{*}$ is consensual if and only if (16) holds.

Let ${\mathbf{x}}^{*}$ and ${\mathbf{q}}^{*}$ satisfy the optimality conditions (15) and (16). Introduce auxiliary sequence

The next lemma establishes the relations among ${\mathbf{x}}^{k}$, ${\mathbf{q}}^{k}$, ${\mathbf{x}}^{*}$, and ${\mathbf{q}}^{*}$.

In EXTRA, the quadruple sequence $\{{\mathbf{x}}^{k},{\mathbf{q}}^{k},{\mathbf{x}}^{*},{\mathbf{q}}^{*}\}$ obeys

Similar to how (10) is derived, summing EXTRA iterations $1$ through $k+1$

Subtracting (21) from (20) and adding $\mathbf{0}=U{\mathbf{q}}^{*}+\alpha{\nabla\mathbf{f}}({\mathbf{x}}^{*})$ to (20), we obtain (18).

2 Convergence and Rate

Let us first interpret the step size condition

which is independent of any network property (size, diameter, etc.). Furthermore, if $L_{f_{i}}$ ($i=1,\ldots,n$) are in the same order, the bound $\frac{1}{{L_{{\mathbf{f}}}}}$ has the same order as the bound $1/(\frac{1}{n}\sum_{i=1}^{n}L_{f_{i}})$, which is used in the (centralized) gradient descent method. In other words, a fixed and rather large step size is permitted by EXTRA.

Following Assumption 2, ${\nabla\mathbf{f}}$ is Lipschitz continuous and thus we have

Substituting (18) from Lemma 4 for $\alpha[{\nabla\mathbf{f}}({\mathbf{x}}^{k})-{\nabla\mathbf{f}}({\mathbf{x}}^{*})]$, it follows from (24) that

For the terms on the right-hand-side of (25), we have

Plugging (26)–(28) into (25) and recalling the definitions of ${\mathbf{z}}^{k}$, ${\mathbf{z}}^{*}$, and $G$, we have

Apply the basic equality $2\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},G({\mathbf{z}}^{*}-{\mathbf{z}}^{k+1})\rangle=\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}-\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*}\|_{G}^{2}-\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|_{G}^{2}$ to (30), we have

It shows from (23) that for any optimal ${\mathbf{z}}^{*}$, $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}$ is bounded and contractive, so $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}$ is converging as $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|_{G}^{2}\rightarrow 0$. The convergence of ${\mathbf{z}}^{k}$ to a solution ${\mathbf{z}}^{*}$ follows from the standard analysis for contraction methods; see, for example, Theorem 3 in .

To estimate the rate of convergence, we need the following result.

Part (i) is obvious. Let $b_{k}\triangleq\frac{1}{k}\sum_{t=1}^{k}a_{t}$. By the assumptions, $kb_{k}$ is uniformly bounded and obeys

from which part (ii) follows. Since $c_{k}\triangleq\min\limits_{t\leq k}\{a_{t}\}$ is monotonically non-increasing, we have

This and the fact that $\lim_{k\to\infty}\sum_{t=k+1}^{2k}a_{t}\rightarrow 0$ give us $c_{k}=o\left(\frac{1}{k}\right)$ or part (iii).

In the same setting of Theorem 5, the following rates hold:

Parts (1) and (2): Since the individual terms $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}$ converge to , we are able to sum (23) in Theorem 5 over $k=0$ through $\infty$ and apply the telescopic cancellation, i.e.,

Then, the results follow from Proposition 6 immediately.

It is open whether $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|_{G}^{2}$ is monotonic or not. If one can show its monotonicity, then the convergence rates will hold for the last point in the running sequence.

3 Linear Convergence under Restricted Strong Convexity

In this subsection we prove that EXTRA with a proper step size reaches linear convergence if the original objective $\bar{f}$ is restricted strongly convex.

For proof convenience, we introduce function

Under Assumptions 1 and 2, the following two statements are equivalent:

The original objective $\bar{f}(x)=\frac{1}{n}\sum_{i=1}^{n}f_{i}(x)$ is restricted strongly convex with respect to $x^{*}$;

In addition, the strong convexity constant of ${\mathbf{g}}$ is no less than that of $\bar{f}$.

Toward a lower bound of $\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}-\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*}\|_{G}^{2}$: From the definition of ${\mathbf{g}}$ and its restricted strong convexity, we have

Using Lemma 4 for $\alpha[{\nabla\mathbf{f}}({\mathbf{x}}^{k})-{\nabla\mathbf{f}}({\mathbf{x}}^{*})]$ in (37), we get

For the last three terms on the right-hand side of (38), we have from Young’s inequality

where $\eta>0$ is a tunable parameter and

Plugging (39)–(41) into (38) and recalling the definition of ${\mathbf{z}}^{k}$, ${\mathbf{z}}^{*}$, and $G$, we obtain

By $2\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},G({\mathbf{z}}^{*}-{\mathbf{z}}^{k+1})=\|{\mathbf{z}}^{k}-{\mathbf{z}}^{*}\|_{G}^{2}-\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{*}\|_{G}^{2}-\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|_{G}^{2}$, (42) turns into

A critical inequality: In order to establish (36), in light of (43), it remains to show

Establishing (45), Step 1: From Lemma 4 we have

Establishing (45), Step 2: In order to establish (45), with (49), it only remains to show

To ensure $\delta>0$, the following conditions are what we finally need:

On the other hand, we numerically observed that a step size as large as $O\left(\frac{1}{{L_{{\mathbf{f}}}}}\right)$ still leads to linear convergence, and EXTRA becomes faster with this larger step size. It remains an open question to prove linear convergence under this larger step size.

4 Decentralized implementation

Numerical Experiments

The network in this experiment is randomly generated with connectivity ratio $r=0.5$, where $r$ is defined as the number of edges divided by $\frac{L(L-1)}{2}$, the number of all possible ones. We set $n=10$, $m_{i}=1,\forall i$, $p=5$. Data $y_{(i)}$ and $M_{(i)}$, as well as noise $e_{(i)}$, $\forall i$, are generated following the standard normal distribution. We normalize the data so that ${L_{{\mathbf{f}}}}=1$. The algorithm starts from $x_{(i)}^{0}=0,\forall i$, and $\|x^{*}-x_{(i)}^{0}\|=300$.

The numerical results are illustrated in Fig. 1. In this experiment, we observe that both DGD with the fixed step size and EXTRA show similar linear convergence in the first $200$ iterations. Then DGD with the fixed step size begins to slow down and eventually stall, and EXTRA continues its progress.

2 Decentralized Robust Least Squares

Consider the same decentralized sensing setting and network as in Section 4.1. In this experiment, we use the Huber loss, which is known to be robust to outliers, and it allows us to observe both sublinear and linear convergence. We call the problem as decentralized robust least squares:

where $M_{(i)j}$ is the $j$-th row of matrix $M_{(i)}$ and $y_{(i)j}$ is the $j$-th entry of vector $y_{(i)}$. The Huber loss function $H_{\xi}$ is defined as

Except for new hand-optimized initial step sizes for DGD’s diminishing step sizes, all other algorithmic parameters remain unchanged from the last test.

3 Decentralized Logistic Regression

Consider the decentralized logistic regression problem:

Conclusion

As one of the fundamental method, gradient descent has been adapted to decentralized optimization, giving rise to simple and elegant iterations. In this paper, we attempted to address a dilemma or deficiency of the current decentralized gradient descent method: to obtain an accurate solution, it works slowly as it must use a small step size or iteratively diminish the step size; a large step size will lead to faster convergence to, however, an inaccurate solution. Our solution is an exact first-order algorithm, EXTRA, which uses a fixed large step size and quickly returns an accurate solution. The claim is supported by both theoretical convergence and preliminary numerical results. On the other hand, EXTRA is far from perfect, and more work is needed to adapt it to the asynchronous and dynamic network settings. They are interesting open questions for future work.

Appendix A Proof of Proposition 8

“(ii) $\Rightarrow$ (i)”: By definition of restricted strong convexity, there exists ${\mu_{\mathbf{g}}}>0$ so that for any ${\mathbf{x}}$,

Therefore, $\bar{f}(x)$ is restricted strongly convex with a constant ${\mu_{\bar{f}}}\triangleq{\mu_{\mathbf{g}}}$.

By, for example, setting $\gamma=\frac{{\mu_{\bar{f}}}}{4{L_{{\mathbf{f}}}}}$, we have ${\mu_{\mathbf{g}}}>0$. Hence, function ${\mathbf{g}}$ is restricted strongly convex for any $\alpha>0$ as long as function $\bar{f}$ is restricted strongly convex.

In the direction of “(ii) $\Rightarrow$ (i)”, we find ${\mu_{\mathbf{g}}}<{\mu_{\bar{f}}}$, unlike the more pleasant ${\mu_{\bar{f}}}={\mu_{\mathbf{g}}}$ in the other direction. However, from (60), we have

References