Fast Distributed Gradient Methods

I Introduction

To solve this and related problems, the literature proposes several distributed gradient like methods, including: (see also ); (see also ); (see also ); and . When the nodes lack global knowledge of the network parameters, reference establishes, for the distributed dual averaging algorithm therein, rate $O\left(\frac{1}{(1-\mu(W))}\frac{\log(Nk)}{k^{1/2}}\right)$, where $k$ is the number of communicated $d$-dimensional vectors per node, which also equals the number of iterations (gradient evaluations per node,) and $\mu(W)$ is the second largest singular value of the underlying $N\times N$ doubly stochastic weight matrix $W$. Further, when $\mu(W)$ is known to the nodes, and after optimizing the step-size, shows the convergence rate to be $O\left(\frac{1}{(1-\mu(W))^{1/2}}\frac{\log(Nk)}{k^{1/2}}\right)$.

Setup. The class of functions usually considered in the references above are more general than we consider here, namely, they assume that the $f_{i}$’s are (possibly) non-differentiable and convex, and:

In contrast, we assume the class $\mathcal{F}$ of convex $f_{i}$’s that have Lipschitz continuous and bounded gradients.

It is well established in centralized optimization, , that one expects faster convergence rates on classes of more structured functions; e.g., for convex, non-smooth functions, the best achievable rate for centralized (sub)gradient methods is $O(1/\sqrt{k})$, while, for convex functions with Lipschitz continuous gradient, the best rate is $O(1/k^{2})$, achieved, e.g., by the Nesterov gradient method . Here $k$ is the number of iterations, i.e., the number of gradient evaluations.

Contributions. Building from the centralized Nesterov gradient method, we develop for the class $\mathcal{F}$ two distributed gradient methods and prove their convergence rates, in terms of the number of per-node communications $\mathcal{K}$, the per-node gradient evaluations $k$, and the network topology. Our first method, the Distributed Nesterov Gradient (D–NG), uses one communication per $k$ (it has $k=\mathcal{K}$) and achieves convergence rate $O\left(\frac{1}{(1-\mu)^{p+\xi}}\left[\,\frac{\log k}{k}+\frac{\sqrt{N}\log^{1/2}k}{k^{3/2}}+\frac{N}{k^{2}}\,\right]\right)$, where $p=3$ and $\xi>0$ is an arbitrarily small quantity, when the nodes have no global knowledge of the parameters underlying the optimization problem and the network: $L$ and $G$ the $f_{i}$’s gradient’s Lispchitz constant and the gradient bound, respectively, $\mu:=\mu(W)$ the second largest singular value of $W$, and $R$ a bound on the distance to a solution. When $L$ and $\mu$ are known by all, D–NG with optimized step-size achieves the same rate with $p$ reduced to $1$.

Our second method, Distributed Nesterov gradient with Consensus iterations (D–NC), assumes global knowledge on $\mu$ and $L$ and achieves rates $O\left(\frac{1}{\left[(1-\mu)\mathcal{K}^{1-\xi}\right]^{2}}+\frac{\sqrt{N}}{\left[(1-\mu)\mathcal{K}^{1-\xi}\right]^{3}}+\frac{N}{\left[(1-\mu)\mathcal{K}^{1-\xi}\right]^{4}}\right)$ and $O\left(\frac{1}{k^{2}}+\frac{\sqrt{N}}{k^{3}}+\frac{N}{k^{4}}\right)$. Further, we establish that, for the class $\mathcal{F}$, both our methods (achieving at least $O(\log k/k)$) are strictly better than the distributed (sub)gradient method and the distributed dual averaging in , even when these algorithms are restricted to functions in $\mathcal{F}$. We show analytically that cannot be better than $\Omega\left(1/k^{2/3}\right)$ and $\Omega\left(1/{\mathcal{K}}^{2/3}\right)$ (see Subsection VII-A for details), and by simulation examples that and perform similarly.

Distributed versus centralized Nesterov gradient methods. The centralized Nesterov gradient method does not require bounded gradients – an assumption that we make for our distributed methods. We prove here that if we drop the bounded gradients assumption, the convergence rates that we establish do not hold for either of our algorithms. (It may be possible to replace the bounded gradients assumption with a weaker requirement.) In fact, the worst case convergence rates of D–NG and D–NC become arbitrarily slow. (See Subsection VII-B for details.) This important result illustrates a distinction between the allowed function classes by the centralized and distributed methods. The result is not specific to our accelerated methods; it can be shown that the standard distributed gradient method in is also arbitrarily slow when the assumption of bounded gradients is dropped (while convexity and Lipschitz continuous gradient hold) .

Remark. We comment on references and (see also Subsection VII-A and ). They develop accelerated proximal methods for time varying networks that resemble D–NC. The methods in and use only one consensus algorithm per outer iteration $k$, while we use two with D–NC. Adapting the results in to our framework, it can be shown that the optimality gap bounds in expressed in terms of $N,1-\mu(W),$ and $\mathcal{K}$ have the same or worse (depending on the variant of their methods) dependence on $\mathcal{K}$ and $\mu(W)$ than the one we show for D–NC, and a worse dependence on $N$. (See Subsection VII-A and .)

In addition to distributed gradient methods, literature also proposes distributed augmented Lagrangian dual or ordinary dual methods . These are based on the augmented Lagrangian (or ordinary) dual of the original problem. They in general have significantly more complex iterations than the gradient type methods that we consider in this paper, due to solving local optimization problems at each node, at each iteration, but may have a lower total communication cost. Reference uses the Nesterov gradient method to propose an augmented Lagrangian dual algorithm but does not analyze its convergence rate. In contrast, ours are primal gradient algorithms, with no notion of Lagrangian dual variables, and we establish the convergence rates of our algorithms. References study both the resource allocation and the problems that we consider (see (1)). For (1), apply certain accelerated gradient methods on the dual problem, in contrast with our primal gradient methods. Finally, uses the Nesterov gradient algorithm to propose a decomposition method based on a smoothing technique, for a problem formulation different than ours and on the Lagrangian dual problem.

