On the Convergence of Decentralized Gradient Descent

Introduction

Consider that $n$ agents form a connected network and collaboratively solve a consensus optimization problem

where each $f_{i}$ is only available to agent $i$. A pair of agents can exchange data if and only if they are connected by a direct communication link; we say that such two agents are neighbors of each other. Let ${\mathcal{X}}^{*}$ denote the set of solutions to (2), which is assumed to be non-empty, and let $f^{*}$ denote the optimal objective value.

The traditional (centralized) gradient descent iteration is

where $\alpha$ is the stepsize, either fixed or varying with $k$. To apply iteration (3) to problem (2) under the decentralized situation, one has two choices of implementation:

let a fusion center (which can be a designated agent) carry out iteration (3);

let all the agents carry out the same iteration (3) in parallel.

In either way, $f_{i}$ (and thus $\nabla f_{i}$) is only known to agent $i$. Therefore, in order to obtain $\nabla f(x(k))=\sum_{i=1}^{n}\nabla f_{i}(x(k))$, every agent $i$ must have $x(k)$, compute $\nabla f_{i}(x(k))$, and then send out $\nabla f_{i}(x(k))$. This approach requires synchronizing $x(k)$ and scattering/collecting $\nabla f_{i}(x(k))$, $i=1,\ldots,n$, over the entire network, which incurs a significant amount of communication traffic, especially if the network is large and sparse. A decentralized approach will be more viable since its communication is restricted to between neighbors. Although there is no guarantee that decentralized algorithms use less communication (as they tend to take more iterations), they provide better network load balance and tolerance to the failure of individual agents. In addition, each agent can keep its $f_{i}$ and $\nabla f_{i}$ private to some extent Neighbors of $i$ may know the samples of $f_{i}$ and/or $\nabla f_{i}$ at some points through data exchanges and thus obtain an interpolation of $f_{i}$..

Decentralized gradient descent does not rely on a fusion center or network-wide communication. It carries out an approximate version of (3) in the following fashion:

let each agent $i$ update its $x_{(i)}$ to the weighted average of its neighborhood;

let each agent $i$ apply $-\nabla f_{i}(x_{(i)})$ to decrease $f_{i}(x_{(i)})$.

At each iteration $k$, each agent $i$ performs the following steps:

computes the neighborhood weighted average $x_{(i)}(k+1/2)=\sum_{j}w_{ij}x_{(j)}(k)$, where $w_{ij}\not=0$ only if $j$ is a neighbor of $i$ or $j=i$;

applies $x_{(i)}(k+1)=x_{(i)}(k+1/2)-\alpha\nabla f_{i}(x_{(i)}(k))$.

Steps 1 and 2 can be carried out in parallel, and their results are used in Step 3. Putting the three steps together, we arrive at our main iteration

When $f_{i}$ is not differentiable, by replacing ${\nabla}f_{i}$ with a member of $\partial f_{i}$ we obtain the decentralized subgradient method . Other decentralization methods are reviewed Section 1.2 below.

We assume that the mixing matrix $W=[w_{ij}]$ is symmetric and doubly stochastic. The eigenvalues of $W$ are real and sorted in a nonincreasing order $1=\lambda_{1}(W)\geq\lambda_{2}(W)\geq\cdots\geq\lambda_{n}(W)\geq-1$. Let the second largest magnitude of the eigenvalues of $W$ be denoted as

The optimization of matrix $W$ and, in particular, $\beta$, is not our focus; the reader is referred to .

Some basic questions regarding the decentralized gradient method include: (i) When does $x_{(i)}(k)$ converge? (ii) Does it converge to $x^{*}\in{\mathcal{X}}^{*}$? (iii) If $x^{*}$ is not the limit, does consensus (i.e., $x_{(i)}(k)=x_{(j)}(k)$, $\forall i,j$) hold asymptotically? (iv) How do the properties of $f_{i}$ and the network affect convergence?

The study on decentralized optimization can be traced back to the seminal work in the 1980s . Compared to optimization with a fusion center that collects data and performs computation, decentralized optimization enjoys the advantages of scalability to network sizes, robustness to dynamic topologies, and privacy preservation in data-sensitive applications . These properties are important for applications where data are collected by distributed agents, communication to a fusion center is expensive or impossible, and/or agents tend to keep their raw data private; such applications arise in wireless sensor networks , multivehicle and multirobot networks , smart grids , cognitive radio networks , etc. The recent research interest in big data processing also motivates the work of decentralized optimization in machine learning . Furthermore, the decentralized optimization problem (2) can be extended to the online or dynamic settings where the objective function becomes an online regret or a dynamic cost .

