Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization

Introduction

A number of problems that arise in the context of wired and wireless networks can be posed as the minimization of a sum of functions, when each component function is available only to a specific agent . Often, it is not efficient, or not possible, for the network agents to share their objective functions with each other or with a central coordinator. In such scenarios, distributed algorithms that only require the agents to locally exchange limited and high level information are preferable. For example, in a large wireless network, energy is a scarce resource and it might not be efficient for a central coordinator to learn the individual objective functions from each and every agent . In a network of databases from which information is to be mined, privacy considerations may not allow the sharing of the objective functions . In a distributed network on a single chip, for the chip to be fault tolerant, it is desirable to perform the processing in a distributed manner to account for the statistical process variations.

We consider constrained minimization of a sum of convex functions, where each component function is known partially (with stochastic errors) to a specific network agent. The algorithm proposed builds on the distributed algorithm proposed in for the unconstrained minimization problem. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent averages the received iterates with its own iterate, and adjusts the iterate by using subgradient information (known with stochastic errors) of its own function and by projecting onto the constraint set. The inter-agent information exchange model is a synchronous and delayless version of the computational model proposed by Tsitsiklis . The algorithm is distributed since there is no central coordinator. The algorithm is local since each agent uses only locally available information (its objective function) and communicates locally with its immediate neighbors.

Related to this work are the distributed incremental algorithms, where the network agents sequentially update an iterate sequence in a cyclic or a random order . The effects of stochastic errors on these algorithms have been investigated in . In an incremental algorithm, there is a single iterate sequence and only one agent updates the iterate at a given time. Thus, while being distributed and local, incremental algorithms differ fundamentally from the algorithm studied in this paper (where all agents update simultaneously). Also related are the optimization algorithms in . However, these algorithms are not local as the complete objective function information is available to each and every agent, with the aim of distributing the processing.

The work in this paper is also related at a much broader level to the distributed consensus algorithms . In these algorithms, each agent starts with a different value and through local information exchange, the agents eventually agree on a common value. The effect of random errors on consensus algorithms have been investigated in . In addition, since we are interested in the effect of stochastic errors, our paper is also related to the literature on stochastic subgradient methods .

We consider general stochastic errors that have uniformly bounded second moments and obtain bounds on the limiting performance of the algorithm in mean for diminishing and non-diminishing stepsizes. When the means of the errors diminish, we prove that there is mean consensus between the agents and mean convergence to the optimum function value for diminishing stepsizes. When the mean errors diminish sufficiently fast, we strengthen the results to consensus and convergence of the iterates to an optimal solution with probability 1 and in mean square.

Our work expands the multi-agent distributed optimization framework studied in . The new contributions are: 1) the study of the effects of stochastic errors in subgradient evaluations; 2) the consideration of constrained optimization problem within the distributed multi-agent setting. The presence of the constraint set complicates the analysis as it introduces non-linearities in the system dynamics. The non-linearity issues that we face have some similarities to those in the constrained consensus problem investigated in , though the problems are fundamentally different. The presence of subgradient stochastic errors adds another layer of complexity to the analysis as the errors made by each agent propagate through the network to every other agent and also across time, making the iterates statistically dependent across time and agents.

The rest of the paper is organized as follows. In Section 2, we formulate the problem, describe the algorithm and state our basic assumptions. In Section 3 we state some results from literature that we use in the analysis, while in Section 4, we derive two important lemmas that form the backbone of the analysis. In Section 5, we study the convergence properties of the method in mean, and in Section 6 we focus on the convergence properties with probability 1 and in mean square. Finally, we discuss some implications and provide some concluding remarks in Sections 7 and 8.

Problem, algorithm and assumptions

In this section, we formulate the problem of interest and describe the algorithm that we propose. We also state and discuss our assumptions on the agent connectivity and information exchange.

We consider a network of $m$ agents that are indexed by $1,\ldots,m$. Often, when convenient, we index the agents by using set $V=\{1,\ldots,m\}$. The network objective is to solve the following constrained optimization problem:

where $X\subseteq\Re^{n}$ is a constraint set and $f_{i}:X\to\Re$ for all $i$. Related to the problem we use the following notation

We are interested in the case when the problem in (2) is convex. Specifically, we assume that the following assumption holds.

The functions $f_{i}$ and the set $X$ are such that

The functions $f_{i},\ i\in V$ are defined and convex over an open set that contains the set $X$.

The function $f_{i}$ is known only partially to agent $i$ in the sense that the agent can only obtain a noisy estimate of the function subgradient. The goal is to solve problem (2) using an algorithm that is distributed and local.See for wireless network applications that can be cast in this framework.

We make no assumption on the differentiability of the functions $f_{i}.$ At points where the gradient does not exist, we use the notion of subgradients. A vector $\nabla f_{i}$ is a subgradient of $f_{i}$ at a point $x\in{\rm dom\,f}$ if the following relation holds

Since the set $X$ is contained in an open set over which the functions are defined and convex, a subgradient of $f_{i}$ exists at any point of the set $X$ (see or ).

2 Algorithm

