Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs

I Introduction

We consider the problem of cooperatively minimizing a separable convex function by a network of nodes. Our motivation stems from much recent interest in distributed optimization problems which arise when large clusters of nodes (which can be sensors, processors, autonomous vehicles or UAVs) wish to collectively optimize a global objective by means of actions taken by each node and local coordination between neighboring nodes.

Our focus here is on the case when the communication topology connecting the nodes is time-varying and directed. In the context of wireless networks, time-varying communication topologies arise if the nodes are mobile or if the communication between them is subject to unpredictable bouts of interference. Directed communication links are also a natural assumption as in many cases there is no reason to expect different nodes to transmit wirelessly at the same power level. Transmissions at different power levels will result in unidirectional communication between nodes (usually, after an initial bidirectional exchange of “hello” messages).

In our previous work we proposed an algorithm which is guaranteed to drive all nodes to an optimal solution in this setting. Our algorithm, which we called the subgradient-push, can be implemented in a fully distributed way: no knowledge of the (time-varying) communication topology or even of the total number of nodes is required, although every node is required to know its out-degree at each time. The subgradient-push is a generalization of the so-called push-sum protocol for computing averages on directed graphs proposed over a decade ago (see also the more recent development in ).

Our main result in was that the subgradient-push protocol drives all the nodes to an optimal solution at a rate $O\left((\ln t)/\sqrt{t}\right)$. Here, we consider the effect of stronger assumptions on the individual functions. Our main result is that if the functions at each node are strongly convex, then even if each node only has access to noisy gradients of its own function, an improvement to an $O\left((\ln t)/t\right)$ rate can be achieved.

Note that our convergence rate is quite close to best achievable rate of $O(1/t)$ in (centralized) strongly convex optimization with noisy gradient samples of bounded variance . Obtaining an algorithm with a $O(1/t)$ rate in our setting of distributed, noisy, strongly-convex optimization over time-varying directed graphs of unknown size remains an open problem.

Our work here contributes to the growing literature on distributed methods for optimization over networks . It is a part of a recent strand of the distributed optimization literature which studies effective protocols when interactions between nodes are unidirectional . Our work is most closely related to recent developments in . We specifically mention , which were the first papers to suggest the use of push-sum-like updates for optimization over directed graphs as well as which derived O($1/t)$ convergence rates in the less stringent setting when every graph is fixed and undirected.

Our paper is organized as follows. In Section II, we describe the problem formally and present the algorithm along with the main results. The results are then proved in Sections III and IV. We conclude with some simulations in Section V and some concluding remarks in Section VI.

II Problem, Algorithm and Main Result

We consider a network of $n$ nodes which would like to collectively solve the following minimization problem:

We make the assumption that at each time $t$, node $i$ can only send messages to its out-neighbors in some directed graph $G(t)$, where the graph $G(t)$ has vertex set $\{1,\ldots,n\}$ and edge set $E(t)$. We will be assuming that the sequence $\{G(t)\}$ is $B$-strongly-connected, which means that there is a positive integer $B$ such that the graph with edge set

is strongly connected for each $k\geq 0$. Intuitively, we are assuming the time-varying network $G(t)$ must be repeatedly connected over sufficiently long time scales.

We use $N^{\rm in}_{i}(t)$ and $N^{\rm out}_{i}(t)$ denote the in- and out-neighborhoods of node $i$ at time $t$, respectively, where by convention node $i$ is always considered to be an in- and out- neighbor of itself, so $i\in N^{\rm in}(i)(t),i\in N^{\rm out}(t)$ for all $i,t$. We use $d_{i}(t)$ to denote the out-degree of node $i$, and we assume that every node $i$ knows its out-degree $d_{i}(t)$ at every time $t$.

where the variables $y_{i}(t)$ are initialized as $y_{i}(0)=1$ for all $i$. Here, we use ${\mathbf{g}}_{i}(t+1)$ to abbreviate the notation ${\mathbf{g}}_{i}({\mathbf{z}}_{i}(t+1))$ (see Eq. (1)). The positive stepsize $\alpha(t+1)$ will be specified later.