Paper organization. The next paragraph introduces notation. Section II describes the network and optimization models that we assume. Section III presents our algorithms, the distributed Nesterov gradient and the distributed Nesterov gradient with consensus iterations, D–NG and D–NC for short. Section IV explains the framework of the (centralized) inexact Nesterov gradient method; we use this framework to establish the convergence rate results for D–NG and D–NC. Sections V and VI prove convergence rate results for the algorithms D–NG and D–NC, respectively. Section VII compares our algorithms D–NG and D–NC with existing distributed gradient type methods, discusses the algorithms’ implementation, and discusses the need for our Assumptions. Section VIII provides simulation examples. Finally, we conclude in Section IX. Proofs of certain lengthy arguments are relegated to Appendix.

II Problem model

This section introduces the network and optimization models that we assume.

Network model. We consider a (sparse) network $\mathcal{N}$ of $N$ nodes (sensors, processors, agents,) each communicating only locally, i.e., with a subset of the remaining nodes. The communication pattern is captured by the graph $\mathcal{G}=(\mathcal{N},E),$ where $E\subset\mathcal{N}\times\mathcal{N}$ is the set of links. The graph $\mathcal{G}$ is connected, undirected and simple (no self/multiple links.)

Weight matrix. We associate to the graph $\mathcal{G}$ a symmetric, doubly stochastic (rows and columns sum to one and all the entries are non-negative), $N\times N$ weight matrix $W$, with, for $i\neq j$, $W_{ij}>0$ if and only if, $\{i,j\}\in E,$ and $W_{ii}=1-\sum_{j\neq i}W_{ij}.$ Denote by $\widetilde{W}=W-J,$ where $J:=\frac{1}{N}{\mathbf{1}}{\mathbf{1}}^{\top}$ is the ideal consensus matrix. We let $\widetilde{W}=Q\widetilde{\Lambda}Q^{\top}$, where $\widetilde{\Lambda}$ is the diagonal matrix with $\widetilde{\Lambda}_{ii}=\lambda_{i}(\widetilde{W})$, and $Q=[q_{1},...,q_{N}]$ is the matrix of the eigenvectors of $\widetilde{W}$. With D–NC, we impose Assumption 1 (a) below; with D–NG, we require both Assumptions 1 (a) and (b).

We assume that (a) $\mu(W)<1$; and (b) $W\succeq{\eta}\,I,$ where ${\eta}<1$ is an arbitrarily small positive quantity.

Note that Assumption 1 (a) can be fulfilled only by a connected network. Assumption 1 (a) is standard and is also needed with the existing algorithms in . For a connected network, nodes can assign the weights $W$ and fulfill Assumption 1 (a), e.g., through the Metropolis weights ; to set the Metropolis weights, each node needs to know its own degree and its neighbors’ degrees. Assumption 1 (b) required by D–NG is not common in the literature. We discuss the impact of Assumption 1 (b) in Subsection VII-A.

Distributed optimization model. The nodes solve the unconstrained problem:

III Distributed Nesterov based algorithms

We now consider our two proposed algorithms. Subsection III-A presents algorithm D–NG, while subsection III-B presents algorithm D–NC.

Here, $W_{ij}$ are the averaging weights (the entries of $W$), and $O_{i}$ is the neighborhood set of node $i$ (including $i$). The step-size $\alpha_{k}$ and the sequence $\beta_{k}$ are:

With algorithm (2)–(3), each node $i$, at each iteration $k$, performs the following: 1) broadcasts its variable $y_{i}(k-1)$ to all its neighbors $j\in O_{i}$; 2) receives $y_{j}(k-1)$ from all its neighbors $j\in O_{i}$; 3) updates $x_{i}(k)$ by weight-averaging its own $y_{i}(k-1)$ and its neighbors variables $y_{j}(k-1)$, and performs a negative gradient step with respect to $f_{i}$; and 4) updates $y_{i}(k)$ via the inexpensive update in (3). To avoid notation explosion in the analysis further ahead, we assume throughout the paper, with both D–NG and D–NC, equal initial estimates $x_{i}(0)=y_{i}(0)=x_{j}(0)=y_{j}(0)$ for all $i,j;$ e.g., nodes can set them to zero.

We adopt the sequence $\beta_{k}$ as in the centralized fast gradient method by Nesterov ; see also . With the centralized Nesterov gradient, $\alpha_{k}=\alpha$ is constant along the iterations. However, under a constant step-size, algorithm (2)–(3) does not converge to the exact solution, but only to a solution neighborhood. More precisely, in general, $f(x_{i}(k))$ does not converge to $f^{\star}$ (See for details.) We force $f(x_{i}(k))$ to converge to $f^{\star}$ with (2)–(3) by adopting a diminishing step-size $\alpha_{k}$, as in (4). The constant $c>0$ in (4) can be arbitrary (See also ahead Theorem 5.)

where the identity matrix is of size $d$ – the dimension of the optimization variable in (1).

III-B Algorithm D–NC

Algorithm D–NC uses a constant step-size $\alpha\leq 1/(2L)$ and operates in two time scales. In the outer (slow time scale) iterations $k$, each node $i$ updates its solution estimate $x_{i}(k)$, and updates an auxiliary variable $y_{i}(k)$ (as with the D–NG); in the inner iterations $s$, nodes perform two rounds of consensus with the number of inner iterations given in (7) and (13) below, respectively. D–NC is Summarized in Algorithm 1.

The number of inner consensus iterations in (7) increases as $\log k$ and depends on the underlying network through $\mu(W)$. Note an important difference between D–NC and D–NG. D–NC uses explicitly a number of consensus steps at each $k$. In contrast, D–NG does not explicitly use multi-step consensus at each $k$; consensus occurs implicitly, similarly to .