To solve the problem in (2) with its inherent decentralized information access, we consider an iterative subgradient method. The iterations are distributed accordingly among the agents, whereby each agent $i$ is minimizing its convex objective $f_{i}$ over the set $X$ and locally exchanging the iterates with its neighbors.

Let $w_{i,k}$ be the iterate with agent $i$ at the end of iteration $k.$ At the beginning of iteration $k+1$, agent $i$ receives the current iterate of a subset of the agents. Then, agent $i$ computes a weighted average of these iterates and adjusts this average along the negative subgradient direction of $f_{i}$, which is computed with stochastic errors. The adjusted iterate is then projected onto the constraint set $X.$ Mathematically, each agent $i$ generates its iterate sequence $\{w_{i,k}\}$ according to the following relation:

starting with some initial iterate $w_{i,0}\in X.$ Here, $\nabla f_{i}\left(v_{i,k}\right)$ denotes the subgradient of $f_{i}$ at $v_{i,k}$ and $\epsilon_{i,k+1}$ is the stochastic error in the subgradient evaluation. The scalar $\alpha_{k+1}>0$ is the stepsize and $P_{X}$ denotes the Euclidean projection onto the set $X.$ The vector $v_{i,k}$ is the weighted average computed by agent $i$ and is given by

where $N_{i}(k+1)$ denotes the set of agents whose current iterates are available to agent $i$ in the $(k+1)$-st iteration. We assume that $i\in N_{i}(k+1)$ for all agents and at all times $k$. The scalars $a_{i,j}(k+1)$ are the non-negative weights that agent $i$ assigns to agent $j$’s iterate. We will find it convenient to define $a_{i,j}(k+1)$ as for $j\notin N_{i}(k+1)$ and rewrite (5) as

This is a “consensus”-based step ensuring that, in a long run, the information of each $f_{i}$ reaches every agent with the same frequency, directly or through a sequence of local communications. Due to this, the iterates $w_{j,k}$ become eventually “the same” for all $j$ and for large enough $k$. The update step in (4) is just a subgradient iteration for minimizing $f_{i}$ over $X$ taken after the “consensus”-based step.

3 Additional assumptions

In addition to Assumption 1, we make some assumptions on the inter-agent exchange model and the weights. The first assumption requires the agents to communicate sufficiently often so that all the component functions, directly or indirectly, influence the iterate sequence of any agent. Recall that we defined $N_{i}(k+1)$ as the set of agents that agent $i$ communicates with in iteration $k+1.$ Define $(V,E_{k+1})$ to be the graph with edges

There exists a scalar $Q$ such that the graph $(V,\cup_{l=1,\ldots,Q}E_{k+l})$ is strongly connected for all $k.$

It is also important that the influence of the functions $f_{i}$ is “equal” in a long run so that the sum of the component functions is minimized rather than a weighted sum of them. The influence of a component $f_{j}$ on the iterates of agent $i$ depends on the weights that agent $i$ uses. To ensure equal influence, we make the following assumption on the weights.

$a_{i,j}(k+1)\geq 0$, and $a_{i,j}(k+1)=0$ when $j\notin N_{i}(k+1),$

There exists a scalar $\eta,$ $0<\eta<1,$ such that $a_{i,j}(k+1)\geq\eta$ when $j\in N_{i}(k+1),$

Assumptions 3a and 3b state that each agent calculates a weighted average of all the iterates it has access to. Assumption 3c ensures that each agent gives a sufficient weight to its current iterate and all the iterates it receives.The agents need not be aware of the common bound $\eta.$ Assumption 3d, together with Assumption 2, as we will see later, ensures that all the agents are equally influential in the long run. In other words, Assumption 3d is crucial to ensure that $\sum_{i=1}^{m}f_{i}$ is minimized as opposed to a weighted sum of the functions $f_{i}$ with non-equal weights. To satisfy Assumption 3d, the agents need to coordinate their weights. Some coordination schemes are discussed in .

Preliminaries

In this section, we state some results for future reference.

For any vectors $v_{1},\ldots,v_{M}\in\Re^{n},$ we have

The preceding relation states that the average of a finite set of vectors minimizes the sum of distances between each vector and any vector in $\Re^{n}$, which can be verified using the first-order optimality conditions.

Both the Euclidean norm and its square are convex functions, i.e., for any vectors $v_{1},\ldots,v_{M}\in\Re^{n}$ and nonnegative scalars $\beta_{1},\ldots,\beta_{M}$ such that $\sum_{i=1}^{M}\beta_{i}=1,$ we have

The following inequality is the well-knownSee for example , Proposition 2.2.1. non-expansive property of the Euclidean projection onto a nonempty, closed and convex set $X$,

2 Scalar sequences

Let $\{\gamma_{k}\}$ be a scalar sequence.