These updates have a simple physical implementation: each node $j$ broadcasts the quantities ${\mathbf{x}}_{j}(t)/d_{j}(t),y_{j}(t)/d_{j}(t)$ to all of the nodes $i$ in its out-neighborhood. Each neighbor $i$ then sums the received messages to obtain ${\mathbf{w}}_{i}(t+1)$ and $y_{i}(t+1)$. The updates of ${\mathbf{z}}_{i}(t+1),{\mathbf{x}}_{i}(t+1)$ then do not require any additional communications among the nodes at step $t$.

Since the chain is ergodic, the matrices $A^{t}$ converge to a rank-one matrix with identical columns, i.e., $\lim_{t\to\infty}A^{t}=\pi{\bf 1}^{\prime}$, where $\pi$ is a stochastic vector with $\pi_{i}>0$ for all $i$. Therefore, for $x(t)$ we have

Consider the coordinate-wise ratio of the vectors $x(t)$ and $y(t)$. The limits of these ratios satisfy the following relation

which relies on the fact that $\pi_{i}>0$ (these values cancel out in the ratio). Thus, any influence that the chain may induce, as reflected in different steady state values $\pi_{i}$, do not appear in the limiting ratios of $x_{i}(t)/y_{i}(t)$. Furthermore, as indicated by Eq. (7), if we set $y(0)={\bf 1}$, we obtain