To demonstrate how decentralized optimization works, we take spectrum sensing in a cognitive radio network as an example. Spectrum sensing aims at detecting unused spectrum bands, and thus enables the cognitive radios to opportunistically use them for data communication. Let $x$ be a vector whose elements are the signal strengths of spectrum channels. Each cognitive radio $i$ takes time-domain measurement $b_{i}=F^{-1}G_{i}x+e_{i}$, where $G_{i}$ is the channel fading matrix, $F^{-1}$ is the inverse Fourier transform matrix, and $e_{i}$ is the measurement noise. To each cognitive radio $i$, assign a local objective function $f_{i}(x)=(1/2)\|b_{i}-F^{-1}G_{i}x\|^{2}$ or the regularized function $f_{i}(x)=(1/2)\|b_{i}-F^{-1}G_{i}x\|^{2}+\phi(x)$, where $\phi(x)$ promotes a certain structure of $x$. To estimate $x$, a set of geologically nearby cognitive radios collaboratively solve the consensus optimization problem (2). Decentralized optimization is suitable for this application since communication between nearby cognitive radios are fast and energy-efficient and, if a cognitive radio joins and leaves the network, no reconfiguration is needed.

2 Related methods

The decentralized stochastic subgradient projection algorithm handles constrained optimization; the fast decentralized gradient methods adopts Nesterov’s acceleration; the distributed online gradient descent algorithmHere we consider its decentralized batch version. has nested iterations, where the inner loop performs a fine search; the dual averaging subgradient method carries out a projection operation after averaging and descending. Unsurprisingly, decentralized computation tends to require more assumptions for convergence than similar centralized computation. All of the above algorithms are analyzed under the assumption of bounded (sub)gradients. Unbounded gradients can potentially cause algorithm divergence. When using a fixed stepsize, the above algorithms (and iteration (4) in particular) converge to a neighborhood of $x^{*}$ rather than $x^{*}$ itself. The size of the neighborhood goes monotonic in the stepsize. Convergence to $x^{*}$ can be achieved by using diminishing stepsizes in at the price of slower rates of convergence. With diminishing stepsizes, shows an outer loop complexity of $O(1/k^{2})$ under Nesterov’s acceleration when the inner loop performs a substantial search job, without which the rate reduces to $O(\log(k)/k)$.

3 Contribution and notation

This paper studies the convergence of iteration (4) under the following assumptions.

For $i=1,\ldots,n$, $f_{i}$ is proper closed convex, lower bounded, and Lipschitz differentiable with constant $L_{f_{i}}>0$.

The network has a synchronized clock in the sense that (4) is applied to all the agents at the same time intervals, the network is connected, and the mixing matrix $W$ is symmetric and doubly stochastic with $\beta<1$ (see (5) for the definition of $\beta$).

Unlike , which characterize the ergodic convergence of $f(\hat{x}_{(i)}(k))$ where $\hat{x}_{(i)}(k)=\frac{1}{k}\sum_{s=0}^{k-1}{x}_{(i)}(s)$, this paper establishes the non-ergodic convergence of all local solution sequences $\{x_{(i)}(k)\}_{k\geq 0}$. In addition, the analysis in this paper does not assume bounded ${\nabla}f_{i}$. Instead, the following stepsize condition will ensure bounded $\nabla f_{i}$:

where $L_{h}=\max\{L_{f_{1}},\ldots,L_{f_{n}}\}$. This result is obtained through interpreting the iteration (4) for all the agents as a gradient descent iteration applied to a certain Lyapunov function.

Under Assumption 1 and condition (6), the rate of $O(1/k)$ for “near” convergence is shown. Specifically, the objective errors evaluated at the mean solution, $f(\frac{1}{n}\sum_{i=1}^{n}x_{(i)}(k))-f^{*}$, and at any local solution, $f({x}_{(i)}(k))-f^{*}$, both reduce at $O(1/k)$ until reaching the level $O(\frac{\alpha}{1-\beta})$. The rate of the mean solution is obtained by analyzing an inexact gradient descent iteration, somewhat similar to . However, all of their rates are given for the ergodic solution $\hat{x}_{(i)}(k)=\frac{1}{k}\sum_{s=0}^{k-1}{x}_{(i)}(s)$. Our rates are non-ergodic.

In addition, a linear rate of “near” convergence is established if $f$ is also strongly convex with modulus $\mu_{f}>0$, namely,

or $f$ is restricted strongly convex with modulus $\nu_{f}>0$,

Since our analysis uses a fixed stepsize, the local solutions will not be asymptotically consensual. To adapt our analysis to diminishing stepsizes, significant changes will be needed.