If $\mathop{\rm limsup}_{k\to\infty}\gamma_{k}=\gamma$ and $\{\zeta_{k}\}$ is a positive scalar sequence with $\sum_{k=1}^{\infty}\zeta_{k}=~{}\infty,$ then $\mathop{\rm limsup}_{K\to\infty}\frac{\sum_{k=0}^{K}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{K}\zeta_{k}}\leq\gamma.$ In addition, if $\mathop{\rm liminf}_{k\to\infty}\gamma_{k}=\gamma$, then $\lim_{K\to\infty}\frac{\sum_{k=0}^{K}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{K}\zeta_{k}}~{}=~{}\gamma.$

(a) Let $\epsilon>0$ be arbitrary. Since $\gamma_{k}\to\gamma$ and for all $k$, there is an index $K$ such that $|\gamma_{k}-\gamma|\leq\epsilon$ for all $k\geq K$. For all $k\geq K+1$, we have

(b) Let $\sum_{k=0}^{\infty}\gamma_{k}<\infty.$ For any integer $M\geq 1$, we have

(c) Since $\mathop{\rm limsup}_{k\to\infty}\gamma_{k}=\gamma,$ for every $\epsilon>0$ there is a large enough $K$ such that $\gamma_{k}\leq\gamma+\epsilon$ for all $k\geq K.$ Thus, for any $M>K,$

By letting $M\to\infty$ and using $\sum_{k}\zeta_{k}=\infty,$ we see that $\mathop{\rm limsup}_{M\to\infty}\ \frac{\sum_{k=0}^{M}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{M}\zeta_{k}}\leq\gamma+\epsilon,$ and since $\epsilon$ is arbitrary, the result for the limit superior follows.

Analogously, if $\mathop{\rm liminf}_{k\to\infty}\gamma_{k}=\gamma,$ then for every $\epsilon>0$ there is a large enough $K$ such that $\gamma_{k}\geq\gamma-\epsilon$ for all $k\geq K.$ Thus, for any $M>K,$

Letting $M\to\infty$ and using $\sum_{k}\zeta_{k}=\infty,$ we obtain $\mathop{\rm liminf}_{M\to\infty}\ \frac{\sum_{k=0}^{M}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{M}\zeta_{k}}\geq\gamma-\epsilon.$ Since $\epsilon>0$ is arbitrary, we have $\mathop{\rm liminf}_{M\to\infty}\ \frac{\sum_{k=0}^{M}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{M}\zeta_{k}}\geq\gamma$. This relation and the relation for the limit superior yield $\lim_{M\to\infty}\ \frac{\sum_{k=0}^{M}\gamma_{k}\zeta_{k}}{\sum_{k=0}^{M}\zeta_{k}}=\gamma$ when $\gamma_{k}\to\gamma$. ∎

3 Matrix convergence

Let $A(k)$ be the matrix with $(i,j)$-th entry equal to $a_{i,j}(k).$ As a consequence of Assumptions 3a, 3b and 3d, the matrix $A(k)$ is doubly stochasticThe sum of its entries in every row and in every column is equal to $1$.. Define, for all $k,s$ with $k\geq s,$

We next state a result from (Corollary 1) on the convergence properties of the matrix $\Phi(k,s).$ Let $[\Phi(k,s)]_{i,j}$ denote the $(i,j)$-th entry of the matrix $\Phi(k,s),$ and let $e\in\Re^{m}$ be the column vector with all entries equal to $1.$

$\lim_{k\to\infty}\Phi(k,s)=\frac{1}{m}\,ee^{T}$ for all $s.$

Further, the convergence is geometric and the rate of convergence is given by

4 Stochastic convergence

We next state some results that deal with the convergence of a sequence of random vectors. The first result is the well known Fatou’s lemma .

Let $\{X_{i}\}$ be a sequence of non-negative random variables. Then

The next result is due to Robbins and Siegmund (Lemma 11, Chapter 2.2, ).

Let $\{B_{k}\},\{D_{k}\},$ and $\{H_{k}\}$ be non-negative random sequences and let $\{\zeta_{k}\}$ be a deterministic nonnegative scalar sequence. Let $G_{k}$ be the $\sigma-$algebra generated by $B_{1},\ldots,B_{k},D_{1},\ldots,D_{k},H_{1},\ldots,H_{k}.$ Suppose that $\sum_{k}\zeta_{k}<\infty,$

and $\sum_{k}H_{k}<\infty$ with probability 1. Then, the sequence $\{B_{k}\}$ converges to a non-negative random variable and $\sum_{k}D_{k}<\infty$ with probability 1, and in mean.

Basic relations

In this section, we derive two basic relations that form the basis for the analysis in this paper. The first of them deals with the disagreements among the agents, and the second deals with the agent iterate sequences.

The agent disagreements are typically thought of as the norms $\|w_{i,k}-w_{j,k}\|$ of the differences between the iterates $w_{i,k}$ and $w_{j,k}$ generated by different agents according to (4)–(5). Alternatively, the agent disagreements can be measured with respect to a reference sequence, which we adopt here. In particular, we study the behavior of $\|y_{k}-w_{i,k}\|,$ where $\{y_{k}\}$ is the auxiliary vector sequence defined by

In the next lemma, we provide a basic estimate for $\|y_{k}-w_{j,k}\|.$ The rate of convergence result from Lemma 2 plays a crucial role in obtaining this estimate.

