{'fraction_non_alphanumeric': 0.05217366499315381, 'fraction_numerical': 0.017029895025102694, 'mean_word_length': 3.870380661294804, 'pattern_counts': {'":': 0, '<': 13, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Distributed Stochastic Subgradient Projection Algorithms for Convex Optimization

We consider a distributed multi-agent network system where the goal is to minimize a sum of convex objective functions of the agents subject to a common convex constraint set. Each agent maintains an iterate sequence and communicates the iterates to its neighbors. Then, each agent combines weighted averages of 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 goal of this paper is to explore the effects of stochastic subgradient errors on the convergence of the algorithm. We first consider the behavior of the algorithm in mean, and then the convergence with probability 1 and in mean square. 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.


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 [23,25,26]. 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 [23]. In a network of databases from which information is to be mined, privacy considerations may not allow the sharing of the objective functions [34]. 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 [32].
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 [19] 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 [30]. 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 [5,12,16,23,25]. The effects of stochastic errors on these algorithms have been investigated in [3,9,14,17,23,25,28]. 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 [2,31]. 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 [2,11,13,15,18,20,21,[29][30][31]33]. 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 [10,13,15,33]. In addition, since we are interested in the effect of stochastic errors, our paper is also related to the literature on stochastic subgradient methods [6][7][8].
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 [19]. 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 [20], 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.
2. 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.

Problem.
We consider a network of m agents that are indexed by 1, . . . , m. Often, when convenient, we index the agents by using set V = {1, . . . , m}. The network objective is to solve the following constrained optimization problem: where X ⊆ ℜ n is a constraint set and f i : X → ℜ for all i. Related to the problem we use the following notation We are interested in the case when the problem in (2.1) is convex. Specifically, we assume that the following assumption holds. Assumption 1. The functions f i and the set X are such that (a) The set X is closed and convex. (b) The functions f i , i ∈ 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.1) using an algorithm that is distributed and local. 1 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 ∇f i is a subgradient of f i at a point x ∈ 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 [1] or [27]).