Vector form. Using the same compact notation for $x(k)$, $y(k)$, and $\nabla F(y(k))$ as with D–NG, D–NC in vector form is:

The power $(W\otimes I)^{\tau_{x}(k)}$ in (9) corresponds to the first consensus in (7), and the power $(W\otimes I)^{\tau_{y}(k)}$ in (10) corresponds to the second consensus in (13). The connection between D–NC and the (centralized) Nesterov gradient method becomes clearer in Subsection IV-B. The matrix powers (9)–(10) are implemented in a distributed way through multiple iterative steps – they require respectively $\tau_{x}(k)$ and $\tau_{y}(k)$ iterative (distributed) consensus steps. This is clear from the representation in Algorithm 1.

IV Intermediate results: Inexact Nesterov gradient method

We will analyze the convergence rates of D–NG and D–NC by considering the evolution of the global averages $\overline{x}(k):=\frac{1}{N}\sum_{i=1}^{N}x_{i}(k)$ and $\overline{y}(k):=\frac{1}{N}\sum_{i=1}^{N}y_{i}(k)$. We will show that, with both distributed methods, the evolution of $\overline{x}(k)$ and $\overline{y}(k)$ can be studied through the framework of the inexact (centralized) Nesterov gradient method, essentially like the one in . Subsection IV-A introduces this framework and gives the relation for the progress in one iteration. Subsection IV-B then demonstrates that we can cast our algorithms D–NG and D–NC in this framework.

We next introduce the definition of a (pointwise) inexact first order oracle.

Remark. The prefix pointwise in Definition 1 emphasizes that we are concerned with finding $\left(\widehat{f}_{y},\widehat{g}_{y}\right)$ that satisfy (11) with $(L_{y},\delta_{y})$ at a fixed point $y$. This differs from the conventional definition (Definition 1) in . Throughout, we always refer to the inexact oracle in the sense of Definition 1 here and drop the prefix pointwise.

Consider the update rule (12) for some $k=1,2,...$ Then:

Lemma 2 is similar to [, Theorem 5], although considers a different accelerated Nesterov method. It is intuitive: the progress per iteration is the same as with the exact Nesterov gradient algorithm, except that it is deteriorated by the “gradient direction inexactness” ($(k+1)^{2}\delta_{k-1}$). The proof follows the arguments of and and is in .

IV-B Algorithms D–NG and D–NC in the inexact oracle framework

We now cast algorithms D–NG and D–NC in the inexact oracle framework.

Algorithm D–NG. Recall the global averages $\overline{x}(k):=\frac{1}{N}\sum_{i=1}^{N}x_{i}(k)$ and $\overline{y}(k):=\frac{1}{N}\sum_{i=1}^{N}y_{i}(k)$, and define:

Multiplying (5)–(6) from the left by $(1/N)(\mathbf{1}^{\top}\otimes I)$, using $(\mathbf{1}^{\top}\otimes I)(W\otimes I)=\mathbf{1}^{\top}\otimes I$, letting $L_{k-1}^{\prime}:=\frac{N}{\alpha_{k-1}}$, and using $\widehat{g}_{k}$ in (14), we obtain that $\overline{x}(k)$, $\overline{y}(k)$ evolve according to:

The following Lemma shows how we can analyze convergence of (15) in the inexact oracle framework. Define $\widetilde{y}_{i}(k):=y_{i}(k)-\overline{y}(k)$ and $\widetilde{y}(k):=(\widetilde{y}_{1}(k)^{\top},...,\widetilde{y}_{N}(k))^{\top}.$ Define analogously $\widetilde{x}_{i}(k)$ and $\widetilde{x}(k)$. We refer to $\widetilde{x}(k)$ and $\widetilde{y}(k)$ as the disagreement vectors, as they indicate how mutually apart the estimates of different nodes are.

Let Assumption 2 hold. Then, $(\widehat{f}_{k},\widehat{g}_{k})$ in (14) is a $(L_{k},\delta_{k})$ inexact oracle of $f=\sum_{i=1}^{N}f_{i}$ at point $\overline{y}(k)$ with constants $L_{k}=2NL$ and $\delta_{k}=L\|\widetilde{y}(k)\|^{2}.$

Lemma 3 implies that, if $L_{k-1}^{\prime}=\frac{Nk}{c}\geq 2NL$, i.e., if $c\leq\frac{k}{2L}$, then the progress per iteration in Lemma 2 holds for (15) with $\delta_{k-1}:=L\|\widetilde{y}(k-1)\|^{2}$. If $c\leq 1/(2L)$, Lemma 2 applies for all iterations $k=1,2,...$; otherwise, it holds for all $k\geq 2cL$.

For notation simplicity, we re-write $y(k)$ and $\overline{y}(k)$ as $y$ and $\overline{y}$, and $\widehat{f}_{k},\widehat{g}_{k},L_{k},\delta_{k}$ as $\widehat{f}_{y},\widehat{g}_{y},L_{y},\delta_{y}$. In view of Definition 1, we need to show inequalities (11). We first show the left one. By convexity of $f_{i}(\cdot)$: $f_{i}(x)\geq f_{i}(y_{i})+\nabla f_{i}(y_{i})^{\top}(x-y_{i}),\>\>\>\forall x;$ summing over $i=1,...,N$, using $f(x)=\sum_{i=1}^{N}f_{i}(x)$, and expressing $x-y_{i}=x-\overline{y}+\overline{y}-y_{i}$:

We now prove the right inequality in (11). As $f_{i}(\cdot)$ is convex and has Lipschitz continuous derivative with constant $L$, we have: $f_{i}(x)\leq f_{i}(y_{i})+\nabla f_{i}(y_{i})^{\top}(x-y_{i})+\frac{L}{2}\|x-y_{i}\|^{2},$ which, after summation over $i=1,...,N$, expressing $x-y_{i}=(x-\overline{y})+(\overline{y}-y_{i})$, and using the inequality $\|x-y_{i}\|^{2}=\|(x-\overline{y})+(\overline{y}-y_{i})\|^{2}\leq 2\|x-\overline{y}\|^{2}+2\|\overline{y}-y_{i}\|^{2}$, gives:

and so $(\widehat{f}_{y},\widehat{g}_{y})$ satisfy the right inequality in (11) with $L_{y}=2NL$ and $\delta_{y}=L\sum_{i=1}^{N}\|\overline{y}-y_{i}\|^{2}.$∎

Algorithm D–NC. Consider algorithm D–NC in (9)–(10). To avoid notational clutter, use the same notation as with D–NG for the global averages: $\overline{x}(k):=\frac{1}{N}\sum_{i=1}^{N}x_{i}(k)$, and $\overline{y}(k):=\frac{1}{N}\sum_{i=1}^{N}y_{i}(k)$, re-define $\widehat{f}_{k},\widehat{g}_{k}$ for D–NC as in (14), and let $L_{k-1}^{\prime}:=\frac{N}{\alpha}$. Multiplying (9)–(10) from the left by $(1/N)\mathbf{1}^{\top}\otimes I$, and using $(\mathbf{1}^{\top}\otimes I)(W\otimes I)=\mathbf{1}^{\top}\otimes I$, we get that $\overline{x}(k),\overline{y}(k)$ satisfy (15). As $\alpha\leq 1/(2L)$, we have $L_{k-1}^{\prime}\geq 2NL$, and so, by Lemma 3, the progress per iteration in Lemma 2 applies to $\overline{x}(k),\overline{y}(k)$ of D–NC for all $k$, with $\delta_{k-1}=L\|\widetilde{y}(k-1)\|^{2}$.

In summary, the analysis of convergence rates of both D–NG and D–NC boils down to finding the disagreements $\|\widetilde{y}(k)\|$ and then applying Lemma 2.

V Algorithm D–NG: Convergence analysis

This Section studies the convergence of D–NG. Subsection V-A bounds the disagreements $\|\widetilde{x}(k)\|$ and $\|\widetilde{y}(k)\|$ with D–NG; Subsection V-B combines these bounds with Lemma 2 to derive the convergence rate of D–NG and its dependence on the underlying network.

This subsection shows that $\|\widetilde{x}(k)\|$ and $\|\widetilde{y}(k)\|$ are $O(1/k)$, hence establishing asymptotic consensus – the differences of the nodes’ estimates $x_{i}(k)$ (and $y_{i}(k)$) converge to zero. Recall the step-size constant $c>0$ in (4) and the gradient bound $G$ in Assumption 3.

For D–NG in (2)–(4) under Assumptions 1 and 3:

with $\mathcal{B}(r):=\sup_{z\geq 1/2}\left(zr^{z}\log(1+z)\right)\in(0,\infty),$ $r\in(0,1).$

For notational simplicity, we prove Theorem 4 for $d=1$, but the proof extends to a generic $d>1.$ We model the dynamics of the augmented state $(\widetilde{x}(k)^{\top},\widetilde{x}(k-1)^{\top})^{\top}$ as a linear time varying system with inputs $(I-J)\nabla F(y(k))$. We present here the linear system and solve it in the Appendix. Substitute the expression for $y(k-1)$ in (5); multiply the resulting equation from the left by $(I-J)$; use $(I-J)W=\widetilde{W}=\widetilde{W}(I-J)$; and set $\widetilde{x}(0)=0$ by assumption. We obtain:

for all $k=1,2,...$, where $\beta_{k}$, for $k=0,1,...$, is in (4), $\beta_{-1}=0,$ and $(\widetilde{x}(0)^{\top},\widetilde{x}(-1)^{\top})^{\top}=0$. We emphasize that system (V-A) is more complex than the corresponding systems in, e.g., , which involve only a single state $\widetilde{x}(k)$; the upper bound on $\|\widetilde{x}(k)\|$ from (V-A) is an important technical contribution of this paper; see Theorem 4 and Appendix A.

V-B Convergence rate and network scaling

Theorem 5 (a) states the $O\left(\log k/k\right)$ convergence rate result for D–NG when the step-size constant $c\leq 1/(2L)$; Theorem 5 (b) (proved in ) demonstrates that the $O\left(\log k/k\right)$ convergence rate still holds if $c>1/(2L)$, with a deterioration in the convergence constant. Part (b) assumes $x_{i}(0)=y_{i}(0)=0$, $\forall i$, to avoid notational clutter.

Consider D–NG under Assumptions 1–3. Let $\|\overline{x}(0)-{{x^{\star}}}\|\leq R$, $R\geq 0$. Then:

If $c\leq 1/(2L)$, we have, $\forall i$, $\forall k=1,2,...$:

We prove here Theorem 5 (a); for part (b), see .

The proof consists of two parts. In the Step 1 of the proof, we estimate the optimality gap $\frac{1}{N}(f(\overline{x}(k))-f^{\star})$ at the point $\overline{x}(k)=\frac{1}{N}\sum_{i=1}^{N}x_{i}(k)$ using Lemma 2 and the inexact oracle machinery. In the Step 2, we estimate the optimality gap $\frac{1}{N}(f(x_{i}(k))-f^{\star})$ at any node $i$ using convexity of the $f_{i}$’s and the bound on $\|\widetilde{x}(k)\|$ from Theorem 4.

Step 1. Optimality gap $(f(\overline{x}(k))-f^{\star})$. Recall that, for $k=1,2,...,$ $(\widehat{f}_{k},\widehat{g}_{k})$ in (14) is a $(L_{k},\delta_{k})$ inexact oracle of $f$ at point $\overline{y}(k)$ with $L_{k}=2NL$ and $\delta_{k}=L\|\widetilde{y}(k)\|^{2}$. Note that $(\widehat{f}_{k},\widehat{g}_{k})$ is also a $(L^{\prime}_{k},\delta_{k})$ inexact oracle of $f$ at point $\overline{y}(k)$ with $L^{\prime}_{k}=N\frac{1}{c}(k+1)=\frac{N}{\alpha_{k}}$, because $\frac{1}{c}\geq 2L$, and so $L^{\prime}_{k}\geq L_{k}$. Now, we apply Lemma 2 to (15), with ${x^{\bullet}}={{x^{\star}}}$, and the Lipschitz constant $L_{k}^{\prime}=1/(\alpha_{k}/N).$ Recall that $\overline{v}(k)=\frac{\overline{y}(k)-(1-\gamma_{k})\overline{x}(k)}{\gamma_{k}}.$ We get:

Because $\frac{(k+1)^{2}}{k}\geq\frac{(k+1)^{2}-1}{k+1}$, and $\left(f(\overline{x}(k))-f^{\star}\right)\geq 0$, we have:

By unwinding the above recursion, and using $\overline{v}(0)=\overline{x}(0)$, gives: $\frac{(k+1)^{2}-1}{k+1}\left(f(\overline{x}(k))-f^{\star}\right)\leq\frac{2N}{c}\|\overline{x}(0)-{{x^{\star}}}\|^{2}+L\sum_{t=1}^{k}\|\widetilde{y}(t-1)\|^{2}\frac{(t+1)^{2}}{t}.$ Applying Theorem 4 to the last equation, and using $\frac{k+1}{(k+1)^{2}-1}=\frac{k+1}{k(k+2)}\leq\frac{k+2}{k(k+2)}=\frac{1}{k}$, and the assumption $\|\widetilde{y}(0)\|=0$, leads to, as desired:

Step 2. Optimality gap $(f(x_{i}(k))-f^{\star})$. Fix an arbitrary node $i$; then, by convexity of $f_{j}$, $j=1,2,...,N$: $f_{j}(\overline{x}(k))\geq f_{j}(x_{i}(k))+\nabla f_{j}(x_{i}(k))^{\top}(\overline{x}(k)-x_{i}(k)),$ and so: $f_{j}(x_{i}(k))\leq f_{j}(\overline{x}(k))+G\|\overline{x}(k)-x_{i}(k)\|.$ Summing the inequalities for $j=1,...,N$, using $\|\overline{x}(k)-x_{i}(k)\|\leq\|\widetilde{x}(k)\|$, subtracting $f^{\star}$ from both sides, from Theorem 4:

which, with (29) where the summation variable $t$ is replaced by $t+1$, completes the proof. ∎

Network Scaling. Using Theorem 5, Theorem 6 studies the dependence of the convergence rate on the underlying network – $N$ and $W$, when: 1) nodes do not know $L$ and $\mu(W)$ before the algorithm run, and they set the step-size constant $c$ to a constant independent of $N,L,W$, e.g., $c=1$; and 2) nodes know $L,\mu(W)$, and they set $c=\frac{1-\mu(W)}{2L}.$ See for dependence of $1/(1-\mu(W))$ on $N$ for commonly used models, e.g., expanders or geometric graphs.

Consider the algorithm D–NG in (2)–(4) under Assumptions 1–3. Then, $\frac{1}{N}\left(f(x_{i}(k))-f^{\star}\right)$ is:

where $A(\xi,{\eta})\in(0,\infty)$ depends only on $\xi,{\eta}$. Consider $\mathcal{B}(r)=\sup_{z\geq 1/2}\left\{z\,r^{z}\log(1+z)\right\},$ $r\in(0,1);$ there exists $K_{B}(\xi)\in(0,\infty)$ such that: $\log(1+z)\leq K_{B}(\xi)z^{\xi}$, $\forall z\geq 1/2.$ Thus:

for all $r\in(0,1)$. From the above equation, and using $1/(-\log\sqrt{u})\leq 2/(1-u)$, $\forall u\in[0,1)$, we have $\mathcal{B}\left(\sqrt{\mu}\right)\leq 2A^{\prime}(\xi)/(1-\mu)^{1+\xi}$. The latter, applied to (17), yields (31), with $A(\xi,{\eta}):=\frac{8}{\sqrt{{\eta}}}\max\left\{3A^{\prime}(\xi),7\right\}.$

A scaling result $O\left(\frac{N^{1/2}}{(1-\mu)^{p+\xi}}\frac{\log k}{k}\right)$, $p=3,1$, readily follows by substitution of (31) in Theorem 5 (a) and (b), respectively. To prove Theorem 6, we modify the argument of (30). We first prove claim (b). Namely, at any node $i$, using Lipschitz continuity of $\nabla f$ (with constant $NL$), $f(x_{i}(k))\leq f(\overline{x}(k))+\nabla f(\overline{x}(k))^{\top}(x_{i}(k)-\overline{x}(k))+\frac{NL}{2}\|x_{i}(k)-\overline{x}(k)\|^{2}$, and thus:

We now apply (31) to (33). Claim (b) is proved after setting $c=(1-\mu)/2L$. The proof for claim (a) is completely analogous; the argument only replaces the term $\frac{1}{k}\frac{2N}{c}R^{2}$ in (29) with $\frac{1}{k}\mathcal{C}^{\prime\prime}(L,G,R,C)$, see also , and sets $c=\Theta(1)$. ∎

VI Algorithm D–NC: Convergence Analysis

We now consider the D–NC algorithm. Subsection VI-A provides the disagreement estimate, while Subsection VI-A gives the convergence rate and network scaling.

We estimate the disagreements $\widetilde{x}(k)$, and $\widetilde{y}(k)$ with D–NC.

Let Assumptions 1 (a) and 3 hold, and consider the algorithm D–NC. Then, for $k=1,2,...$: $\|\widetilde{x}(k)\|\leq 2\alpha\sqrt{N}{G}\frac{1}{k^{2}}$, and $\|\widetilde{y}(k)\|\leq 2\alpha\sqrt{N}{G}\frac{1}{k^{2}}.$