Based on iteration (4), a decentralized algorithm is derived for the basis pursuit problem with distributed data to recover a sparse signal in Section 3. The algorithm converges linearly until reaching an $O(\frac{\alpha}{1-\beta})$-neighborhood of the sparse signal.

Section 4 presents numerical results on the test problems of decentralized least squares and decentralized basis pursuit to verify our developed rates of convergence and the levels of the landing neighborhoods.

Throughout the rest of this paper, we employ the following notations of stacked vectors:

Convergence analysis

Previous methods and analysis assume bound gradients or subgradients of $f_{i}$. The assumption indeed plays a key role in the convergence analysis. For decentralized gradient descent iteration (4), it gives bounded deviation from mean $\|x_{(i)}(k)-\frac{1}{n}\sum_{j=1}^{n}x_{(j)}(k)\|$. It is necessary in the convergence analysis of subgradient methods, whether they are centralized or decentralized. But as we show below, the boundedness of $\nabla f_{i}$ does not need to be guaranteed but is a consequence of bounded stepsize $\alpha$, with dependence on the spectral properties of $W$. We derive a tight bound on $\alpha$ for $\nabla f_{i}(x_{(i)}(k))$ to be bounded.

and $L_{h}>0$. This is a trivial average consensus problem with $\nabla f_{i}(x_{(i)})=L_{h}(x_{(i)}-1)$ and $x^{*}=1$. Take any $\tau\in(0,1/3)$ and let the mixing matrix be

which is symmetric doubly stochastic. We have $\lambda_{3}(W)=3\tau-1\in(-1,0)$. Start from $(x_{(1)},x_{(2)},x_{(3)})=(1,0,2)$. Simple calculations yield:

if $\alpha<(1+\lambda_{3}(W))/L_{h}$, then $x_{(i)}(k)$ converges to $x^{*}$, $i=1,2,3$; (The consensus among $x_{(i)}(k)$ as $k\to\infty$ is due to design.)

if $\alpha>(1+\lambda_{3}(W))/L_{h}$, then $x_{(i)}(k)$ diverges and is asymptotically unbounded where $i=1,2,3$;

if $\alpha=(1+\lambda_{3}(W))/L_{h}$, then $(x_{(1)}(k),x_{(2)}(k),x_{(3)}(k))$ equals $(1,2,0)$ at odd $k$ and $(1,0,2)$ at even $k$.

Clearly, if $x_{(i)}$ converges, then $\nabla f_{i}(x_{(i)})$ converges and thus stays bounded. In the above example $\alpha=(1+\lambda_{3}(W))/L_{h}$ is the critical stepsize.

As each $\nabla f_{i}(x_{(i)})$ is Lipschitz continuous with constant $L_{f_{i}}$, $h(k)$ is Lipschitz continuous with constant

We formally show that $\alpha<(1+\lambda_{n}(W))/L_{h}$ ensures bounded $h(k)$. The analysis is based on the Lyapunov function

which is convex since all $f_{i}$ are convex and the remaining terms $\frac{1}{2}\left(\sum_{i=1}^{n}\|x_{(i)}\|^{2}-\sum_{i,j=1}^{n}w_{ij}x_{(i)}^{T}x_{(j)}\right)$ is also convex (and uniformly nonnegative) due to $\lambda_{1}(W)=1$. In addition, $\nabla\xi_{\alpha}$ is Lipschitz continuous with constant $L_{\xi_{\alpha}}\leq(1-\lambda_{n}(W))+{\alpha}L_{h}$. Rewriting iteration (4) as

we can observe that decentralized gradient descent reduces to unit-stepsize centralized gradient descent applied to minimize $\xi_{\alpha}([x_{(i)}])$.

then, starting from $x_{(i)}(0)=0$, ${i=1,2,\ldots,n}$, the sequence $x_{(i)}(k)$ generated by the iteration (4) converges. In addition we also have

for all $k=1,2,\ldots$, where $f^{o}:=\sum_{i=1}^{n}f_{i}(x_{(i)}^{o})$ and $x_{(i)}^{o}=\arg\min_{x}f_{i}(x)$.

Note that the iteration (4) is equivalent to the gradient descent iteration for the Lyapunov function (8). From the classic analysis of gradient descent iteration in and , $[x_{(i)}(k)]$, and hence $x_{(i)}(k)$, will converge to a certain point when $\alpha\leq(1+\lambda_{n}(W))/L_{h}$.

Next we show (10). Since $\beta<1$, we have $\lambda_{n}(W)>-1$ and $(L_{\xi_{\alpha}}/2-1)\leq 0$. Hence,