Let Assumptions 1a, 2, and 3 hold. Assume that the subgradients of $f_{i}$ are uniformly bounded over the set $X$, i.e., there are scalars $C_{i}$ such that

Using the matrices $\Phi(k,s)$ defined in (11) we can write

Using (14), we can also rewrite $y_{k},$ defined in (13), as follows

In the view of the doubly stochasticity of the weights, we have $\sum_{i=1}^{m}a_{i,j}(k+1)=1$, implying that

Substituting for $y_{k+1}$ from (16) and for $w_{j,k+1}$ from (15), we obtain

We next estimate the norms of the vectors $\|p_{i,k}\|$ for any $k$. From the definition of $p_{i,k+1}$ in (14) and the definition of the vector $v_{i,k}$ in (5), we have $p_{i,k+1}=w_{i,k+1}-v_{i,k}$. Note that, being a convex combination of vectors $w_{j,k}$ in the convex set $X$, the vector $v_{i,k}$ is in the set $X$. By the definition of the iterate $w_{i,k+1}$ in (4) and the non-expansive property of the Euclidean projection in (10), we have

In the last step we have used the subgradient boundedness. By substituting the preceding relation in (18), we obtain the desired relation. ∎

2 Iterate Relation

Here, we derive a relation for the distances $\|v_{i,k+1}-~{}z\|$ and the function value differences $f(y_{k})-f(z)$ for an arbitrary $z\in X.$ This relation together with Lemma 5 provides the basis for our subsequent convergence analysis. In what follows, recall that $f=\sum_{i=1}^{m}f_{i}$.

Let Assumptions 1, 2, and 3 hold. Assume that the subgradients of $f_{i}$ are uniformly bounded over the set $X$, i.e., there are scalars $C_{i}$ such that

Using the Euclidean projection property in (10), from the definition of the iterate $w_{i,k+1}$ in (4), we have for any $z\in X$ and all $k$,

By using the subgradient inequality in (3) to bound the second term, we obtain

Note that by the convexity of the squared norm [cf. Eq. (9)], we have

In view of Assumption 3, we have $\sum_{i=1}^{m}a_{i,j}(k+2)=1$ for all $j$ and $k$, implying that

By summing the relations in (20) over all $i\in V$ and by using the preceding relation, we obtain

Recall that $v_{i,k}=\sum_{j=1}^{m}a_{i,j}(k+1)w_{j,k}$ [cf. (6)]. Substituting for $v_{i,k}$ and using the convexity of the norm [cf. (8)], from (24) we obtain

By using the preceding estimate in relation (22), we have

The result follows by using the subgradient norm boundedness, $\|\nabla f_{i}(v_{i,k})\|\leq C_{i}$ for all $k$ and $i$. ∎

Convergence in mean

Here, we study the behavior of the iterates generated by the algorithm, under the assumption that the errors have bounded norms in mean square. In particular, we assume the following.

The subgradient errors are uniformly bounded in mean square, i.e, there are scalars $\bar{\nu}_{i}$ such that

Using this assumption, we provide a bound on the expected disagreement $\mathsf{E}\!\left[\|w_{i,k}-y_{k}\|\right]$ for nondiminishing stepsize. We later use this bound to provide an estimate for the algorithm’s performance in mean. The bound is provided in the following theorem.

Let Assumptions 1a, 2, 3 and 4 hold. Also, let the subgradients of each $f_{i}$ be uniformly bounded over $X$, i.e., for each $i\in V$ there is $C_{i}$ such that

If the stepsize $\{\alpha_{k}\}$ is such that $\lim_{k\to\infty}\alpha_{k}=\alpha$ for some $\alpha\geq 0,$ then for all $j\in V$,

The conditions of Lemma 5 are satisfied. Taking the expectation in the relation of Lemma 5 and using the inequality $\mathsf{E}\!\left[\|\epsilon_{i,k}\|\right]\leq\sqrt{\mathsf{E}\!\left[\|\epsilon_{i,k}\|^{2}\right]}=\bar{\nu}_{i},$ we obtain for all $j\in V$ and all $k,$

When the stepsize is diminishing (i.e., $\alpha=0$), the result of Theorem 7 implies that the expected disagreements $\mathsf{E}\!\left[\|y_{k+1}-w_{j,k+1}\|\right]$ converge to 0 for all $j$. Thus, there is an asymptotic consensus in mean. We formally state this as a corollary.

Let the conditions of Theorem 7 hold with $\alpha=0.$ Then $\lim_{k\to\infty}\mathsf{E}\!\left[\|w_{j,k}-y_{k}\|\right]=0$ for all $j\in V.$

We next obtain bounds on the performance of the algorithm. We make the additional assumption that the set $X$ is bounded. Thus, the subgradients of each $f_{i}$ are also bounded (see , Proposition 4.2.3).

Note that, under Assumption 4, by Jensen’s inequality we have $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|\leq\bar{\nu}_{i}.$ Therefore, under Assumption 4,