Algorithm.
To solve the problem in (2.1) 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 ∈ X. Here, ∇f i (v i,k ) denotes the subgradient of f i at v i,k and ǫ i,k+1 is the stochastic error in the subgradient evaluation. The scalar α 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 ∈ 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 0 for j / ∈ N i (k + 1) and rewrite (2.4) 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 (2.3) is just a subgradient iteration for minimizing f i over X taken after the "consensus"-based step.

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 Assumption 2. There exists a scalar Q such that the graph (V, ∪ l=1,...,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. Assumption 3. For i ∈ V and all k, (a) a i,j (k + 1) ≥ 0, and a i,j (k + 1) = 0 when j / ∈ 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. 2 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 m i=1 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 [19,25].

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

Euclidean norm inequalities. For any vectors
for any x ∈ ℜ n . (3.1) 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 ℜ 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 , . . . , v M ∈ ℜ n and nonnegative scalars β 1 , . . . , β M such that The following inequality is the well-known 3 non-expansive property of the Euclidean projection onto a nonempty, closed and convex set X, 3.2. Scalar sequences. For a scalar β and a scalar sequence {γ k }, we consider the "convolution" sequence k ℓ=0 β k−ℓ γ ℓ = β k γ 0 + β k−1 γ 1 + · · · + βγ k−1 + γ k . We have the following result.
Proof. (a) Let ǫ > 0 be arbitrary. Since γ k → γ and for all k, there is an index K such that |γ k − γ| ≤ ǫ for all k ≥ K. For all k ≥ K + 1, we have it follows that for all k ≥ K + 1, Therefore, Since ǫ is arbitrary, we conclude that limsup k→∞ Since ǫ is arbitrary, we have liminf k→∞ k ℓ=0 β k−ℓ γ ℓ ≥ γ 1−β . This and the relation limsup k→∞ By letting M → ∞ and using k ζ k = ∞, we see that limsup M→∞ P M k=0 γ k ζ k P M k=0 ζ k ≤ γ +ǫ, and since ǫ is arbitrary, the result for the limit superior follows.
Analogously, if liminf k→∞ γ k = γ, then for every ǫ > 0 there is a large enough K such that γ k ≥ γ − ǫ for all k ≥ K. Thus, for any M > K, Letting M → ∞ and using k ζ k = ∞, we obtain liminf M→∞ Since ǫ > 0 is arbitrary, we have liminf M→∞ This relation and the relation for the limit superior yield lim M→∞ 3.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 stochastic 4 . Define, for all k, s with k ≥ s, We next state a result from [18] (Corollary 1) on the convergence properties of the matrix Φ(k, s). Let [Φ(k, s)] i,j denote the (i, j)-th entry of the matrix Φ(k, s), and let e ∈ ℜ m be the column vector with all entries equal to 1. Lemma 3.2. Let Assumptions 2 and 3 hold. Then Further, the convergence is geometric and the rate of convergence is given by 3.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 [4].
and {H k } be non-negative random sequences and let {ζ k } be a deterministic nonnegative scalar sequence. Let G k be the σ−algebra generated by

6)
and k H k < ∞ with probability 1. Then, the sequence {B k } converges to a nonnegative random variable and k D k < ∞ 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.
4.1. Disagreement Estimate. 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 (2.3)-(2.4). 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 3.2 plays a crucial role in obtaining this estimate. Lemma 4.1. 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 Then, for all j ∈ V and k ≥ 0, Proof. Define for all i ∈ V and all k, Using the matrices Φ(k, s) defined in (3.5) we can write Using (4.2), we can also rewrite y k , defined in (4.1), as follows In the view of the doubly stochasticity of the weights, we have m i=1 a i,j (k + 1) = 1, implying that Therefore Substituting for y k+1 from (4.4) and for w j,k+1 from (4.3), we obtain Therefore, for all j ∈ V and all k, We can bound w i,0 ≤ max i∈V w i,0 . Further, we can use the rate of convergence result from Lemma 3.
We next estimate the norms of the vectors p i,k for any k. From the definition of p i,k+1 in (4.2) and the definition of the vector 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 (2.3) and the non-expansive property of the Euclidean projection in (3.4), we have In the last step we have used the subgradient boundedness. By substituting the preceding relation in (4.5), we obtain the desired relation.

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 ∈ X. This relation together with Lemma 4.1 provides the basis for our subsequent convergence analysis. In what follows, recall that f = m i=1 f i . Lemma 4.2. 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 Then, for any z ∈ X and all k, Proof. Using the Euclidean projection property in (3.4), from the definition of the iterate w i,k+1 in (2.3), we have for any z ∈ X and all k, By using the subgradient inequality in (2.2) to bound the second term, we obtain Note that by the convexity of the squared norm [cf. Eq. (3. 3)], we have In view of Assumption 3, we have m i=1 a i,j (k + 2) = 1 for all j and k, implying that By summing the relations in (4.6) over all i ∈ V and by using the preceding relation, we obtain . Substituting for v i,k and using the convexity of the norm [cf. (3.2)], from (4.8) we obtain By using the preceding estimate in relation (4.7), we have The result follows by using the subgradient norm boundedness, ∇f i (v i,k ) ≤ 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. Using this assumption, we provide a bound on the expected disagreement E[ w i,k − y k ] 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. Theorem 5.1. 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 ∈ V there is C i such that If the stepsize {α k } is such that lim k→∞ α k = α for some α ≥ 0, then for all j ∈ V , Proof. The conditions of Lemma 4.1 are satisfied. Taking the expectation in the relation of Lemma 4.1 and using the inequality E[ ǫ i,k ] ≤ E[ ǫ i,k 2 ] =ν i , we obtain for all j ∈ V and all k, Since lim k→∞ α k = α, by Lemma 3.1(a) we have lim k→∞ k ℓ=1 β k−ℓ α ℓ = α 1−β . Using this relation and lim k→∞ α k = α, we obtain the result by taking the limit superior in (5.1) as k → ∞.
When the stepsize is diminishing (i.e., α = 0), the result of Theorem 5.1 implies that the expected disagreements E[ y k+1 − w j,k+1 ] converge to 0 for all j. Thus, there is an asymptotic consensus in mean. We formally state this as a corollary.
Corollary 5.2. Let the conditions of Theorem 5.1 hold with α = 0. Then 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 [ We have used this relation in our analysis of the agent disagreements in Theorem 5.1. 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 E[ǫ i,k+1 ] = 0 for all i, k, or limsup k→∞ E[ǫ i,k+1 ] = 0 for all i. Theorem 5.3. Let Assumptions 1, 2, 3 and 4 hold. Assume that the set X is bounded. Let lim k→∞ α k = α with α ≥ 0. If α = 0, also assume that k α k = ∞. Then, for all j ∈ V , and C i is an upper-bound on the subgradient norms of f i over the set X. Proof. Under Assumption 4, the limit superiorsμ i = limsup k→∞ E[ǫ i,k+1 ] are finite [cf. Eq. (5.2)]. Since the set X is bounded the subgradients of f i over the set X are also bounded for each i ∈ V ; hence, the bounds C i , i ∈ V on subgradient norms exist. Thus, the conditions of Lemma 4.2 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 [27]). Thus, the set X is compact and f is continuous over X, implying that the optimal set X * is nonempty. Let x * ∈ X * , and let y = x * in Lemma 4.2. We have, for all k, Since X is bounded, by using v i,k − x * ≤ max x,y∈X x − y , taking the expectation and using the error bounds E ǫ i,k+1 By rearranging the terms and summing over k = 1, . . . , K, for an arbitrary K, we obtain Note that when α k+1 → α and α > 0, we have k α k = ∞. When α = 0, we have assumed that k α k = ∞. Therefore, by letting K → ∞, we have 2)] and lim k→∞ α k = α, we obtain Next from the convexity inequality in (2.2) and the boundedness of the subgradients it follows that for all k and j ∈ V , By using the preceding relation, we see that The network topology influences the error only through the term θβ 1−β 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 η in Assumption 3 does not depend on the number m of agents, the term θβ 1−β 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 Note that agent i can locally and recursively evaluate z i,t+1 from z i,t and w i,t+1 .
Theorem 5.4. Consider the weighted time averages z j,t = P t k=1 α k+1 w j,k P t k=1 α k+1 for j ∈ V and t ≥ 1. Let the conditions of Theorem 5.3 hold. Then, we have for all j ∈ V,