Recall that $\frac{1}{2}\left(\sum_{i=1}^{n}\|x_{(i)}\|^{2}-\sum_{i,j=1}^{n}w_{ij}x_{(i)}^{T}x_{(j)}\right)$ is nonnegative. Therefore, we have

On the other hand, for any differentiable convex function $g$ with the minimizer $x^{*}$ and Lipschitz constant $L_{g}$, we have $g(x_{a})\geq g(x_{b})+\nabla g^{T}(x_{b})(x_{a}-x_{b})+\frac{1}{2L_{g}}\|\nabla g(x_{a})-\nabla g(x_{b})\|^{2}$ and $\nabla g(x^{*})=0$. Then, $\|\nabla g(x)\|^{2}\leq 2L_{g}(g(x)-g^{*})$ where $g^{*}:=g(x^{*})$. Applying this inequality and (11), we obtain

where $f_{i}^{o}=f_{i}(x_{(i)}^{o})$ and $x_{(i)}^{o}=\arg\min_{x}f_{i}(x)$. Note that $x_{(i)}^{o}$ exists because of Assumption 1. Besides, we denote $f^{o}=\sum_{i=1}^{n}f_{i}^{o}$. This completes the proof. ∎

In the above theorem, we choose $x_{(i)}(0)=0$ for convenience. For general $x_{(i)}(0)$, a different bound for $\|h(k)\|$ can still be obtained. Indeed, if $x_{(i)}(0)\neq 0$, then \alpha^{-1}\xi_{\alpha}(0)=\sum_{i=1}^{n}f_{i}(0)+\frac{1}{2\alpha}\big{(}\sum_{i=1}^{n}\|x_{(i)}(0)\|^{2}-\sum_{i,j=1}^{n}w_{ij}x_{(i)}(0)^{T}x_{(j)}(0)\big{)} in (11). Hence we have \|h(k)\|^{2}\leq 2L_{h}\big{(}\sum_{i=1}^{n}f_{i}(0)-f^{o}\big{)}+\frac{L_{h}}{\alpha}\big{(}\sum_{i=1}^{n}\|x_{(i)}(0)\|^{2}-\sum_{i,j=1}^{n}w_{ij}x_{(i)}(0)^{T}x_{(j)}(0)\big{)}. The initial values of $x_{(i)}(0)$ do not influence the stepsize condition though they change the bound of gradient. For simplicity, we let $x_{(i)}(0)=0$ in the rest of the paper.

Dependence on stepsize. In (4), the negative gradient step $-\alpha\nabla f_{i}(x_{(i)})$ does not diminish at $x_{(i)}=x^{*}$. Even if we let $x_{(i)}=x^{*}$ for all $i$, $x_{(i)}$ will immediately change once $\eqref{dec_grad}$ is applied. Therefore, the term $-\alpha\nabla f_{i}(x_{(i)})$ prevents the consensus of $x_{(i)}$. Even worse, because both terms in the right-hand side of (4) change $x_{(i)}$, they can possibly add up to an uncontrollable amount and cause $x_{(i)}(k)$ to diverge. The local averaging term is stable itself, so the only choice we have is to limit the size of $-\alpha\nabla f_{i}(x_{(i)})$ by bounding $\alpha$.

Network spectrum. One can design $W$ so that $\lambda_{n}(W)>0$ and thus simply bound (9) to

2 Bounded deviation from mean

be the mean of $x_{(1)}(k),\ldots,x_{(n)}(k)$. We will later analyze the error in terms of $\bar{x}(k)$ and then each $x_{(i)}(k)$. To enable that analysis, we shall show that the deviation from mean $\|x_{(i)}(k)-\bar{x}(k)\|$ is bounded uniformly over $i$ and $k$. Then, any bound of $\|\bar{x}(k)-x^{*}\|$ will give a bound of $\|x_{(i)}(k)-x^{*}\|$. Intuitively, if the deviation from mean is unbounded, then there would be no approximate consensus among $x_{(1)}(k),\ldots,x_{(n)}(k)$. Without this approximate consensus, descending individual $f_{i}(x_{(i)}(k))$ will not contribute to the descent of $f(\bar{x}(k))$ and thus convergence is out of the question. Therefore, it is critical to bound the deviation $\|x_{(i)}(k)-\bar{x}(k)\|$.

If (10) holds and $\beta<1$, then the total deviation from mean is bounded, namely,

Recall the definition of $[x_{(i)}]$ and $h(k)$, from the equation (4) we have

where $\otimes$ denotes the Kronecker product. From it, we obtain