For notational simplicity, we perform the proof for $d=1$, but it extends to a generic $d>1$. Denote by $B_{t-1}:=\max\left\{\|\widetilde{x}(t-1)\|,\,\,\|\widetilde{y}(t-1)\|\right\}$, and fix $t-1$. We want to upper bound $B_{t}$. Multiplying (9)–(10) by $(I-J)$ from the left, using $(I-J)W=\widetilde{W}(I-J)$:

We upper bound $\|\widetilde{x}(t)\|$ and $\|\widetilde{y}(t)\|$ from (34), (35). Recall $\|\widetilde{W}\|=\mu(W):=\mu\in(0,1)$; from (7) and (13), we have $\mu^{\tau_{x}(t)}\leq\frac{1}{t^{2}}$ and $\mu^{\tau_{y}(t)}\leq\frac{1}{3t^{2}}.$ From (34), using the sub-additive and sub-multiplicative properties of norms, and using $\|\widetilde{y}(t-1)\|\leq B_{t-1}$, $\mu\in(0,1)$, $\|(I-J)\nabla F(y(t-1))\|\leq\|\nabla F(y(t-1))\|\leq\sqrt{N}G$, $\beta_{t-1}\leq 1$:

Clearly, from (36) and (37):$B_{t}\leq\frac{1}{t^{2}}B_{t-1}+\frac{1}{t^{2}}\alpha\sqrt{N}{G}.$ Next, using $B_{0}=0$, unwind the latter recursion for $k=1,2$, to obtain, respectively: $B_{1}\leq\alpha\sqrt{N}G$ and $B_{2}\leq\alpha\sqrt{N}G/2$, and so the bound in Theorem 7 holds for $k=1,2.$ Further, for $k\geq 3$ unwinding the same recursion for $t=k,k-1,...,1$:

where we use $1+\sum_{t=2}^{k-1}\frac{1}{t^{2}}\leq\pi^{2}/6$, $\forall k\geq 3.$ ∎

VI-B Convergence rate and network scaling

We are now ready to state the Theorem on the convergence rate of D–NC.

Consider the algorithm D–NC under Assumptions 1 (a), 2, and 3. Let $\|\overline{x}(0)-{{x^{\star}}}\|\leq R$, $R\geq 0$. Then, after $\mathcal{K}=\sum_{t=1}^{k}\left(\tau_{x}(t)+\tau_{y}(t)\right)\leq\frac{2}{-\log\mu(W)}\left(k\log 3+2(k+1)\log(k+1)\right)=O\left(k\log k\right)$ communication rounds, i.e., after $k$ outer iterations, at any node $i$:

The proof is very similar to the proof of Theorem 5 (a) (for details see , second version v2); first upper bound $f(\overline{x}(k))-f^{\star}$, and then $f(x_{i}(k))-f^{\star}$. To upper bound $f(\overline{x}(k))-f^{\star}$, recall that the evolution (15) with $\alpha_{k}=\alpha$ for $(\overline{x}(k),\overline{y}(k))$ is the inexact Nesterov gradient with the inexact oracle $(\widehat{f}_{k},\widehat{g}_{k})$ in (14), and $(L_{k}=2NL,\,\delta_{k}=L\|\widetilde{y}(k)\|^{2})$. Then, apply Lemma 2 with $x^{\bullet}\equiv{{x^{\star}}}$ and $L_{k-1}^{\prime}=N/\alpha$, and use Theorem 7, to obtain:

Finally, find the bound on $f({x}_{i}(k))-f^{\star}$ analogously to the proof of Theorem 5 (a). ∎

Network scaling. We now give the network scaling for algorithm D–NC in Theorem 9. We assume that nodes know $L$ and $\mu(W)$ before the algorithm run.

Consider D–NC under Assumptions 1 (a), 2, and 3 with step-size $\alpha\leq 1/(2L)$. Then, after $k$ outer iterations and $\mathcal{K}$ communication rounds, at any node $i$, $\frac{1}{N}\left(f(x_{i})-f^{\star}\right)$ is $O\left(\frac{1}{\left(\left(1-\mu\right)\mathcal{K}^{1-\xi}\right)^{2}}+\frac{\sqrt{N}}{\left(\left(1-\mu\right)\mathcal{K}^{1-\xi}\right)^{3}}+\frac{N}{\left(\left(1-\mu\right)\mathcal{K}^{1-\xi}\right)^{4}}\right)$ and $O\left(\frac{1}{k^{2}}+\frac{N^{1/2}}{k^{3}}+\frac{N}{k^{4}}\right).$

Fix $\xi\in(0,1)$, and let $\mathcal{K}$ be the number of elapsed communication rounds after $k$ outer iterations. There exists $C_{0}(\xi)\in(1,\infty)$, such that, $2\left(k\log 3+2(k+1)\log(k+1)\right)\leq C_{0}(\xi)k^{1+\xi},$ $\forall k\geq 1.$ The latter, combined with $1/(-\log\mu(W))\leq 1/(1-\mu(W))$, $\mu(W)\in[0,1)$, and the upper bound bound on $\mathcal{K}$ in Theorem 8, gives: $1/k\leq\left(C_{0}(\xi)\right)\frac{1}{(1-\mu){\mathcal{K}}^{1-\xi}}$. Plugging the latter in the optimality gap bound in Theorem 8 gives a scaling result $O(N^{1/2}/[(1-\mu){\mathcal{K}}]^{2})$ and $O(N^{1/2}/k^{2})$. To prove Theorem 9, we proceed analogously to the proof of Theorem 6. From Theorem 8 and $\|\nabla f(\overline{x}(k))\|\leq\sqrt{2NL}\sqrt{f(\overline{x}(k))-f^{\star}}$, $\|\nabla f(\overline{x}(k))\|=O(N/k)$. Consider (32). Subtracting $f^{\star}$, dividing by $N$, and using $\|\nabla f(\overline{x}(k))\|=O(N/k)$ and (39), we obtain $\frac{1}{N}(f(x_{i}(k))-f^{\star})=O(1/k^{2}+N^{1/2}/k^{3}+N/k^{4})$. Finally, substitute $1/k\leq\left(C_{0}(\xi)\right)\frac{1}{(1-\mu){\mathcal{K}}^{1-\xi}}$ in the last bound. ∎