We have used this relation in our analysis of the agent disagreements in Theorem 7. Using this relation, we obtain special results for the cases when the errors are zero mean or when their mean is diminishing, i.e., the cases $\mathsf{E}\!\left[\epsilon_{i,k+1}\right]=0$ for all $i,k,$ or $\mathop{\rm limsup}_{k\to\infty}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|=0$ for all $i$.

Let Assumptions 1, 2, 3 and 4 hold. Assume that the set $X$ is bounded. Let $\lim_{k\to\infty}\alpha_{k}=\alpha$ with $\alpha\geq 0.$ If $\alpha=0,$ also assume that $\sum_{k}\alpha_{k}=\infty.$ Then, for all $j\in V$,

where $\bar{\mu}_{i}=\mathop{\rm limsup}_{k\to\infty}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|$ and $C_{i}$ is an upper-bound on the subgradient norms of $f_{i}$ over the set $X.$

Under Assumption 4, the limit superiors $\bar{\mu}_{i}=\mathop{\rm limsup}_{k\to\infty}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|$ are finite [cf. Eq. (26)]. Since the set $X$ is bounded the subgradients of $f_{i}$ over the set $X$ are also bounded for each $i\in V$; hence, the bounds $C_{i},\ i\in V$ on subgradient norms exist. Thus, the conditions of Lemma 6 are satisfied. Further, by Assumption 1, the set $X$ is contained in the interior of the domain of $f$, over which the function is continuous (by convexity; see ). Thus, the set $X$ is compact and $f$ is continuous over $X$, implying that the optimal set $X^{*}$ is nonempty. Let $x^{*}\in X^{*},$ and let $y=x^{*}$ in Lemma 6. We have, for all $k$,

Since $X$ is bounded, by using $\|v_{i,k}-x^{*}\|\leq\max_{x,y\in X}\|x-y\|,$ taking the expectation and using the error bounds $\mathsf{E}\!\left[\|\epsilon_{i,k+1}\|^{2}\right]\leq\bar{\nu}_{i}^{2}$ we obtain

By rearranging the terms and summing over $k=1,\ldots,K,$ for an arbitrary $K$, we obtain

Note that when $\alpha_{k+1}\to\alpha$ and $\alpha>0,$ we have $\sum_{k}\alpha_{k}=\infty.$ When $\alpha=0,$ we have assumed that $\sum_{k}\alpha_{k}=\infty.$ Therefore, by letting $K\to\infty$, we have

Using $\mathop{\rm limsup}_{k\to\infty}\left\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\right\|=\bar{\mu}_{i}$ [see Eq. (26)] and $\lim_{k\to\infty}\alpha_{k}=\alpha,$ we obtain

Next from the convexity inequality in (3) and the boundedness of the subgradients it follows that for all $k$ and $j\in V$,

By using the preceding relation, we see that

The network topology influences the error only through the term $\frac{\theta\beta}{1-\beta}$ and can hence be used as a figure of merit for comparing different topologies. For a network that is strongly connected at every time, [i.e., $Q=1$ in Assumption 2] and when $\eta$ in Assumption 3 does not depend on the number $m$ of agents, the term $\frac{\theta\beta}{1-\beta}$ is of the order $m^{2}$ and the error bound scales as $m^{4}.$

We next show that stronger bounds can be obtained for a specific weighted time averages of the iterates $w_{i,k}$. In particular, we investigate the limiting behavior of $\{f(z_{i,t})\},$ where ${z_{i,t}=}\frac{\sum_{k=1}^{t}\alpha_{k+1}w_{i,k}}{\sum_{k=1}^{t}\alpha_{k+1}}.$ Note that agent $i$ can locally and recursively evaluate $z_{i,t+1}$ from $z_{i,t}$ and $w_{i,t+1}.$

Consider the weighted time averages ${z_{j,t}=}\frac{\sum_{k=1}^{t}\alpha_{k+1}w_{j,k}}{\sum_{k=1}^{t}\alpha_{k+1}}$ for $j\in V$ and $t\geq 1.$ Let the conditions of Theorem 9 hold. Then, we have for all $j\in V,$

The relation in (29) of Theorem 9 is valid, and we have for any $x^{*}\in X^{*},$

From the subgradient boundedness and the subgradient inequality in (3) we have for any $j$,

By re-arranging these terms, summing over $k=1,\ldots,t$ and dividing with $2\sum_{k=1}^{t}\alpha_{k+1}$, we further obtain

From the preceding two relations we obtain

First note that in the limit as $t\to\infty,$ the second term in (30) converges to since $\sum_{k=1}^{t}\alpha_{k+1}=\infty.$ By using the results of Lemma 1c, for the remaining terms, we obtain

which when substituted in the preceding relation, yields

The error bounds in Theorems 9 and 10 have the same form, but they apply to different sequences of function evaluations. Furthermore, in Theorem 10, the bound is for all subsequences of $\mathsf{E}\!\left[f(z_{i,k})\right]$ for each agent $i$. In contrast, in Theorem 9, the bound is only for a subsequence of $\mathsf{E}\!\left[f(z_{i,k})\right]$ for each agent $i$. Theorem 10 demonstrates that, due to the convexity of the objective function $f$, there is an advantage when agents are using the running averages of their iterates.