where (14) holds since $W$ is doubly stochastic. From $\|h(k)\|\leq D$ and $\beta<1$, it follows that

The proof of Lemma 1 utilizes the spectral property of the mixing matrix $W$. The constant in the upper bound is proportional to the stepsize $\alpha$ and monotonically increasing with respect to the second largest eigenvalue modulus $\beta$. The papers , , and also analyze the deviation of local solutions from their mean, but their results are different. The upper bound in is given at the termination time of the algorithm, which is not uniform in $k$. The two papers and , instead of bounding $\|W-\frac{1}{n}\mathbf{11}^{T}\|$, decompose it as the sum of element-wise $|w_{ij}-\frac{1}{n}|$ and then bounds it with the minimum nonzero element in $W$.

As discussed after Theorem 1, $D$ is affected by the value of $x_{(i)}(0)$, if it is nonzero. In Lemma 1, if $x_{(i)}(0)\neq 0$, then $[x_{(i)}(k)]=(W^{k}\otimes I)[x_{(i)}(0)]-\alpha\sum_{s=0}^{k-1}(W^{k-1-s}\otimes I)h(s)$. Substituting it into the proof of Lemma 1 we obtain

When $k\rightarrow\infty$, $\beta^{k}\|[x_{(i)}(0)]\|\rightarrow 0$ and, therefore, the last term dominates.

A consequence of Lemma 1 is that the distance between the following two quantities is also bounded

Under Assumption 1, if (10) holds and $\beta<1$, then

where the last inequality follows from Lemma 1. On the other hand, we have

We are interested in $g(k)$ since $-\alpha g(k)$ updates the average of $x_{(i)}(k)$. To see this, by taking the average of (4) over $i$ and noticing $W=[w_{ij}]$ is doubly stochastic, we obtain

On the other hand, since the exact gradient of $\frac{1}{n}\sum_{i=1}^{n}f_{i}(\bar{x}(k))$ is $\bar{g}(k)$, iteration (15) can be viewed as an inexact gradient descent iteration (using $g(k)$ instead of $\bar{g}(k)$) for the problem

It is easy to see that $\bar{f}$ is Lipschitz continuous with the constant

If any $f_{i}$ is strongly convex, then so is $\bar{f}$, with the modulus $\mu_{\bar{f}}=\frac{1}{n}\sum_{i=1}^{n}\mu_{f_{i}}$. Based on the above interpretation, next we bound $f(\bar{x}(k))-f^{*}$ and $\|\bar{x}(k)-x^{*}\|$.

3 Bounded distance to minimum

We consider the convex, restricted strongly convex, and strongly convex cases. In the former two cases, the solution $x^{*}$ may be non-unique, so we use the set of solutions ${\mathcal{X}}^{*}$. We need the followings for our analysis:

objective error $\bar{r}(k):=\bar{f}(\bar{x}(k))-\bar{f}^{*}=\frac{1}{n}(f(\bar{x}(k))-f^{*})~{}\text{where}~{}\bar{f}^{*}:=\bar{f}(x^{*})$, $x^{*}\in{\mathcal{X}}^{*}$;

Under Assumption 1, if $\alpha\leq\min\{(1+\lambda_{n}(W))/L_{h},1/L_{\bar{f}}\}=O(1/L_{h})$, then while

(where constants $C$ and $D$ are defined in (17) and (10), respectively), the reduction of $\bar{r}(k)$ obeys

In other words, $\bar{r}(k)$ decreases at a minimal rate of $O(\frac{1}{\alpha k})=O(1/k)$ until reaching $O(\frac{\alpha}{1-\beta})$.

Next we show the convergence of $\bar{r}(k)$. By the assumption, we have $1-\alpha L_{\bar{f}}\geq 0$, and thus

where the last inequality follows from Young’s inequality $\pm 2a^{T}b\leq\delta^{-1}\|a\|^{2}+\delta\|b\|^{2}$ for any $\delta>0$. Although we can later optimize over $\delta>0$, we simply take $\delta=1$. Since $\alpha\leq(1+\lambda_{n}(W))/L_{h}$, we can apply Theorem 1 and then Lemma 2 to the last term above, and obtain

Since $\|\bar{e}(k)\|\leq C$ as shown in (17), from $\bar{r}(k)=\bar{f}(\bar{x}(k))-\bar{f}^{*}\leq\langle\bar{g}(k),\bar{x}(k)-x^{*}(k)\rangle=\langle\bar{g}(k),\bar{e}(k)\rangle$, we obtain that