Proof. The relation in (5.3) of Theorem 5.3 is valid, and we have for any
From the subgradient boundedness and the subgradient inequality in (2.2) we have for any j, Therefore, we obtain By re-arranging these terms, summing over k = 1, . . . , t and dividing with 2 t k=1 α k+1 , we further obtain Next by the convexity of f note that From the preceding two relations we obtain First note that in the limit as t → ∞, the second term in (5.4) converges to 0 since t k=1 α k+1 = ∞. By using the results of Lemma 3.1c, for the remaining terms, we obtain By Theorem 5.1, we have for all j ∈ V , which when substituted in the preceding relation, yields The error bounds in Theorems 5.3 and 5.4 have the same form, but they apply to different sequences of function evaluations. Furthermore, in Theorem 5.4, the bound is for all subsequences of E[f (z i,k )] for each agent i. In contrast, in Theorem 5.3, the bound is only for a subsequence of E[f (z i,k )] for each agent i. Theorem 5.4 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 5 moments E[ǫ i,k+1 ] converge to zero as k → ∞, and the stepsize converges to zero [α = 0], Theorems 5.3 and 5.4 yield respectively When a constant stepsize α 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 = 1 zero mean errors, the relation in (5.4) reduces to This can be used to derive an estimate per iteration, as seen in the following.
Proof. Taking the expectation in the relation of Lemma 4.1, we obtain Combining the preceding relation with the inequality in (5.5), and using 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 (ν i = 0) and suppose that the goal is to determine the number of iterations required for agents to find a point in the ǫ-optimal set, i.e., in the set X ǫ = {x ∈ X : f (x) ≤ f * + ǫ}. Minimizing the bound in Corollary 5.5 over different stepsize values α, we can show that ǫ-optimality can be achieved in where ψ ǫ is the positive root of the quadratic equation and A, B and C are Since ψ ǫ scales as √ ǫ, we can conclude that N ǫ scales as 1 ǫ 2 . Equivalently, we can say that the level ǫ of sub-optimality diminishes inversely with the square root of the number of iterations.
6. Almost sure and mean square convergence. In this section, we impose some additional assumptions on the subgradient errors to obtain almost sure consensus among the agents and almost sure convergence of the iterates to an optimal solution of (2.1). Towards this, define F k to be the σ-algebra σ (ǫ i,ℓ ; i ∈ V, 0 ≤ ℓ ≤ k) generated by the errors in the agent system up to time k. In other words, F k captures the history of the errors until the end of time k. We use the following assumption on the subgradient errors ǫ i,k .
Assumption 5. There are scalars ν i such that E ǫ i,k+1 2 | F k ≤ ν 2 i 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.
Theorem 6.1. 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 ∈ V there is C i such that If ∞ k=0 α 2 k+1 < ∞, then with probability 1, Furthermore, for all j ∈ V , we have lim k→∞ y k+1 − w j,k+1 = 0 with probability 1 and in mean square. Proof. By Lemma 4.1 and the subgradient boundedness, we have for all j ∈ V , Using the inequalities By using the inequalities k ℓ=1 β k+1−ℓ ≤ β 1−β for all k ≥ 1 and 1 2m + 1 2 ≤ 1, and by grouping the terms accordingly, from the preceding relation we have Taking the conditional expectation and using E ǫ i,ℓ 2 | F ℓ−1 ≤ ν 2 i , and then taking the expectation again, we obtain Since k α 2 k < ∞ (and hence {α k } bounded), the first two terms and the last two terms are summable. Furthermore, in view of Lemma 3.
Thus, the third term is also summable. Hence ∞ k=1 E[α k+2 y k+1 − w j,k+1 ] < ∞. From the monotone convergence theorem [4], 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, ∞ k=1 α k+2 y k+1 − w j,k+1 < ∞ for all j ∈ V. (6.1) We now show that lim k→∞ y k − w j,k = 0 with probability 1 for all j ∈ V. Note that the conditions of Theorem 5.1 are satisfied withν i = ν i and α = 0. Therefore, y k − w j,k converges to 0 in the mean and from (Fatou's) Lemma 3.3 it follows that and hence E[liminf k→∞ y k − w j,k ] = 0. Therefore, with probability 1, To complete the proof, in view of (6.2) it suffices to show that y k − w j,k converges with probability 1. To show this, we define and note that P X [r i,k+1 ] = w i,k+1 [see (2.3) and (2.4)]. Since y k = 1 m m i=1 w i,k and the set X is convex, it follows that y k ∈ X for all k. Therefore, by the non-expansive property of the Euclidean projection in (3.4), we have w i,k+1 − y k 2 ≤ r i,k+1 − y k 2 for all i ∈ V and all k. Summing these relations over all i, we obtain for all k.
Therefore, for all k, From the definition of r i,k+1 and the equality m j=1 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 ∈ V yield a convex combination. Thus, by the convexity of the norm [(3.2) and (3.3)] and by the subgradient boundedness, we have Summing over all i and using Using this in (6.3) and taking the conditional expectation, we see that for all k, we have with probability 1, where we use a i,j (k + 1) ≤ 1 for all i, j and k, and the relations E ǫ i,k+1 We now apply Theorem 3.4 to the relation in (6.4). To verify that the conditions of Theorem 3.4 are satisfied, note that the stepsize satisfies ∞ k=1 α 2 k+1 < ∞ for all i ∈ V. We also have ∞ k=1 α k+1 w j,k − y k < ∞ with probability 1 [cf. (6.1)]. Therefore, the relation in (6.4) satisfies the conditions of Theorem 3.4 with ζ k = D k = 0, thus implying that w j,k − y k converges with probability 1 for every j ∈ V.
Let us compare Theorem 6.1 and Corollary 5.2. Corollary 5.2 provided sufficient conditions for the different agents to have consensus in the mean. Theorem 6.1 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 E[ǫ i,k+1 | F k ] are diminishing.
Theorem 6.2. 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 ∈ V there is C i such that Also, assume that ∞ k=0 E[ǫ i,k+1 | F k ] 2 < ∞ for all i ∈ V. Further, let the stepsize sequence {α k } be such that ∞ k=1 α k = ∞ and ∞ k=1 α 2 k < ∞. Then, if the optimal set X * is nonempty, the iterate sequence {w i,k } of each agent i ∈ V converges to the same optimal point with probability 1 and in mean square. Proof. Observe that the conditions of Lemma 4.2 are satisfied. Letting z = x * for some x * ∈ X * , taking conditional expectations and using the bounds on the error moments, we obtain for any x * ∈ X * and any k, with probability 1, where f * = f (x * ), and we use the notation (6.5) By Theorem 6.1, we have with probability 1, k α k+1 w j,k − y k < ∞.
Further, since k µ 2 i,k < ∞ and k α 2 k < ∞ with probability 1, the relation in (6.5) satisfies the conditions of Theorem 3.4. We therefore have and v i,k − x * converges with probability 1 and in mean square. In addition, by Theorem 6.1, we have lim k→∞ w i,k − y k = 0 for all i, with probability 1. Hence, lim k→∞ v i,k − y k → 0 for all i, with probability 1. Therefore, y k − x * converges with probability 1 for any x * ∈ X * . Moreover, from (6.6) and the fact that k α k = ∞, 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 6.2 holds without assuming compactness of the constraint set X. This was possible due to the assumption that both the stepsize α k and the norms E[ǫ i,k+1 | F k ] of the conditional errors are square summable. In addition, note that the result of Theorem 6.2 remains valid when the condition 7. 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 [24].
Let the function f i (x) be given by 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 [22], the subgradient ∇f i (x) is approximated by ∇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, Var[∇g i (x, R i )] is bounded for all x ∈ X then the conditions of Theorems 5.3, 5.4 and 6.2 are satisfied. Let us next consider the case when f i (x) = E[g i (x, R i (x))] , where R i (x) is a random variable that is parameterized by x. To keep the discussion simple, let us assume that x ∈ ℜ. 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 [22], where r i (x) is a sample of the random variable R i (x). The corresponding distributed optimization algorithm is where β i,k+1 is a positive scalar. In this case, the error is If the function g i is differentiable then E[ǫ i,k+1 | v i,k ] is of the order β i,k+1 . Thus, the conditions on the mean value of the errors can be controlled through the sequence {β i,k } and the conditions in Theorems 5.3, 5.4 and 6.2 can be met by suitably choosing the sequence {β i,k }.
8. 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 η is independent of the size of the network, the bound scales as α (max i∈V {C i + ν i }) 2 m 4 , where m is the number of agents in the network, α is the stepsize limit, and C i and ν 2 i 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 1 t , where t is the number of iterations. Finally, we proved that when the expected error and the stepsize converge to 0 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 5.2 and Theorem 6.1 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 [30]. 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.