When the error When the moments $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|$ are zero, it can be seen that the results of Theorems 9 and 10 hold when the boundedness of $X$ is replaced by the weaker assumption that the subgradients of each $f_{i}$ are bounded over $X.$ moments $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|$ converge to zero as $k\to\infty$, and the stepsize converges to zero [$\alpha=0$], Theorems 9 and 10 yield respectively

When a constant stepsize $\alpha$ is used, the vector $z_{j,t}$ is simply the running average of all the iterates of agent $j$ until time $t,$ i.e., $z_{j,t}=\frac{1}{t}\sum_{k=1}^{t}w_{j,k}.$ For this case, with zero mean errors, the relation in (30) reduces to

This can be used to derive an estimate per iteration, as seen in the following.

Under the conditions of Theorem 9 with $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\right]\|=0$ and $\alpha_{k}=0$ for all $i$ and $k$, for the average sequences $\{z_{j,k}\}$ we have for all $t$ and $j$,

Taking the expectation in the relation of Lemma 5, we obtain

Combining the preceding relation with the inequality in (31), and using $\sum_{k=1}^{t}\beta^{k+1}\leq\frac{\beta^{2}}{1-\beta}$, we obtain

The preceding equation provides a bound on the algorithm’s performance at each iteration. The bound can be used in obtaining stopping rules for the algorithm. For example, consider the error free case ($\bar{\nu}_{i}=0$) and suppose that the goal is to determine the number of iterations required for agents to find a point in the $\epsilon$-optimal set, i.e., in the set $X_{\epsilon}=\{x\in X:f(x)\leq f^{*}+\epsilon\}.$ Minimizing the bound in Corollary 11 over different stepsize values $\alpha$, we can show that $\epsilon$-optimality can be achieved in $N_{\epsilon}=\left\lceil\frac{1}{\psi^{2}_{\epsilon}}\right\rceil$ iterations with a stepsize $\alpha_{\epsilon}=\frac{\sqrt{A}\psi_{\epsilon}}{\sqrt{C}}$, where $\psi_{\epsilon}$ is the positive root of the quadratic equation

Since $\psi_{\epsilon}$ scales as $\sqrt{\epsilon},$ we can conclude that $N_{\epsilon}$ scales as $\frac{1}{\epsilon^{2}}.$ Equivalently, we can say that the level $\epsilon$ of sub-optimality diminishes inversely with the square root of the number of iterations.

Almost sure and mean square convergence

There are scalars $\nu_{i}$ such that $\mathsf{E}\!\left[\|\epsilon_{i,k+1}\|^{2}\mid F_{k}\right]\leq\nu_{i}^{2}$ for all $k$ with probability 1.

Note that Assumption 5 is stronger than Assumption 4. Furthermore, when the errors are independent across iterations and across agents, Assumption 5 reduces to Assumption 4.

We start by analyzing the agents’ disagreements measured in terms of distances $\|y_{k}-w_{j,k}\|$. We have the following result.

Let Assumptions 1a, 2, 3 and 5 hold. Suppose that the subgradients of each $f_{i}$ are uniformly bounded over $X$, i.e., for each $i\in V$ there is $C_{i}$ such that

If $\sum_{k=0}^{\infty}\alpha_{k+1}^{2}<\infty,$ then with probability 1,

Furthermore, for all $j\in V$, we have $\lim_{k\to\infty}\|y_{k+1}-w_{j,k+1}\|=0$ with probability 1 and in mean square.

By Lemma 5 and the subgradient boundedness, we have for all $j\in V$,

Since $\sum_{k}\alpha^{2}_{k}<\infty$ (and hence $\{\alpha_{k}\}$ bounded), the first two terms and the last two terms are summable. Furthermore, in view of Lemma 1 [part (b)], we have

Thus, the third term is also summable. Hence $\sum_{k=1}^{\infty}\mathsf{E}\!\left[\alpha_{k+2}\|y_{k+1}-w_{j,k+1}\|\right]<\infty.$ From the monotone convergence theorem , it follows that

and it is hence finite for all $j$. If the expected value of a random variable is finite, then the variable has to be finite with probability 1; thus, with probability 1,

We now show that $\lim_{k\to\infty}\|y_{k}-w_{j,k}\|=0$ with probability 1 for all $j\in V.$ Note that the conditions of Theorem 7 are satisfied with $\bar{\nu}_{i}=\nu_{i}$ and $\alpha=0.$ Therefore, $\|y_{k}-w_{j,k}\|$ converges to in the mean and from (Fatou’s) Lemma 3 it follows that

and hence $\mathsf{E}\!\left[\mathop{\rm liminf}_{k\to\infty}\left\|y_{k}-w_{j,k}\right\|\right]=0.$ Therefore, with probability 1,

To complete the proof, in view of (33) it suffices to show that $\left\|y_{k}-w_{j,k}\right\|$ converges with probability 1. To show this, we define