Hence, while $\frac{\alpha}{2C^{2}}\bar{r}^{2}(k)>2\cdot\frac{\alpha^{3}D^{2}L_{h}^{2}}{2(1-\beta)^{2}}$ or equivalently $\bar{r}(k)>C\sqrt{2}\cdot\frac{\alpha L_{h}D}{(1-\beta)}$, we have $\bar{r}(k+1)\leq\bar{r}(k)-O(\alpha\bar{r}^{2}(k))$. Dividing both sides by $\bar{r}(k)\bar{r}(k+1)$ gives $\frac{1}{\bar{r}(k)}+O(\frac{\alpha\bar{r}(k)}{\bar{r}(k+1)})\leq\frac{1}{\bar{r}(k+1)}$. Hence, $\frac{1}{\bar{r}(k)}$ increase at $\Omega(\alpha k)$, or $\bar{r}(k)$ reduces at $O(1/(\alpha k))$, which completes the proof. ∎

Theorem 2 shows that until reaching $f^{*}+O(\frac{\alpha}{1-\beta})$, $f(\bar{x}(k))$ reduces at the rate of $O(1/(\alpha k))$. For fixed $\alpha$, there is a tradeoff between the convergence rate and optimality. Again, upon the stopping of iteration (4), $\bar{x}(k)$ is not available to any of the agents but obtainable by invoking an average consensus algorithm.

Since $\bar{f}(x)$ is convex, we have for all $i=1,2,\ldots,n$:

From Theorem 2 we conclude that $\bar{f}(x_{(i)}(k))-\bar{f}^{*}$, like $\bar{r}(k)$, converges at $O(1/k)$ until reaching $O(\frac{\alpha}{1-\beta})$.

This nearly sublinear convergence rate is stronger than those of the distributed subgradient method and the dual averaging subgradient method . Their rates are in terms of objective error $f(\hat{x}_{(i)}(k))-f^{*}$ evaluated at the ergodic solution $\hat{x}_{(i)}(k)=\frac{1}{k}\sum_{s=0}^{k-1}x_{(i)}(s)$.

Next, we bound $\|\bar{e}(k+1)\|$ under the assumption of restricted or standard strong convexities. To start, we present a lemma.

Suppose that $\nabla\bar{f}$ is Lipschitz continuous with constant $L_{\bar{f}}$. Then, we have

(where $x^{*}\in{\mathcal{X}}^{*}$ and $\nabla\bar{f}(x^{*})=0$) for the following cases:

([21, Theorem 2.1.12]) if ${\bar{f}}$ is strongly convex with modulus $\mu_{\bar{f}}$, then $c_{1}=\frac{1}{\mu_{\bar{f}}+L_{\bar{f}}}$ and $c_{2}=\frac{\mu_{\bar{f}}L_{\bar{f}}}{\mu_{\bar{f}}+L_{\bar{f}}}$;

([37, Lemma 2]) if ${\bar{f}}$ is restricted strongly convex with modulus $\nu_{\bar{f}}$, then $c_{1}=\frac{\theta}{L_{\bar{f}}}$ and $c_{2}=(1-\theta)\nu_{\bar{f}}$ for any $\theta\in$.

Under Assumption 1, if $f$ is either strongly convex with modulus $\mu_{f}$ or restricted strongly convex with modulus $\nu_{f}$, and if $\alpha\leq\min\{(1+\lambda_{n}(W))/L_{h},c_{1}\}=O(1/L_{h})$ and $\beta<1$, then we have

constants $c_{1}$ and $c_{2}$ are given in Lemma 3, $\mu_{\bar{f}}=\mu_{f}/n$ and $\nu_{\bar{f}}=\nu_{f}/n$, and $\delta$ is any positive constant. In particular, if we set $\delta=\frac{c_{2}}{2(1-\alpha c_{2})}$ such that $c_{3}=\sqrt{1-\frac{\alpha c_{2}}{2}}\in(0,1)$, then we have

where the last inequality follows again from $\pm 2a^{T}b\leq\delta^{-1}\|a\|^{2}+\delta\|b\|^{2}$ for any $\delta>0$. The bound of $\|\bar{g}(k)-g(k)\|^{2}$ follows from Lemma 2 and Theorem 1, and we shall bound $\|\bar{e}(k)-\alpha\bar{g}(k)\|^{2}$, which is a standard exercise; we repeat below for completeness. Applying Lemma 3 and noticing $\bar{g}(x)=\nabla{\bar{f}}(x)$ by definition, we have

We shall pick $\alpha\leq c_{1}$ so that $\alpha(\alpha-c_{1})\|\bar{g}(k)\|^{2}\leq 0$. Then from the last two inequality arrays, we have