VII Comparisons with the literature and Discussion of the Assumptions

Subsection VII-A compares D–NG, D–NC, and the distributed (sub)gradient algorithms in , from the aspects of implementation and convergence rate; Subsection VII-B gives a detailed discussion on Assumptions 1–3.

We first set up the comparisons by explaining how to account for Assumption 1 (b) and by adapting the results in to our framework.

Assumption 1 (b). To be fair, we account for Assumption 1 (b) with D–NG as follows. Suppose that the nodes are given arbitrary symmetric, doubly stochastic weights $W$ with $\mu(W)<1$ – the matrix required by D–NC and . (For example, the Metropolis weights $W$.) As the nodes may not be allowed to check whether the given $W$ obeys Assumption 1 (b) or not, they modify the weights to $W^{\prime}:=\frac{1+{\eta}}{2}I+\frac{1-{\eta}}{2}W$, where $\eta\in(0,1)$ can be taken arbitrarily small. The matrix $W^{\prime}$ obeys Assumption 1 (b), whether $W$ obeys it or not. The modification is done without any required knowledge of the system parameters nor inter-node communication; node $i$ sets: 1) $W^{\prime}_{ij}=\frac{1-{\eta}}{2}W_{ij}$, for $\{i,j\}\in E$, $i\neq j$; 2) $W^{\prime}_{ij}=0$, for $\{i,j\}\notin E$, $i\neq j$; and 3) $W^{\prime}_{ii}:=1-\sum_{j\neq i}W^{\prime}_{ij}$. To be fair, when we compare D–NG with other methods (either theoretically as we do here or numerically as done in Section VIII), we set its weights to $W^{\prime}$. For theoretical comparisons, from Theorem 5, the convergence rate of D–NG depends on $W^{\prime}$ through the inverse spectral gap $1/(1-\mu(W^{\prime})).$ It can be shown that $\frac{1}{1-\mu(W^{\prime})}=\frac{2}{1-{\eta}}\frac{1}{1-\mu(W)},$ i.e., the spectral gaps of $W$ and $W^{\prime}$ differ only by a constant factor and the weight modification does not affect the convergence rate (up to a numerical constant); henceforth, we express the theoretical rate for D–NG in terms of $W$.

References develop and analyze non-accelerated and accelerated distributed gradient and proximal gradient methods for time-varying networks and convex $f_{i}$’s that have a differentiable component with Lipschitz continuous and bounded gradient and a non-differentiable component with bounded gradient. To compare with , we adapt it to our framework of static networks and differentiable $f_{i}$’s. (We set the non-differentiable components of the $f_{i}$’s to zero.) References assume deterministic time-varying networks. To adapt their results to our static network setup in a fair way, we replace the parameter $\gamma$ in (see equation (7) in ) with $\mu(W)$. The references propose two variants of the accelerated algorithm: the first (see (6a)–(6d) in ) has $k$ inner consensus iterations at the outer iteration $k$, while the second one has $\lceil 4\log(k+1)/(-\log\mu)\rceil$ (See Subsection III-C in .) The bounds established in for the second variant give its rate: 1) $O\left(\frac{N^{2}}{(1-\mu(W))^{2}\mathcal{K}^{2-\xi}}\right)$, when nodes know $\mu(W)$ and $L$. The first variant has a slower rate .

Algorithm implementation and convergence rate. Table 1 compares D–NG, D–NC, the algorithm in and the second algorithm in with respect to implementation and the number of communications $\mathcal{K}(\epsilon;N,W)$ to achieve $\epsilon$-accuracy. Here $\mathcal{K}(\epsilon;N,W)$ is the smallest number of communication rounds $\mathcal{K}$ after which $\frac{1}{N}(f(x_{i})-f^{\star})\leq\epsilon$, $\forall i.$ Regarding implementation, we discuss the knowledge required a priori by all nodes for: 1) convergence (row 1); and 2) both stopping and optimizing the step-size (row 2). By stopping, we mean determining a priori the (outer) iteration $k_{0}$ such that $\frac{1}{N}(f(x_{i}(k))-f^{\star})\leq\epsilon$, $\forall k\geq k_{0}$, $\forall i$. Optimizing the step size here means finding the step-size that minimizes the established upper bound (in the reference of interest) on the optimality gap (e.g., the bound for D–NG in Theorem 5 (a).) We assume, with all methods, that $W$ is already given (e.g., Metropolis.) Regarding $\mathcal{K}(\epsilon;N,W)$, we neglect the logarithmic and $\xi$-small factors and distinguish two cases: 1) the nodes have no global knowledge (row 3); and 2) the nodes know $L,\mu(W)=:\mu.$ We can see from Table 1 that, without global knowledge (row 3), D–NG has better dependence on $\epsilon$ than and worse dependence on $N,\mu$. Under global knowledge (row 4), D–NC has better complexity than and has better dependence on $\epsilon,\mu$ than and a worse dependence on $N$. Further, while D–NG and require no knowledge of any global parameters for convergence (row 1), D–NC and the second algorithm in need $L$ and $\mu(W)$. The first variant in requires only $L.$ Also, Table 1 for holds for a wider class of functions, and in row 4, only $\mu$ is needed .

Consider now D–NC when nodes do not have available their local gradient Lipschitz constants $L_{i}$. Nodes can take a diminishing step size $\alpha_{k}=1/(k+1)^{p}$, $p\in(0,1]$, and still guarantee convergence, with a deteriorated rate $O\left(\frac{1}{\mathcal{K}^{2-p-\xi}}\right).$ In alternative, it may be possible to employ a “distributed line search,” similarly to . Namely, in the absence of knowledge of the gradient’s Lipschitz constant $L$, the centralized Nesterov gradient method with a backtracking line search achieves the same rate $O(1/k^{2})$, with an additional computational cost per iteration $k$; see . It is an interesting research direction to develop a variant of distributed line search for D–NC type methods and explore the amount of incurred additional communications/computations per outer iteration $k$; due to lack of space, this is left for future work.