and note that $P_{X}[r_{i,k+1}]=w_{i,k+1}$ [see (4) and (5)]. Since $y_{k}=\frac{1}{m}\sum_{i=1}^{m}w_{i,k}$ and the set $X$ is convex, it follows that $y_{k}\in X$ for all $k$. Therefore, by the non-expansive property of the Euclidean projection in (10), we have $\|w_{i,k+1}-y_{k}\|^{2}\leq\|r_{i,k+1}-y_{k}\|^{2}$ for all $i\in V$ and all $k$. Summing these relations over all $i,$ we obtain

From $y_{k+1}=\frac{1}{m}\sum_{i=1}^{m}w_{i,k+1}$ and the fact that the average of vectors minimizes the sum of distances between each vector and arbitrary vector in $\Re^{n}$ [cf. Eq (7)], we further obtain

We next relate $\sum_{i=1}^{m}\|r_{i,k+1}-y_{k}\|^{2}$ to $\sum_{i=1}^{m}\|w_{i,k}-y_{k}\|^{2}.$ From the definition of $r_{i,k+1}$ and the equality $\sum_{j=1}^{m}a_{i,j}(k+1)=1$ [cf. Assumption 3b], we have

By Assumption 3a and 3b, we have that the weights $a_{i,j}(k+1),j\in V$ yield a convex combination. Thus, by the convexity of the norm [(8) and (9)] and by the subgradient boundedness, we have

Summing over all $i$ and using $\sum_{i=1}^{m}a_{i,j}(k+1)=1$ [cf. Assumption 3d], we obtain

Using this in (34) and taking the conditional expectation, we see that for all $k$, we have with probability 1,

where we use $a_{i,j}(k+1)\leq 1$ for all $i,j$ and $k$, and the relations $\mathsf{E}\!\left[\|\epsilon_{i,k+1}\|^{2}\mid F_{k}\right]\leq\nu_{i}^{2},$ $\mathsf{E}\!\left[\|\epsilon_{i,k+1}\|\mid F_{k}\right]\leq\nu_{i}$ holding with probability 1.

We now apply Theorem 4 to the relation in (36). To verify that the conditions of Theorem 4 are satisfied, note that the stepsize satisfies $\sum_{k=1}^{\infty}\alpha^{2}_{k+1}<\infty$ for all $i\in V.$ We also have $\sum_{k=1}^{\infty}\alpha_{k+1}\left\|w_{j,k}-y_{k}\right\|<\infty$ with probability 1 [cf. (32)]. Therefore, the relation in (36) satisfies the conditions of Theorem 4 with $\zeta_{k}=D_{k}=0,$ thus implying that $\left\|w_{j,k}-y_{k}\right\|$ converges with probability 1 for every $j\in V.$ ∎

Let us compare Theorem 12 and Corollary 8. Corollary 8 provided sufficient conditions for the different agents to have consensus in the mean. Theorem 12 strengthens this to consensus with probability 1 and in mean square sense, for a smaller class of stepsize sequences under a stricter assumption.

We next show that the consensus vector is actually in the optimal set, provided that the optimal set is nonempty and the conditional expectations $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|$ are diminishing.

Let Assumptions 1, 2, 3 and 5 hold. Suppose that the subgradients of each $f_{i}$ are uniformly bounded over $X$, i.e., for each $i\in V$ there is $C_{i}$ such that

Also, assume that $\sum_{k=0}^{\infty}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|^{2}<\infty$ for all $i\in V.$ Further, let the stepsize sequence $\{\alpha_{k}\}$ be such that $\sum_{k=1}^{\infty}\alpha_{k}=\infty$ and $\sum_{k=1}^{\infty}\alpha_{k}^{2}<\infty.$ Then, if the optimal set $X^{*}$ is nonempty, the iterate sequence $\{w_{i,k}\}$ of each agent $i\in V$ converges to the same optimal point with probability 1 and in mean square.

Observe that the conditions of Lemma 6 are satisfied. Letting $z=x^{*}$ for some $x^{*}\in X^{*}$, taking conditional expectations and using the bounds on the error moments, we obtain for any $x^{*}\in X^{*}$ and any $k$, with probability 1,

where $f^{*}=f(x^{*}),$ and we use the notation $\mu_{i,k+1}=\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|.$ Using the inequality

By Theorem 12, we have with probability 1,

Further, since $\sum_{k}\mu^{2}_{i,k}<\infty$ and $\sum_{k}\alpha_{k}^{2}<\infty$ with probability 1, the relation in (37) satisfies the conditions of Theorem 4. We therefore have

and $\|v_{i,k}-x^{*}\|$ converges with probability 1 and in mean square. In addition, by Theorem 12, we have $\lim_{k\to\infty}\|w_{i,k}-y_{k}\|=0$ for all $i$, with probability 1. Hence, $\lim_{k\to\infty}\|v_{i,k}-y_{k}\|\to 0$ for all $i$, with probability 1. Therefore, $\|y_{k}-x^{*}\|$ converges with probability 1 for any $x^{*}\in X^{*}.$ Moreover, from (38) and the fact that $\sum_{k}\alpha_{k}=\infty,$ by continuity of $f$, it follows that $y_{k},$ and hence $w_{i,k},$ must converge to a vector in $X^{*}$ with probability 1 and in mean square. ∎