Note that if $f$ is strongly convex, then $c_{1}c_{2}=\frac{\mu_{\bar{f}}L_{\bar{f}}}{(\mu_{\bar{f}}+L_{\bar{f}})^{2}}<1$; if $f$ is restricted strongly convex, then $c_{1}c_{2}=\frac{\theta(1-\theta)\nu_{\bar{f}}}{L_{\bar{f}}}<1$ because $\theta\in$ and $\nu_{\bar{f}}<L_{\bar{f}}$. Therefore we have $c_{1}<1/c_{2}$. When $\alpha<c_{1}$, $(1+\alpha\delta)(1-\alpha c_{2})>0$.

As a result, if $f$ is strongly convex, then $\bar{x}(k)$ geometrically converges until reaching an $O(\frac{\alpha}{1-\beta})$-neighborhood of the unique solution $x^{*}$; on the other hand, if $f$ is restricted strongly convex, then $\bar{x}(k)$ geometrically converges until reaching an $O(\frac{\alpha}{1-\beta})$-neighborhood of the solution set $\mathcal{X}^{*}$.

4 Local agent convergence

Under Assumption 1, if $f$ is either strongly convex or restricted strongly convex, $\alpha<\min\{(1+\lambda_{n}(W))/L_{h},c_{1}\}$ and $\beta<1$, then we have

where $x^{*}(0),{x}^{*}(k)\in{\mathcal{X}}^{*}$ are solutions defined at the beginning of subsection 2.3 and the constants $c_{3}$, $c_{4}$, $D$ are the same as given in Theorem 3.

Similar to Theorem 3 and Remark 1, if we set $\delta=\frac{c_{2}}{2(1-\alpha c_{2})}$, and if $f$ is strongly convex, then $x_{(i)}(k)$ geometrically converges to an $O(\frac{\alpha}{1-\beta})$-neighborhood of the unique solution $x^{*}$; if $f$ is restricted strongly convex, then $x_{(i)}(k)$ geometrically converges to an $O(\frac{\alpha}{1-\beta})$-neighborhood of the solution set $\mathcal{X}^{*}$.

Decentralized basis pursuit

We derive an algorithm for solving a decentralized basis pursuit problem to illustrate the application of iteration (4).

where $\sum_{i=1}^{n}A_{i}y_{i}=Ay$. This formulation is a column-partitioned version of decentralized basis pursuit, as opposed to the row-partitioned version in and . Both versions find applications in, for example, collaborative spectrum sensing , sparse event detection , and seismic modeling .

Developing efficient decentralized algorithms to solve (18) is nontrivial since the objective function is neither differentiable nor strongly convex, and the constraint couples all the agents. In this paper, we turn to an equivalent and tractable reformulation by appending a strongly convex term and solving its Lagrange dual problem by decentralized gradient descent. Consider the augmented form of (18) motivated by :

where the regularization parameter $\gamma>0$ is chosen so that (19) returns a solution to (18). Indeed, provided that $Ay=b$ is consistent, there always exists $\gamma_{\min}>0$ such that the solution to (19) is also a solution to (18) for any $\gamma\geq\gamma_{\min}$ . Linearized Bregman iteration proposed in is proven to converge to the unique solution of (19) efficiently. See for its analysis and for important improvements. Since the problem (19) is now solved over a network of agents, we need to devise a decentralized version of linearized Bregman iteration.

The Lagrange dual of (19), casted as a minimization (instead of maximization) problem, is

The function $f_{i}$ is defined with $A_{i}$ and $b$, where matrix $A_{i}$ is the private information of agent $i$. The local objective functions $f_{i}$ are differentiable with the gradients given as

Applying the iteration (4) to the problem (21) starting with $x_{(i)}(0)=0$, we obtain the iteration

Note that the primal solution $y_{i}(k)$ is iteratively updated, as a middle step for the update of $x_{(i)}(k+1)$.

It is easy to verify that the local objective functions $f_{i}$ are Lipschitz differentiable with the constants $L_{f_{i}}=\gamma\|A_{i}\|^{2}$. Besides, given that $Ay=b$ is consistent, proves that $f(x)$ is restricted strongly convex with a computable constant $\nu_{f}>0$. Therefore, the objective function $f(x)$ in (20) has $L_{h}=\max\{\gamma\|A_{i}\|^{2}:i=1,2,\cdots,n\}$, $L_{\bar{f}}=\frac{\gamma}{n}\sum_{i=1}^{n}\|A_{i}\|^{2}$ and $\nu_{\bar{f}}=\nu_{f}/n$. By Theorem 3, any local dual solution $x_{(i)}(k)$ generated by iteration (23) linearly converges to a neighborhood of the solution set of (20), and the primal solution $y(k)=[y_{1}(k);\cdots;y_{n}(k)]$ linearly converges to a neighborhood of the unique solution of (19).