showing that the ratios $x_{i}(t)/y_{i}(t)$ approach the initial average as $t\to\infty$. When the underlying Markov chain is time-varying (i.e., the matrix $A$ is time-varying, then one would expect that the limits of the ratios $x_{i}(t)/y_{i}(t)$ track the running averages $\frac{{\bf 1}^{\prime}x(t)}{n}$ with increasing accuracy.

The algorithm (3) is motivated by the insight that the ratios $x_{i}(t)/y_{i}(t)$ can track the running averages $\frac{{\bf 1}^{\prime}x(t)}{n}$ with the accuracy that can been characterized by the connectivity stricture of the underlying graphs. Additionally, the running averages are controlled by the ”gradient” field in order to move them toward the set of optimal solutions of the problem of our interest. Specifically, in the light of the above discussion, the updates ${\mathbf{x}}_{i}(t+1)$ and $y_{i}(t+1)$ in the algorithm (3) correspond to updates of vector-variables of the nodes, where $y$ variables serve to cancel out the effects of scaling (which is due to a time-varying Markov chain, as reflected by the graph structure). The updates of $z_{i}(t+1)$ in algorithm (3) are just keeping track of the ratios at the nodes (as these will be consenting in a long run). The last update step in algorithm (3) is basically forcing the consensus point to asymptotically approach an optimal solution of the problem.

Our previous work in provided a rate estimate for a suitable averaged version of the variables ${\bf z}_{i}(t)$ with the stepsize choice $\alpha(t)=1/\sqrt{t}$. In particular, we showed in that, for each $i=1,\ldots,n$, a suitably averaged version of ${\bf z}_{i}(t)$ converges to the same global minimum of the function $F(z)$ at a rate of $O((\ln t)/\sqrt{t})$. Our main contribution in this paper is an improved convergence rate estimate $O((\ln t)/t)$ under the strong convexity assumption on the functions $f_{i}$.

where $g({\mathbf{y}})$ is any subgradient of $f({\mathbf{z}})$ at ${\mathbf{z}}={\mathbf{y}}$.

We next provide precise statements of our improved rate estimates. For convenience, we define

to be the vector which averages all the ${\mathbf{x}}_{j}(t)$ at each node. Furthermore, let us introduce some notation for the assumptions we will be making.

(a) The graph sequence $\{G(t)\}$ is $B$-strongly-connected. (b) Each function $f_{i}$ is $\mu_{i}$-strongly convex with $\mu_{i}>0$.

Note that Assumption 1(b) implies the existence of a unique global minimizer ${\bf z^{*}}$ of $F({\bf z})$.

This can easily be done recursively, e.g., by setting $\widehat{\mathbf{z}}_{i}(1)={\mathbf{z}}_{i}(0)$ and updating as

We are now ready to state our first main result, which deals with the speed at which the averaged iterates $\widehat{\mathbf{z}}_{i}(t)$ we have just described converge to the global minimizer ${\bf z}^{*}$ of $F({\bf z})$.

Suppose Assumption 1 is satisfied and $\alpha(t)=\frac{p}{t}$ for $t\geq 1$, where the constant $p$ is such that

Suppose further that there exists a scalar $D$ such that with probability $1$, $\sup_{t}\|{\bf z}_{i}(t)\|\leq D$. Then, we have for all $i=1,\ldots,n$,

where $L_{i}$ is the largest-possible Euclidean norm of any subgradient of $f_{i}$ on the ball of radius $D$ around the origin, $L=\sum_{j=1}^{n}L_{j}$, $B_{i}=\sqrt{d}(L_{i}+c_{i})$, while the scalars $\lambda\in(0,1)$ and $\delta>0$ are functions of the graph sequence $\{G(t)\}$ which satisfy

Moreover, if each of the graphs $G(t)$ is regularA directed graph $G(t)$ is regular if every out-degree and every in-degree of a node in $G(t)$ equals $d(t)$ for some $d(t)$., then

and $\sigma_{2}(A)$ is the second-largest singular value of $A$.

Note that each term on the right-hand side of the bound in the above theorem has a $\tau$ in the denominator and an $\ln(\tau-1)$ or a constant in the numerator. The convergence time above should therefore be interpreted as proving a decay with time which decreases at an expected $O((\ln t)/t)$ rate with the number of iterations $t$. Note that this is an extended and corrected version of a result from the conference version of this paper .

We remark that our result is new even for undirected graphs, which are included as a special case of the above theorem; indeed, to our knowledge, we are the first to demonstrate a decay rate of $O((\ln t)/t)$ for stochastic gradient descent over time-varying undirected graphs (however, recall our earlier discussion of which derived similar decay rates for the deterministic case with a fixed undirected graph). Surprisingly, the undirected and directed cases do not appear to be very different; the main difference seems to do with the constant $\delta$ and $\lambda$. Indeed, note that the bounds for the constants $\delta$ and $\lambda$ which appear in the bound are rather large in the most general case; in particular, they grow exponentially in the number of nodes $n$. At present, this scaling appears unavoidable: those constants reflect the best available bounds on the performance of average consensus protocols in directed graphs, and it is an open question whether average consensus on directed graphs can be done in time polynomial in $n$. In the case of regular graphs, the bounds scale polynomially in $n$ due to the availability of good bounds on the convergence of consensus. Similarly, for undirected case, the possibility of modifyin the protocol by instead choosing a symmetric matrix $A$ leads to good bounds on $\delta$ and $\lambda$ . Our results therefore further motivate problem of finding consensus algorithms with good convergence times, especially on directed graphs.

Finally, we remark that choosing a stepsize parameter $p$ so that Eq. (10) is satisfied is most easily done by instead insuring that $p(\min_{i}\mu_{i})/n>4$. This is a more conservative condition than that of Eq. (10) but ensuring it requires the nodes only to compute $\min_{i}\mu_{i}$. This is more convenient because the minimum of any collection of numbers $r_{1},\ldots,r_{n}$ (with $r_{i}$ stored at node $i$) can be easily computed by the following distributed protocol: node $i$ sets its initial value to $r_{i}$ and then repeatedly replaces its value with the minimum of the values of its in-neighbors. It is easy to see that on any fixed network, this process converges to the minimum in as many steps as the diameter. Furthermore, on any $B$-strongly-connected sequence this processes converges in the optimal $O(nB)$ steps. Thus, the pre-processing required to come up with a suitable step-size parameter $p$ is reasonably small.

A shortcoming of Theorem 1 is that we must assume that the iterates ${\bf z}_{i}(t)$ remain bounded (as opposed to obtaining this as a by-product of the theorem). This is a common situation in the analysis of subgradient-type methods in non-differentiable optimization: the boundedness of the iterates or their subgradients often needs to be assumed in advance in order to obtain a result about convergence rate.

We next show that we can remedy this shortcoming at the cost of imposing additional assumptions on the functions $f_{i}$, namely that they are differentiable and their gradients are Lipschitz.

Each $f_{i}$ is differentiable and its gradients are Lipschitz continuous, i.e., for a scalar $M_{i}>0$,

Suppose that Assumption 1 and Assumption 2 hold and suppose $\lim_{t\to\infty}\alpha(t)=0$. Then, there exists a scalar $D$ such that with probability $1$, $\sup_{t}\|{\mathbf{z}}_{i}(t)\|\leq D$ for all $i$.

The proof of this theorem is constructive in the sense than an explicit expression for $D$ can be derived in terms of the level set growth of the functions $f_{j}$. Additionally, the scalar $D$ depends on the initial points ${\mathbf{x}}_{i}(0)$, the step-size sequence $\alpha(t)$, the functions $f_{i}(\cdot)$, the Lipschitz constants $M_{j}$ and the noise bounds $c_{j}$ (cf. (2)).

Putting Theorems 1 and 2 together, we obtain our main result: for strongly convex functions with Lipschitz gradients, the stochastic (sub)gradient-push with appropriately chosen step-size and averaging strategy converges at an $O((\ln t)/t)$ rate.

III Proof of Theorem 1

We briefly sketch the main ideas of the proof of Theorem 1. First, we will argue that if the subgradient terms in the subgradient-push protocol are bounded, then as a consequence of the decaying stepsize $\alpha(t)$, the protocol will achieve consensus. We will then analyze the evolution of the average $\bar{\mathbf{x}}(t)$ and show that, as a consequence of the protocol achieving consensus, $\bar{\mathbf{x}}(t)$ satisfies approximately the same recursion as the iterates of the ordinary subgradient method. Finally, the key idea in our proof is the observation in that, for a noisy gradient update on a strongly convex function, a decay of $O(1/t)$ can be achieved by a simple averaging of iterates that places more weight on recent iterations, specifically by weighting the $t$’th iterate proportional to $t$. Here, we show that, for the perturbed subgradient method which is followed by the averaging step $\bar{\mathbf{x}}(t)$, a nearly identical rate $O((\ln t)/t)$ can be achieved.

Our starting point is an analysis of a perturbation of the so-called push-sum protocol of for computing averages in directed networks. We next describe this perturbed push-sum protocol. Every node $i$ maintains scalar variables $x_{i}(t),y_{i}(t),z_{i}(t),w_{i}(t)$, where $y_{i}(0)=1$ for all $i$. Every node $i$ updates these variables according to the following rule: for $t\geq 0$,

where $\epsilon_{i}(t)$ is some (perhaps adversarially chosen) perturbation at time $t$. Without the perturbation term $\epsilon_{i}(t)$, the method in Eq. (12) is called push-sum. For the perturbed push-sum method above in Eq. (12), we have that the following is true.

Consider the sequences $\{z_{i}(t)\}$, $i=1,\ldots,n,$ generated by the method in Eq. (12). Assuming that the graph sequence $\{G(t)\}$ is $B$-strongly-connected, we have that for all $t\geq 1$,

We refer the reader to for a proof where this statement is Lemma 1. Informally, the push-sum protocol ensures that all $z_{i}(t)$ track the running averages $\frac{{\bf 1}^{\prime}x(t)}{n}$ with a geometric rate $\lambda$, while the perturbations $\epsilon_{i}(t)$ push the node values apart. The perturbations can be viewed as an external force that influences the node values and causes additional disagreement. Lemma 1 provides a bound on the size of the disagreements among the agents in terms of the network caused imbalances and the imbalances due to the external force.

Consider the update of Eq. (12) with the scalar variables $x_{i}(t),w_{i}(t),z_{i}(t),\epsilon_{i}(t)$ replaced by the vector variables ${\mathbf{x}}_{i}(t),{\mathbf{w}}_{i}(t),{\mathbf{z}}_{i}(t),{\bf e}_{i}(t)$ for each $i=1,\ldots,n$. Assuming that the graph sequence $\{G(t)\}$ is $B$-strongly-connected, for all $i=1,\ldots,n,t\geq 1$ we have

where $\delta,\lambda$ satisfy the same inequalities as in Theorem 1.

we then have that for all $i=1,\ldots,n$ and all $\tau\geq 1,$

The parameters $\delta>0$ and $\lambda\in(0,1)$ satisfy the same inequalities as in Theorem 1.

We use Corollary 1. The first term in the estimate follows immediately. The second term requires some attention:

and the result follows from the usual bound on the sum of harmonic series, $\sum_{s=1}^{\tau}\frac{1}{s}\leq 1+\ln\tau$. ∎

In the proof of Theorem 1, we also use the following result, which is a generalization of Lemma 8 in . Before stating this lemma, we introduce some notation. We define ${\cal F}_{t}$ to be all the information generated by the stochastic gradient-push method by time $t$, i.e., all the ${\mathbf{x}}_{i}(k),{\mathbf{z}}_{i}(k),{\mathbf{w}}_{i}(k),y_{i}(k),{\mathbf{g}}_{i}(k)$ and so forth for $k=1,\ldots,t$. We then have the following lemma.

where $L_{j}=\max_{\|u\|\leq D}\nabla f_{j}(u)$ and constants $c_{j}$ are from (2).

where the last equality follows from the definition of ${\mathbf{z}}_{i}(t+1)$. Since the matrices $A(t)$ are column stochastic, the sums of $y_{i}(t)$ are preserved at all times, i.e., $\sum_{i=1}^{n}y_{i}(t)=n$ for all $t$. Furthermore, $y_{i}(t)>0$ for all $i$ and $t$. Thus, relation (19) shows that each vector $\bar{\mathbf{x}}(t)$ is a convex combination of ${\mathbf{z}}_{i}(t+1)$, $i=1,\ldots,n,$ implying that for all $t\geq 0$

Thus, with probability 1, we have $\|\bar{x}(t)\|\leq D.$

We next show the relation stated in the lemma. Due to the column-stochasticity of the matrices $A(t)$, for the stochastic gradient-push update of Eq. (3) we have

Taking expectations of both sides with respect to ${\cal F}_{t}$, and using ${\mathbf{g}}_{j}(t+1)=\nabla f_{j}({\mathbf{z}}_{j}(t+1))+{\bf N}_{j}({\mathbf{z}}_{j}(t+1))$ (see Eq. (1)) and the relation

Next, we upper-bound the last term in the preceding relation. By using the inequality $(\sum_{j=1}^{n}a_{j})^{2}\leq n\sum_{j=1}^{n}a_{j}^{2}$ we obtain that with probability $1$,

since $\|{\mathbf{g}}_{j}(t+1)\|\leq\max_{\|u\|\leq D}\|\nabla f_{j}(u)\|+c_{j}$ from Eq. (2). This implies for all $t\geq 1$,

Now, consider each of the cross-terms $\nabla f_{j}({\mathbf{z}}_{j}(t+1))^{\prime}(\bar{\mathbf{x}}(t)-{\mathbf{v}})$ in (22), for which we write

By using the Cauchy-Schwarz inequality we have with probability 1,

As for the term $\nabla f_{j}({\mathbf{z}}_{j}(t+1))^{\prime}({\mathbf{z}}_{j}(t+1)-{\mathbf{v}})$, we use the fact that the function $f_{j}$ is $\mu_{i}$-strongly convex to obtain

By writing $f_{j}({\mathbf{z}}_{j}(t+1))-f_{j}({\mathbf{v}})=(f_{j}({\mathbf{z}}_{j}(t+1))-f_{j}(\bar{\mathbf{x}}(t))+(f_{j}(\bar{\mathbf{x}}(t))-f_{j}({\mathbf{v}}))$ and by using the convexity of $f_{j}$, we have

where $\nabla f_{j}(\bar{\mathbf{x}}(t))$ is a subgradient of $f_{j}$ at $\bar{\mathbf{x}}(t)$. In view of relation (20), the sub-gradients $\nabla f_{j}(\bar{x}(t))$ are also bounded with probability 1, so we have

From relation (30), (32) and (34), we conclude that with probability 1,

By substituting the estimates of Eqs. (28) and (36) back in relation (25), and using $F({\mathbf{x}})=\sum_{j=1}^{n}f_{j}({\mathbf{x}})$ we obtain

Plugging this relation into Eq. (22), we obtain the statement of this lemma. ∎

With Lemma 2 in place, we are now ready to provide the proof of Theorem 1. Besides Lemma 2, our arguments will also crucially rely on the results established earlier for the perturbed push-sum method.

The function $F=\sum_{i=1}^{n}f_{i}$ has a unique minimum which we will denote by ${\mathbf{z}}^{*}$. In Lemma 2 we let ${\mathbf{v}}={\mathbf{z}}^{*}$ to obtain for all $t\geq 0$,

Next, we estimate the term $F(\bar{\mathbf{x}}(t))-F({\mathbf{z}}^{*})$ in the above equation by breaking it into two parts. On the one hand,

On the other hand, since the function $F$ is Lipschitz continuous with constant $L=L_{1}+\cdots+L_{n}$ over the ball of radius $D$ around the origin to which all ${\mathbf{z}}_{j}(t),\overline{{\mathbf{x}}}(t)$ always belong (by assumption and by Lemma 2), we also have that for any $i=1,\ldots,n,$

Therefore, using the preceeding two estimates we obtain for all $i=1,\ldots,n$,

Combining relation (42) with Eq. (37), we obtain that for each $i=1,\ldots,n$, with probability 1,

Now plugging in the expression for $\alpha(t)$ and using the definition of $p$ to combine the first two terms, we see that for all $i=1,\ldots,n$ and all $t\geq 0$,

where $q^{2}=\sum_{j=1}^{n}(L_{j}+c_{j})^{2}$. We multiply the preceding relation by $t(t+1)$, and we obtain that for all $i=1,\ldots,n$ and all $t\geq 1$,

By iterating the expectations in (45) and applying the resulting inequality, recursively, we obtain that all $\tau\geq 2$,

Thus, by Corollary 2 we obtain for all $i=1,\ldots,n$,

Upon substituting the preceding inequality into relation (50) and dividing both sides by $\tau(\tau-1)$, after re-arranging the terms, we obtain for all $\tau\geq 2,$

Combining the first two terms on the right hand side of the preceding relation, using $L=\sum_{j=1}^{n}L_{j}$ and canceling $p/n$ from both sides, we get

Finally, by convexity we have for each $i=1,\ldots,n$,

Putting together Eqs. (53) and (56) concludes the proof. ∎

IV Proof of Theorem 2

We begin by briefly sketching the main idea of the proof. The proof proceeds by simply arguing that if $\max_{i}\|{\mathbf{z}}_{i}(t)\|$ gets large, it decreases. Since the stochastic subgradient-push protocol (Eq. (3)) is somewhat involved, proving this will require some involved arguments relying on the level-set boundedness of strongly convex functions with Lipschitz gradients and some special properties of element-wise ratios of products of column-stochastic matrices.

Our starting point is a lemma that exploits the structure of strongly convex functions with Lipschitz gradients.

where $R=\max_{z\in{\cal V}}\left\{\|z\|+(\mu/(8M^{2}))\|\nabla q(z)\|\right\}+(\mu c)/(8M^{2})$.

The strong convexity of the function $q$ implies

For the last term in the preceding relation, we write

where the last inequality is obtained by using Eq. (59) and by exploiting the Lipchitz property of the gradient of $q$. Similarly, using the given growth-property of $\|\phi(v)\|$ we obtain

By substituting Eqs. (60)–(62) in relation (58), we find

which for $\alpha\in{{(0,\frac{\mu}{8M^{2}}]}}$ yields

Define the set ${\cal V}^{\prime}$ to be the following level set of $q$:

Being the level-set of a strongly-convex function, the set ${\cal V}^{\prime}$ is compact (see Proposition 2.3.1(b), page 93). Let $B({\bf 0},\epsilon)$ be the Euclidean ball centered at the origin and with a radius $\epsilon>0$. Define the set ${\cal V}$ as follows:

If $v$ is such that $\|v\|\geq 4c/\mu$ and $q(v)\geq q(0)+2\alpha(\|\nabla q(0)\|^{2}+c^{2})$ (i.e., $v\not\in{\cal V}$), then by relation (63), we obtain $\|u\|^{2}\leq\|v\|^{2}.$ On the other hand, if $v\in{\cal V}$, then by using the definition of $u$ and the bound $||\phi(v)||\leq c$ we can see that

By using the upper bound on $\alpha$ we obtain the stated relation. ∎

We next state an important relation for the images of two vectors under a linear transformation with a column-stochastic matrix. This is a generalization of a relation from , Section 7.3.2.

Define the vectors $r$ and $\hat{r}$ with their $i$’th entries given by $r_{i}=u_{i}/v_{i}$ and $\hat{r}_{i}=\hat{u}_{i}/\hat{v}_{i}$, respectively. Then, we have

Since $\hat{u}_{i}=\hat{v}_{i}\hat{u}_{i}$ and $u_{j}=v_{j}r_{j}$, the preceding equation can be rewritten as

Since $v$ has all entries positive and $P$ has positive diagonal entries, it follows that $\hat{v}$ also has all entries positive. Therefore,

Define the matrix $Q$ from this equation, i.e., $Q_{ij}=\frac{P_{ij}v_{j}}{\hat{v}_{i}}$ for all $i,j$. The fact that $Q$ is row-stochastic follows from $\hat{v}=Pv$. ∎

Informally speaking, the above lemma reduces the “push-sum” iteration to a simple stochastic “consensus” update. We note that it could be used to provide considerable simplifications of many of the arguments that have been used to show the convergence of push-sum in the past, though this is beyond the scope of the present paper. With this lemma in place, we now proceed to prove our second theorem.

Letting $y(t)$ be the vector with entries $y_{i}(t)$, we can write $y(t+1)=A(t)y(t),$ where $A(t)$ is the matrix given in Eq. (11). Thus, since $y_{i}(0)=1$ for all $i$, we have

where ${\bf 1}$ is the vector with all entries equal to 1. Under Assumption 1(a), we have shown in (see there Corollary 2(b)) that for all $i$,

Thus, using the definition of ${\mathbf{x}}_{i}(t+1)$, we can see that for all $t\geq 1$,

Since the matrix $A(t)A(t-1)\cdots A(0)$ is column stochastic and $y(0)={\bf 1}$, we have that $\sum_{i=1}^{n}y_{i}(t)=n$. Therefore, $y_{i}(t)\leq n$, which together with Eq. (65) and $\alpha(t)\to 0$ yields

Therefore, for every $i$, there is a time $\tau_{i}>1$ such that $\alpha(t)/y_{i}(t)\leq\frac{\mu_{i}}{{{8M_{i}^{2}}}}$ for all $t\geq\tau_{i}$. Hence, for each $i$, Lemma 3 applies to the vector ${\mathbf{x}}_{i}(t)/y_{i}(t)$ for $t\geq\tau_{i}$. By Lemma 3, it follows that for each function $f_{i}$, there is a compact set ${\cal V}_{i}$ and a time $\tau_{i}$ such that for all $t\geq\tau_{i}$,

Let $\tau=\max_{i}{\tau_{i}}$. By using the mathematical induction, we will prove that for all $t\geq\tau$,

where $\bar{R}=\max\{\max_{i}R_{i},\max_{j}\|{\mathbf{z}}_{j}(\tau)\|\}$. Indeed, relation (70) is true for $t=\tau$. Suppose it is true at some time $t{{\geq}}\tau$. Then, by Eq. (69) we have

where $Q(t)$ is a row stochastic matrix with entries $Q_{ij}(t)=\frac{A_{ij}(t)y_{j}(t)}{y_{i}(t+1)}$. By the convexity of the Euclidean norm, it follows that for all $i$,

which together with Eq. (71) yields $\|{\mathbf{z}}_{i}(t+1)\|\leq\bar{R}$, thus implying that at time $t+1$ we have

Hence, Eq. (70) is valid for all $t\geq\tau$.

Note that the constant $\bar{R}$ is random as it depends on the random vectors $z_{i}(\tau)$, $i=1,\ldots,n$, where the time $\tau$ is deterministic. However, we next argue that we may replace $\bar{R}$ with a deterministic constant which upper bounds all $\|{\mathbf{z}}_{i}(t+1)\|,i=1,\ldots,n,t\geq 1$. Indeed, it would suffice to find a constant which upper bounds all $\|z_{i}(t)\|$ with $i=1,\ldots,n$ and $t=1,\ldots,\tau$.

Using Eqs. (66) and (72), we can see that for all $t\geq 1$,

Let ${\mathbf{z}}_{j}^{*}$ be the minimizer of $f_{j}$, which exists and is unique due to the strong convexity of $f_{j}$. Then, by Assumption 2 it follows that

where $\gamma_{1}=1+(\bar{\alpha}/\delta)\max_{j}M_{j}$, $\gamma_{2}=(\bar{\alpha}/\delta)\max_{j}M_{j}$, $\gamma_{3}=(\bar{\alpha}/\delta)\max_{j}c_{j}$, and $\bar{\alpha}=\max_{t}\alpha(t)$. Thus, using the preceding relation recursively for $t=1,\ldots,\tau-1,$ and the fact that the initial points ${\mathbf{x}}_{i}(0)$ are deterministic, we conclude that there exists a uniform deterministic bound on $\|{\mathbf{z}}_{i}(t)\|$ for all $t\geq 1$ and $i$. ∎

Remark: It is possible to generalize our results to more general models of noise where

and each $\epsilon_{i}$ is small compared to $\mu_{i}$. We omit the details as the proofs are essentially identical to the proofs given here for the case of $\epsilon_{i}=0$.

V Simulations

We report some simulations of the subgradient-push method which experimentally demonstrate its performance. We consider the scalar function $F(\theta)=\sum_{i=1}^{n}p_{i}(\theta-u_{i})^{2}$ where $u_{i}$ is a variable that is known only to node $i$. This is a canonical problem in distributed estimation, whereby the nodes are attempting to measure a parameter $\widehat{\theta}$. Each node $i$ measures $u_{i}=\widehat{\theta}+w_{i}$, where $w_{i}$ are jointly Gaussian and zero mean. Letting $p_{i}$ be the inverse of the variance of $w_{i}$, the maximum likelihood estimate is the minimizer $\theta^{*}$ of $F(\theta)$ ($\theta^{*}$ is unique provided that $p_{i}>0$ for at least one $i$). Each $p_{i}$ is a uniformly random variable taking values between and $1$. The initial points $x_{i}(0)$ are generated as independent random variables, each with a standard Gaussian distribution. This setup is especially attractive since the optimal solution can be computed explicitly (it is a weighted average of the $u_{i}$) allowing us to see exactly how far from optimality our protocol is at every stage.

The subgradient-push method is run for 200 iterations with the stepsize $\alpha(t)=p/t$ and $p=2n/(\sum_{i=1}^{n}p_{i})$. The graph sequence is constructed over 1000 nodes with a random connectivity pattern.

Figure 1 shows the results obtained for simple random graphs where every node has two out-neighbors, one belonging to a fixed cycle and the other one chosen uniformly at random at each step. The top plot shows how $\ln(|\widetilde{z_{i}}(t)-\theta^{*}|)$ decays on average (over 25 Monte Carlo simulations) for five randomly selected nodes. The bottom plot shows a sample of $\ln(|\widetilde{z_{i}}(t)-\theta^{*}|)$ for a single Monte Carlo run and the same selection of 5 nodes.

Figure 2 illustrates the same quantities for the sequence of graphs which alternate between two (undirected) star graphs.

We see that the error decays at a fairly speedy rate, especially given both the relatively large number of nodes in the system (a thousand) and the sparsity of the graph at each stage (every node has two out-neighbors). Our simulation results suggest the gradient-push methods we have proposed have the potential to be effective tools for network optimization problems. For example, the simulation of Figure 1 shows that a relatively fast convergence time can be obtained if each node can support only a single long-distance out-link.

VI Conclusion

We have considered a variant of the subgradient-push method of our prior work , where the nodes have access to noisy subgradients of their individual objective functions $f_{i}$. Our main result was that the functions $f_{i}$ are strongly convex functions with Lipchitz gradients, we have established $O(\ln t/t)$ convergence rate of the method, which is an improvement of the previously known rate $O(\ln t/\sqrt{t})$ for (noiseless) subgradient-push method shown in .

Our work suggests a number of open questions. Our bounds on the performance of the (sub)gradient-push directly involve the convergence speed $\lambda$ of consensus on directed graphs. Thus the problem of designing well-performing consensus algorithms is further motivated by this work. In particular, a directed average consensus algorithm with polynomial scaling with $n$ on arbitrary time-varying graphs would lead to polynomial convergence-time scalings for distributed optimization over time-varying directed graphs. However, such an algorithm is not available to the best of the authors’ knowledge.

Moreover, it would be interesting to relate the convergence speed of distributed optimization procedures to the properties possessed by the individual functions. We have begun on this research program here by showing an improved rate for strongly convex functions with Lipschitz gradients. However, one might expect that stronger results might be available under additional assumptions. It is not clear, for example, under what conditions a geometric rate can be achieved when graphs are directed and time-varying, if at all.

Finally, in many applications convergence speed should be measured not by the number of iterations but by different metrics. For example, it may be appropriate to count the number of bits that have to be exchanged before all nodes are close to the solution. Alternatively, when some of the variables correspond to physical positions which must be adjusted as a result of the protocol, the dominating factor may be the total distance traveled by each node. Furthermore, there may be tradeoffs between these metrics that we do not at present understand. Understanding the performance of protocols for convex optimization in these scenarios remains an open problem.

References