The $\Omega(1/k^{2/3})$ lower bound on the worst-case optimality gap for . We focus on the dependence on $k$ and $\mathcal{K}$ only (assuming a finite, fixed $1/(1-\mu(W))$.) We demonstrate that D–NG has a strictly better worst-case convergence rate in $k$ (and $\mathcal{K}$) than , when applied to the $f_{i}$’s defined by Assumptions 2 and 3. Thus, D–NC also has a better rate.

is the worst-case optimality gap when the step-size $\alpha_{k}=\frac{c}{(k+1)^{\tau}}$ is used. We perform the proof by constructing a “hard” example of the functions $f_{i}\in\mathcal{F}(L,G)$ and a “hard” initial condition to upper bound $\mathcal{E}\left(k,R;\tau,c\right)$; for any fixed $k,c,\tau$, we set: $x_{i}(0)=:(1,0)^{\top}$, $i=1,2;$ $f_{i}=:f_{i}^{{\theta}_{k}}$, where:

${\theta}_{k}=\frac{1}{\sum_{t=0}^{k-1}(t+1)^{-\tau}}$; and $\overline{\chi}=6.$ The proof of (40) is in the Appendix. We convey here the underlying intuition. When $\tau$ is $\epsilon$-smaller (away) from one, we show:

The first summand is the “optimization term,” for which a counterpart exists in the centralized gradient method also. The second, “distributed problem” term, arises because the gradients $\nabla f_{i}(x^{\star})$ of the individual nodes functions are non-zero at the solution $x^{\star}.$ Note the two opposing effects with respect to $\tau$: $\frac{1}{k^{1-\tau}}$ (the smaller $\tau\geq 0$, the better) and $\frac{1}{k^{2\tau}}$ (the larger $\tau\geq 0$, the better.) To balance the opposing effects of the two summands, one needs to take a diminishing step-size; $\tau=1/3$ strikes the needed balance to give the $\Omega(1/k^{2/3})$ bound.

VII-B Discussion on Assumptions

We now discuss what may occur if we drop each of the Assumptions made in our main results–Theorems 4 and 5 for D–NG, and Theorems 7 and 8 for D–NC.

Assumption 1 (a). Consider Theorems 4 and 7. If Assumption 1 (a) is relaxed, then $\widetilde{x}(k)$ with both methods may not converge to zero. Similarly, consider Theorems 5 and 8. Without Assumption 1 (a), $f(x_{i}(k))$ may not converge to $f^{\star}$ at any node; e.g., take $N=2$, $W=I$, and $f_{i}$, $i=1,2,$ in the next paragraph.

Note that the above means $\mathcal{E}(k;R;\alpha=1/(2L))=+\infty$, $\forall k\geq 10$, $\forall R\geq 0.$ That is, no matter how large the (outer) iteration number $k$ is, the worst case optimality gap is still arbitrarily large.

Similarly to D–NC, with D–NG we show in that (42) also holds for the $2$-node connected network, the symmetric $W$ with $W_{12}=W_{21}=1-W_{11}=1-W_{22}=\frac{1}{2}\left(1-10^{-6}\right)$ (this $W$ obeys Assumption 1), $\alpha_{k}=c/(k+1)$, and $c=\frac{1}{4}\times 10^{-6}$. The candidate functions are in (43), where, for fixed $k\geq 5$, $M>0$, $\theta(k,M)=8\times 10^{6}\,k\,\sqrt{M}.$

Finally, we consider what occurs if we drop Assumption 3 with Theorems 4 and 7. We show with D–NG and the above “hard” examples that $\|\widetilde{x}(k)\|\geq\frac{\sqrt{2}\,c\,\theta}{2\,k}$, $\forall k\geq 5.$ Hence, $\|\widetilde{x}(k)\|$ is arbitrarily large by choosing $\theta$ large enough. (see .) Similarly, with D–NC: $\|\widetilde{x}(k)\|\geq\frac{\alpha\,\theta\sqrt{2}}{4\,k^{2}}$, $\forall k\geq 10.$ (see Appendix C and .)

VIII Simulations

We compare the proposed D–NG and D–NC algorithms with on the logistic loss. Simulations confirm the increased convergence rates of D–NG and D–NC with respect to and show a comparable performance with respect to . More precisely, D–NG achieves an accuracy $\epsilon$ faster than for all $\epsilon$, while D–NC is faster than at least for $\epsilon\leq 10^{-2}$. With respect to , D–NG is faster for lower accuracies ($\epsilon$ in the range $10^{-1}$ to $10^{-4}-10^{-5}$), while becomes faster for high accuracies ($10^{-4}-10^{-5}$ and finer); D–NC performs slower than .

Results. Figure 1 (top) compares D–NG, D–NC (with step-sizes $\alpha=1/(2L)$ and $1/L$), , (both 1st and 2nd variant with $\alpha=1/L$.) We can see that D–NG converges faster than other methods for accuracies $\epsilon$ in the range $10^{-1}$ to $3\cdot 10^{-5}$. For example, for $\epsilon=10^{-2}$, D–NG requires about $10^{4}$ transmissions; (2nd variant) $\approx 3.16\cdot 10^{4}$; D–NC ($\alpha=1/L$) $\approx 4.65\cdot 10^{4}$, and D–NC with $\alpha=1/(2L)$ $\approx 1.1\cdot 10^{5}$; and (1st variant), , and – at least $\approx 1.3\cdot 10^{5}$. For high accuracies, $2\cdot 10^{-5}$ and finer, (2nd variant) becomes faster than D–NG. Finally, (2nd) converges faster than D–NC, while (1st) is slower than D–NC.