Note that the result of Theorem 13 holds without assuming compactness of the constraint set $X$. This was possible due to the assumption that both the stepsize $\alpha_{k}$ and the norms $\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|$ of the conditional errors are square summable. In addition, note that the result of Theorem 13 remains valid when the condition $\sum_{k=0}^{\infty}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|^{2}<\infty$ for all $i$ is replaced with $\sum_{k=0}^{\infty}\alpha_{k+1}\|\mathsf{E}\!\left[\epsilon_{i,k+1}\mid F_{k}\right]\|<\infty$ for all $i$.

Implications

The primary source of stochastic errors in the subgradient evaluation is when the objective function is not completely known and has some randomness in it. Such settings arise in sensor network applications that involve distributed and recursive estimation .

Let the function $f_{i}(x)$ be given by $f_{i}(x)=\mathsf{E}\!\left[g_{i}(x,R_{i})\right],$ where $R_{i}$ is a random variable whose statistics are independent of $x.$ The statistics of $R_{i}$ are not available to agent $i$ and hence the function $f_{i}$ is not known to agent $i.$ Instead, agent $i$ observes samples of $R_{i}$ in time. Thus, in a subgradient algorithm for minimizing the function, the subgradient must be suitably approximated using the observed samples. In the Robbins-Monro stochastic approximation , the subgradient $\nabla f_{i}(x)$ is approximated by $\nabla g_{i}(x,r_{i}),$ where $r_{i}$ denotes a sample of $R_{i}.$ The associated distributed Robbins-Monro stochastic optimization algorithm is

where $r_{i,k+1}$ is a sample of $R_{i}$ obtained at time $k.$ The expression for the error is

If the samples obtained across iterations are independent then

If in addition, $\mathsf{Var}\!\left[\nabla g_{i}(x,R_{i})\right]$ is bounded for all $x\in X$ then the conditions of Theorems 9, 10 and 13 are satisfied.

Let us next consider the case when $f_{i}(x)=\mathsf{E}\!\left[g_{i}(x,R_{i}(x))\right],$ where $R_{i}(x)$ is a random variable that is parameterized by $x.$ To keep the discussion simple, let us assume that $x\in\Re.$ As in the preceding case, the statistics of $R_{i}(x)$ are not known to agent $i,$ but the agent can obtain samples of $R_{i}(x)$ for any value of $x.$ In the Kiefer-Wolfowitz approximation ,

where $r_{i}(x)$ is a sample of the random variable $R_{i}(x).$ The corresponding distributed optimization algorithm is

where $\beta_{i,k+1}$ is a positive scalar. In this case, the error is

If the function $g_{i}$ is differentiable then $\mathsf{E}\!\left[\epsilon_{i,k+1}\mid v_{i,k}\right]$ is of the order $\beta_{i,k+1}.$ Thus, the conditions on the mean value of the errors can be controlled through the sequence $\{\beta_{i,k}\}$ and the conditions in Theorems 9, 10 and 13 can be met by suitably choosing the sequence $\{\beta_{i,k}\}$.

Discussion

We studied the effects of stochastic subgradient errors on distributed algorithm for network of agents with time-varying connectivity. We first considered very general errors with bounded second moments and obtained explicit bounds on the agent disagreements and on the expected deviation of the limiting function value from the optimal. The bounds are explicitly given as a function of the network properties, objective function and the error moments. For networks that are connected at all times and $\eta$ is independent of the size of the network, the bound scales as $\alpha\left(\max_{i\in V}\{C_{i}+\nu_{i}\}\right)^{2}m^{4},$ where $m$ is the number of agents in the network, $\alpha$ is the stepsize limit, and $C_{i}$ and $\nu_{i}^{2}$ are respectively the subgradient norm bound and the bound on the second moment of the subgradient errors for agent $i$. For the constant stepsize case, we obtained a bound on the performance of the algorithm after a finite number of iterations. There, we showed that deviation from the “error-bound” diminishes at rate $\frac{1}{t},$ where $t$ is the number of iterations. Finally, we proved that when the expected error and the stepsize converge to sufficiently fast, the agents reach a consensus and the iterate sequences of agents converge to a common optimal point with probability 1 and in mean square.

We make the following remarks. First, it can be shown that the disagreement results in Corollary 8 and Theorem 12 hold even when the agents use non-identical stepsizes. However, with non-identical agent stepsizes there is no guarantee that the sum of the objectives rather than a weighted sum, is minimized.

Future work includes several important extensions of the distributed model studied here. At first, we have assumed no communication delays between the agents and synchronous processing. An important extension is to consider the properties of the algorithm in asynchronous networks with communication delays, as in . At second, we assumed perfect communication scenario, i.e., noiseless communication links. In wireless network applications, the links are typically noisy and this has to be taken into consideration. At third, we have considered the class of convex functions. This restricts the number of possible applications for the algorithm. Further research is to develop distributed algorithms when the functions $f_{i}$ are not convex.

References