Consider $x_{(i)}(k)$ generated by iteration (23) and $\bar{x}(k):=\frac{1}{n}\sum_{i=1}^{n}x_{(i)}(k)$. The unique solution of (19) is $y^{*}$ and the projection of $\bar{x}(k)$ onto the optimal solution set of (20) is $\bar{x}^{*}(k)=\text{Proj}_{\mathcal{X}^{*}}(\bar{x}(k))$. If the stepsize $\alpha<\min\{{(1+\lambda_{n}(W))}/{L_{h}},c_{1}\}$, we have

where the constants $c_{3}$ and $c_{4}$ are the same as given in Theorem 3. In particular, if we set $\delta=\frac{c_{2}}{2(1-\alpha c_{2})}$ such that $c_{3}=\sqrt{1-\frac{\alpha c_{2}}{2}}\in(0,1)$, then $\frac{c_{4}}{\sqrt{1-c_{3}^{2}}}+\frac{\alpha D}{1-\beta}=O(\frac{\alpha}{1-\beta})$. On the other hand, the primal solution satisfies

The result (24) is a corollary of Corollary 1. We focus on showing (25).

Given any dual solution $\bar{x}(k)$, the primal solution of (19) is $y^{*}=\gamma\text{Shrink}(A^{T}\bar{x}^{*}(k))$. Recall that $y(k)=[y_{1}(k);\cdots;y_{n}(k)]$ and $y_{i}(k)=\gamma\text{Shrink}(A_{i}^{T}x_{(i)}(k))$. We have

Due to the contraction of the shrinkage operator, we have the bound $\|\text{Shrink}(A_{i}^{T}x_{(i)}(k))-\text{Shrink}(A_{i}^{T}\bar{x}^{*}(k))\|\leq\|A_{i}\|\|x_{(i)}(k)-\bar{x}^{*}(k)\|\leq\max_{i}\left(\|A_{i}\|\|x_{(i)}(k)-\bar{x}^{*}(k)\|\right)$. Combining this inequality with (26), we get (25). ∎

Numerical experiments

In this section, we report our numerical results applying the iteration (4) to a decentralized least squares problem and the iteration (23) to a decentralized basis pursuit problem.

We generate a network consisting of $n$ agents with $\frac{n(n-1)}{2}\eta$ edges that are uniformly randomly chosen, where $n=100$ and $\eta=0.3$ are chosen for all the tests. We ensure a connected network.

We apply the iteration (4) to the least squares problem

Fig. 1 depicts the convergence of the error $\bar{e}(k)$ corresponding to five different stepsizes. It shows that $\bar{e}(k)$ reduces linearly until reaching an $O(\alpha)$-neighborhood, which agrees with Theorem 3. Not surprisingly, a smaller $\alpha$ causes the algorithm to converge more slowly.

Fig. 2 compares our theoretical stepsize bound in Theorem 1 to the empirical bound of $\alpha$. The theoretical bound for this experimental network is $\min\{\frac{1+\lambda_{n}(W)}{L_{h}},c_{1}\}=0.1038$. In Fig. 2, we choose $\alpha=0.1038$ and then the slightly larger $\alpha=0.12$. We observe convergence with $\alpha=0.1038$ but clear divergence with $\alpha=0.12$. This shows that our bound on $\alpha$ is quite close to the actual requirement.

2 Decentralized gradient descent for basis pursuit

In this subsection we test the iteration (23) for the decentralized basis pursuit problem (18).

Conclusion

Consensus optimization problems in multi-agent networks arise in applications such as mobile computing, self-driving cars’ coordination, cognitive radios, as well as collaborative data mining. Compared to the traditional centralized approach, a decentralized approach offers more balanced communication load and better privacy protection. In this paper, our effort is to provide a mathematical understanding to the decentralized gradient descent method with a fixed stepsize. We give a tight condition for guaranteed convergence, as well as an example to illustrate the fail of convergence when the condition is violated. We provide the analysis of convergence and the rates of convergence for problems with different properties and establish the relations between network topology, stepsize, and convergence speed, which shed some light on network design. The numerical observations reasonably matches the theoretical results.

Acknowledgements

Q. Ling is supported by NSFC grant 61004137. W. Yin is supported by ARL and ARO grant W911NF-09-1-0383 and NSF grants DMS-0748839 and DMS-1317602. The authors thank Yangyang Xu for helpful comments.

References