Incremental Stochastic Subgradient Algorithms for Convex Optimization

Introduction

A problem of recent interest in distributed networks is the design of decentralized algorithms to minimize a sum of functions, when each component function is known only to a particular agent . Such problems arise in many network applications, including in-network estimation, learning, signal processing and resource allocation . In these applications, there is no central coordinator that has access to all the information and, thus, decentralized algorithms are needed to solve the problems. In this paper, we consider decentralized subgradient methods for constrained minimization of a sum of convex functions, when each component function is only known partially (with stochastic errors) to a specific network agent. We study two incremental subgradient methods with stochastic errors: a cyclic and a (non-cyclic) Markov randomized incremental method.

The cyclic incremental algorithm is a decentralized method in which the network agents form a ring and process the information cyclically. The incremental method was originally proposed by Kibardin and has been extensively studied more recently in . Incremental gradient algorithms were first used for optimizing the weights in neural network training , and most of the associated literature deals with differentiable non-convex unconstrained optimization problems . The incremental subgradient algorithm for non-differentiable constrained convex optimization has been investigated in without errors, and in where the effects of deterministic errors are considered. The algorithm that we consider in this paper is stochastic and as such differs from the existing literature. For this algorithm, we establish convergence for diminishing step-size and provide an error bound for constant step-size.

The Markov randomized incremental algorithm is a decentralized method where the iterates are generated incrementally within the network by passing them from agent to agent. Unlike the cyclic incremental method, where the agent network has a ring structure and the information flow is along this ring (cycle), in the Markov randomized incremental method, the network can have arbitrary structure. However, similar to cyclic incremental method, in the Markov randomized incremental method, only one agent updates at any given time. In particular, an agent in the network updates the current iterate (by processing locally its own objective function) and either, passes the new iterate to a randomly chosen neighbor, or, processes it again. Thus the order in which the agents update the iterates is random. This class of incremental algorithms was first proposed in , where the agent that receives the iterate is chosen with uniform probability in each iteration (corresponding to the case of a fully connected agent network). Recently, this idea has been extended in to the case where the sequence in which the agents process the information is a time homogeneous Markov chain. The rationale behind this model is that the agent updating the information at a given time is more likely to pass this information to a close neighbor rather than to an agent who is further away. In this paper, we consider a more general framework than that of by allowing the sequence in which the agents process the information to be a time non-homogeneous Markov chain.The primary motivation to study such a model are mobile networks where the network connectivity structure is changing in time and, thus, the set of the neighbors of an agent is time-varying. We prove the algorithm convergence for diminishing step-size and establish an error bound for a constant step-size. This extends the results in , where an error bound for a homogeneous Markov randomized incremental subgradient method is discussed for a constant step-size and error-free case.

The Markov randomized incremental algorithm is also related to the decentralized computation model in for stochastic optimization problems. However, the emphasis in these studies is on parallel processing where each agent completely knows the entire objective function to be minimized. More closely related is the work in studies in that develops a “parallel” version of the unconstrained incremental subgradient algorithm. Also related is the constrained consensus problem studied in where agents are interested in obtaining a solution to a feasibility problem, when different parts of the problem are known to different agents. At a much broader scale, the paper is also related to the literature on distributed averaging and consensus algorithms .

Our main contributions in this paper are the development and analysis of the Markov randomized incremental method with stochastic subgradients and the use of a time non-homogeneous Markov model for the sequence of computing agents. In addition, To the best of our knowledge, this is among the few attempts made at studying the effects of stochastic errors on the performance of decentralized optimization algorithms. The other studies are , but the algorithms considered are fundamentally different from the incremental algorithms studied in this paper.In that work, the components of the decision vector are distributed while the objective function is known to all agents. In contrast, in this paper, the objective function data is distributed, while each agent has an estimate of the entire decision vector.

The paper is organized as follows. In Section 2, we formulate the problem of interest, and introduce the cyclic incremental and Markov randomized incremental method with stochastic errors. We also discuss some applications that motivate our interest in these methods. In Section 3, we analyze convergence properties of the cyclic incremental method. We establish convergence of the method under diminishing step-size and provide an error bound for the method with a constant step-size, both valid with probability 1. We establish analogous results for the Markov randomized incremental method in Section 4. We give some concluding remarks in Section 5.

Problem Formulation and Motivation

We consider a network of $m$ agents, indexed by $i=1,\ldots,m$. The network objective is to solve the following problem:

where $x\in\Re^{n}$ is a decision or a parameter vector, $X$ is a closed and convex subset of $\Re^{n}$, and each $f_{i}$ is a convex function from $\Re^{n}$ to $\Re$ that is known only to agent $i.$ Problems with the above structure arise in the context of estimation in sensor networks , where $x$ is an unknown parameter to be estimated and $f_{i}$ is the cost function that is determined by the $i$-th sensor’s observations (for example, $f_{i}$ could be the log-likelihood function in maximum likelihood estimation). Furthermore, problems with such structure also arise in resource allocation in data networks. In this context, $x$ is the resource vector to be allocated among $m$ agents and $f_{i}$ is the utility function for agent $i$ . We discuss these in more detail later.

To solve the problem (1) in a network where agents are connected in a directed ring structure, we consider the cyclic incremental subgradient method . Time is slotted and in each time slot, the estimate is passed by an agent to the next agent along the ring. In particular, agent $i,$ receives the iterate from agent $i-1,$ and updates the received estimate using a subgradient of its “own objective function $f_{i}$”. The updated iterate is then communicated to the next agent in the cycle, which is agent $i+1$ when $i<m$ and agent $1$ when $i=m.$ We are interested in the case where the agent subgradient evaluations have random errors. Formally, the algorithm is given as follows:

where the initial iterate $x_{0}\in X$ is chosen at random. The vector $x_{k}$ is the estimate at the end of cycle $k,$ $z_{i,k+1}$ is the intermediate estimate obtained after agent $i$ updates in $k+1$-st cycle, $\nabla f_{i}(x)$ is the subgradient of $f_{i}$ evaluated at $x,$ and $\epsilon_{i,k+1}$ is a random error. The scalar $\alpha_{k+1}$ is a positive step-size and $\mathcal{P}_{X}$ denotes Euclidean projection onto the set $X.$ We study the convergence properties of method (2) in Section 3 for diminishing and constant step-size.

In addition, for a network of agents with arbitrary connectivity, we consider an incremental algorithm where the agent that updates is selected randomly according to a distribution depending on the agent that performed the most recent update. Formally, in this method the iterates are generated according to the following rule:

where the initial iterate $x_{0}\in X$ is chosen at random and the agent $s(0)$ that initializes the method is also selected at random. The integer $s(k+1)$ is the index of the agent that performs the update at time $k+1$, and the sequence $\{s(k)\}$ is modeled as a time non-homogeneous Markov chain with state space $\{1,\ldots,m\}$. In particular, if agent $i$ was processing at time $k$, then the agent $j$ will be selected to perform the update at time $k+1$ with probability $[P(k)]_{i,j}$. Formally, we have

When there are no errors ($\epsilon_{s(k+1),k+1}=0$) and the probabilities $[P(k)]_{i,j}$ are all equal to $\frac{1}{m}$, the method in (3) coincides with the incremental method with randomization that was proposed and studied in .

Following , we refer to the method in (3) as the Markov randomized incremental stochastic algorithm. We analyze convergence properties of this method in Section 4 for diminishing and constant step-sizes.

As mentioned, we study the convergence properties of the incremental algorithms (2) and (3) for diminishing and constant step-size, and for zero and non-zero mean errors. Such errors may arise directly as computational round-off errors, which are of interest when the entire network is on a single chip and each agent is a processor on the chip . In addition, stochastic errors also arise in the following context.

Let the function $f_{i}(x)$ have the following form

where $\mathsf{E}\!\left[\cdot\right]$ denotes the expectation, $R_{i}\in\Re^{d}$ is a random vector and $g_{i}:\Re^{n\times d}\to\Re$. Agent $i$ does not know the statistics of $R_{i},$ and thus does not know its complete objective function $f_{i}$. However, agent $i$ sequentially observes independent samples of $R_{i}$ and uses these samples to determine an approximate subgradient using the Robbins-Monro approximation or Kiefer-Wolfowitz approximation . These approximate sub-gradients can be considered to be the actual sub-gradient corrupted by stochastic errors.

We next discuss some specific problems that fall within the framework that we consider and can be solved using the proposed methods.

Consider $m$ sensors that sense a time invariant spatial field. Let $r_{i,k}$ be the measurement made by $i^{th}$ sensor in time slot $k.$ Let $s_{i}$ be the location of the $i^{th}$ sensor. Let $h(s;x)$ be a set of candidate models for the spatial field that are selected based on a priori information and parameterized by $x$. Thus, for each $x,$ the candidate $h(s,x)$ is a model for the spatial field and $h(s_{i},x)$ is a model for the measurement $r_{i,k}.$ The problem in regression is to choose the best model among the set of candidate models based on the collected measurements $r_{i,k}$, i.e., to determine the value for $x$ that best describes the spatial field. In least square regression, the parameter value $x^{*}$ corresponding to the best model satisfies the following relation:

When the measurements $r_{i,k}$ are corrupted by i.i.d. noise, then the preceding relation is equivalent to the following

In linear least squares regression, the models $h(s_{i},x)$, $i=1,\ldots,m,$ are linear in $x$, so that each of the functions $f_{i}(x)=\mathsf{E}\!\left[\left(R_{i}-h(s_{i},x)\right)^{2}\right]$ is convex in $x$.

Distributed Resource Allocation

In some networks, the same flow can communicate different types of traffic that has different importance in different time slots. For example, in an intruder detection network, a “detected” message is more important (and is rewarded/weighted more) than a “not detected” message or some other system message. Thus, the reward function is also a function of the contents of the flow: if the type of flow $i$ in time slot $k$ is $r_{i,k},$ where $r_{i,k}$ takes values from the set of all possible types of flow data, then the reward is $U_{i}(x_{i},r_{i,k})$ at time $k$. When the type of traffic on each flow across slots is i.i.d, the fair allocation rate problem can be written as

The statistics of $R_{i}$ may not be known since they may depend upon external factors such as the frequency of intruders in an intruder detection network.

2 Notation and Basics

We view vectors as columns. We write $x^{T}y$ to denote the inner product of two vectors $x$ and $y$. We use $\|\cdot\|$ to denote the standard Euclidean norm. For a vector $x$, we use $x_{i}$ to denote its $i$-th component. For a matrix $A,$ we use $[A]_{i,j}$ to denote its $(i,j)$-th entry, $[A]_{i}$ its $i$-th row and $[A]^{j}$ its $j$-th column. We use $e$ to denote a vector with each entry equal to 1.

We use $f^{*}$ to denote the optimal value of the problem (1), and we use $X^{*}$ to denote its optimal set. Throughout the paper, we assume that the optimal value $f^{*}$ is finite.

In our analysis, we use the subgradient defining property. Specifically, for a convex function $f:\Re^{n}\to\Re$, the vector $\nabla f(x)$ is a subgradient of $f$ at $x$ when the following relation is satisfied:

Cyclic Incremental Subgradient Algorithm

Recall, that the cyclic incremental stochastic subgradient algorithm is given by

where $x_{0}\in X$ is a random initial vector, $\nabla f_{i}(x)$ is a subgradient of $f_{i}$ at $x$, $\epsilon_{i,k+1}$ is a random noise vector and $\alpha_{k+1}>0$ is a step-size.

The main difficulty in the study of the incremental stochastic subgradient algorithm is that the expected direction in which the iterate is adjusted in each sub-iteration is not necessarily a subgradient of the objective function $f$. For this reason, we cannot directly apply the classic stochastic approximation convergence results of to study the convergence of method in (2). The key relation in our analysis is provided in Lemma 1 in Section 3.1. Using this lemma and a standard super-martingale convergence result, we obtain results for diminishing step-size in Theorem 3. Furthermore, by considering a related “stopped” process to which we apply a standard supermartingale convergence result, we obtain the error bound results for a constant step-size in Theorems 4 and 5.

We make the following basic assumptions on the set $X$ and the functions $f_{i}$.

The set $X\subseteq\Re^{n}$ is closed and convex. The function $f_{i}:\Re^{n}\to\Re$ is convex for each $i\in\{1,\ldots,m\}.$

In our analysis, we assume that the first and the second moments of the subgradient noise $\epsilon_{i,k}$ are bounded uniformly over the agents, conditionally on the past realizations. In particular, we define $F_{k}^{i}$ as the $\sigma$-algebra generated by $x_{0}$ and the subgradient errors $\epsilon_{1,1},\ldots,\epsilon_{i,k}$, and assume the following.

There exist deterministic scalar sequences $\{\mu_{k}\}$ and $\{\nu_{k}\}$ such that

Assumption 2 holds for example, when the errors $\epsilon_{i,k}$ are independent across both $i$ and $k,$ and have finite moments. Note that under the assumption that the second moments are bounded, from Jensen’s inequality we readily have

However, for a constant step-size, the terms $\left\|\mathsf{E}\!\left[\epsilon_{i,k}\mid F_{k}^{i-1}\right]\right\|$ and $\mathsf{E}\!\left[\|\epsilon_{i,k}\|^{2}\mid F_{k}^{i-1}\right]$ affect the error bounds on the performance of the incremental method differently, as seen in Section 3.3. For this reason, we prefer to use different upper-bounds for the terms $\left\|\mathsf{E}\!\left[\epsilon_{i,k}\mid F_{k}^{i-1}\right]\right\|$ and $\mathsf{E}\!\left[\|\epsilon_{i,k}\|^{2}\mid F_{k}^{i-1}\right].$ We will also, without any loss of generality, assume that $\mu_{k}<\nu_{k}.$

We also assume that the subgradients $\nabla f_{i}(x)$ are uniformly bounded over the set $X$ for each $i$. This assumption is commonly used in the convergence analysis of subgradient methods with a diminishing or a constant step-size.

For every $i$, the subgradient set of the function $f_{i}$ at $x\in X$ is nonempty and uniformly bounded over the set $X$ by a constant $C_{i}$, i.e.,

Assumption 3 holds for example, when each $f_{i}$ is a polyhedral function or when the set $X$ is compact.

In this section, we provide a lemma establishing a basic relation for the iterates generated by the incremental method (5) and any step-size rule. This relation plays a key role in our subsequent development.

Let Assumptions 1, 2, and 3 hold. Then, the iterates generated by algorithm (5) are such that for any step-size rule and for any $y\in X$,

where $d_{k}(y)=x_{k}-y$ and $d_{i,k+1}(y)=z_{i,k+1}-y$ for all $k$.

Using the iterate update rule in (5) and the non-expansive property of the Euclidean projection, we obtain for any $y\in X$,

Taking conditional expectations with respect to the $\sigma$-field $F_{k+1}^{i-1}$, we further obtain

We now estimate the last two terms in the right hand side of the preceding equation by using Assumption 2 on the error moments. In particular, we have for all $i$ and $k$,

Next, we estimate the last term in Eq. (8) by using Assumption 2 on the error moments in and Assumption 3 on the subgradient norms. We have all $i$ and $k$,

where in the last inequality we use $\mathsf{E}\!\left[\left\|\epsilon_{i,k}\right\|^{2}\mid F_{k}^{i-1}\right]\leq\nu_{k}^{2}$ and $\left\|\mathsf{E}\!\left[\epsilon_{i,k}\mid F_{k}^{i-1}\right]\right\|\leq\nu_{k}$ for all $k$ [cf. Eq. (6)]. Combining the preceding two relations and the inequality in (8), we obtain for all $y\in X$,

We now estimate the second term in the right hand side of the preceding relation. From the subgradient inequality in (4) we have

In (13) we have again used the subgradient inequality (4) to bound $f_{i}(z_{i-1,k+1})-f_{i}(x_{k}),$ while in (14) we have used the subgradient norm bound from Assumption 3. We next consider the term $\left\|z_{i-1,k+1}-x_{k}\right\|$. From (5) we have

By the non-expansive property of the projection, we further have

By combining the preceding relation with Eq. (14), we have

By substituting the preceding estimate in the inequality in (9), we obtain for all $y\in X$,

Taking the expectation conditional on $F_{k}^{m}$, we obtain

where we have used Assumption 2 and Jensen’s inequality to bound $\mathsf{E}\!\left[\|\epsilon_{j,k+1}\|\mid F_{k}^{m}\right]$ by $\nu_{k+1}$ [cf. Eq. (6)]. Summing over $i=1,\ldots,m,$ and noting that $d_{0,k+1}(y)=x_{k}-y$, we see that

we obtain for all $y\in X$, and all $i$ and $k$,

2 Convergence for diminishing step-size

We here study the convergence of the method in (5) for diminishing step-size rule. In our analysis, we use the following result due to Robbins and Siegmund (see Lemma 11, Chapter 2.2, ).

Let $(\Omega,\mathcal{F},\mathcal{P})$ be a probability space and let $\mathcal{F}_{0}\subset\mathcal{F}_{1}\subset\ldots$ be a sequence of sub $\sigma$-fields of $\mathcal{F}.$ Let $u_{k},v_{k}$ and $w_{k},$ $k=0,1,2\ldots,$ be non-negative $\mathcal{F}_{k}$-measurable random variables and let $\{q_{k}\}$ be a deterministic sequence. Assume that $\sum_{k=0}^{\infty}q_{k}<\infty,$ and $\sum_{k=0}w_{k}<\infty$ and

hold with probability 1. Then, with probability 1, the sequence $\{u_{k}\}$ converges to a non-negative random variable and $\sum_{k=0}^{\infty}v_{k}<\infty$.

We next provide a convergence result for diminishing step-sizes.

Let Assumptions 1, 2 and 3 hold. Assume that the step-size sequence $\{\alpha_{k}\}$ is positive and such that $\sum_{k=1}^{\infty}\alpha_{k}=\infty$ and $\sum_{k=1}^{\infty}\alpha_{k}^{2}<\infty$. In addition, assume that the bounds $\mu_{k}$ and $\nu_{k}$ on the moments of the error sequence $\{\epsilon_{i,k}\},$ are such that

Also, assume that the optimal set $X^{*}$ is nonempty. Then, the iterate sequence $\{x_{k}\}$ generated by the method (5) converges to an optimal solution with probability 1.

First note that all the assumptions of Lemma 1 are satisfied. Let $x^{*}$ be an arbitrary point in $X^{*}.$ By letting $y=x^{*}$ in Lemma 1, we obtain for any $x^{*}\in X^{*}$,

We relate $\|d_{i-1,k+1}(x^{*})\|$ to $\|d_{k}(x^{*})\|$ by using the triangle inequality of norms,

Substituting for $\|z_{i-1,k+1}-x_{k}\|$ from (15) we obtain

Taking conditional expectations, we further obtain

where we have used Assumption 2 and Jensen’s inequality to bound $\mathsf{E}\!\left[\|\epsilon_{j,k+1}\|\mid F_{k}^{m}\right]$ by $\nu_{k+1}.$ Using the preceding inequality in (16), we have

By the assumptions on the step-size, and the sequences $\{\mu_{k}\}$ and $\{\nu_{k}\}$, we further have

where in the second relation above, we have used $\mu_{k+1}\leq\nu_{k+1}$ [cf. Eq. (6)], while in the last inequality, we have used $(a+b)^{2}\leq 2(a^{2}+b^{2})$ valid for any scalars $a$ and $b$. Thus, the conditions of Lemma 2 are satisfied with $u_{k}=\|d_{k}(x^{*})\|^{2},$ $\mathcal{F}_{k}=F^{m}_{k},$ $q_{k}=m\alpha_{k+1}\mu_{k+1},$ $v_{k}=2\alpha_{k+1}\left(f(x_{k})-f^{*}\right)$ and

Therefore, with probability 1, the scalar $\|d_{k+1}(x^{*})\|^{2}$ converges to some non-negative random variable for every $x^{*}\in X^{*}$. Also with probability 1, we have

Since $\sum_{k=1}^{\infty}\alpha_{k}=\infty,$ it follows that $\liminf_{k\to\infty}f(x_{k})=f^{*}$ with probability 1. By considering a sample path for which $\liminf_{k\to\infty}f(x_{k})=f^{*}$ and $\|d_{k+1}(x^{*})\|^{2}$ converges for any $x^{*}$, we conclude that the sample sequence must converge to some $x^{*}\in X^{*}$ in view of continuity of $f$. Hence, the sequence $\{x_{k}\}$ converges to some vector in $X^{*}$ with probability 1. ∎

Note that under assumptions of Theorem 3, it can be seen that $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k},X^{*}\right)^{2}\right]$ also converges to $0.$ In particular, since the solution set $X^{*}$ is closed and convex, there exists a point $x_{k}^{*}\in X^{*}$ that is closest to $x_{k}$ for every $k$. Letting $y=x_{k}^{*}$ in relation (17) and using the fact that $\mathsf{dist}\left(x_{k+1},X^{*}\right)\leq d_{k+1}(x_{k}^{*})$ with probability $1$, we obtain for all $k$,

Taking expectations, we obtain for all $k$,

From the deterministic analog of Lemma 2, we can argue that $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k+1},X^{*}\right)^{2}\right]$ converges and $\liminf_{k\to\infty}\mathsf{E}\!\left[f(x_{k})\right]=f^{*}$. Since $\{x_{k}\}$ converges to a point in $X^{*}$ with probability 1, it follows that $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k+1},X^{*}\right)^{2}\right]$ converges to $0.$

3 Error bound for constant step-size

Here, we study the behavior of the iterates $\{x_{k}\}$ generated by the method (5) with a constant step-size rule, i.e., $\alpha_{k}=\alpha$ for all $k$. In this case, we cannot guarantee the convergence of the iterates, however, we can provide bounds on the performance of the algorithm. In the following lemma, we provide an error bound for the expected values $\mathsf{E}\!\left[f(x_{k})\right]$ and a bound for $\inf_{k}f(x_{k})$ that holds with probability 1. The proofs of these results are similar to those used in .

Let Assumptions 1 and 2 hold. Let the sequence $\{x_{k}\}$ be generated by the method (5) with a constant step-size rule, i.e., $\alpha_{k}=\alpha$ for all $k\geq 1.$ Also, assume that the set $X$ is bounded, and

Since $X$ is compact and each $f_{i}$ is convex over $\Re^{n}$, the subgradients of $f_{i}$ are bounded over $X$ for each $i$. Thus, all the assumptions of Lemma 1 are satisfied. Furthermore, the optimal set $X^{*}$ is non-empty. Since $\mu_{k}\leq\mu$ and $\nu_{k}\leq\nu$ for all $k$, and $\|d_{i-1,k+1}(y)\|\leq\max_{x,y\in X}\|x-y\|,$ according to the relation of Lemma 1, we have for $y=x^{*}\in X^{*}$,

By taking the total expectation, we obtain for all $y\in X$ and all $k$,

Now, assume that the relation (18) does not hold. Then there will exist a $\gamma>0$ and an index $k_{\gamma}$ such that for all $k>k_{\gamma}$,

For sufficiently large $k,$ the right hand side of the preceding relation is negative, yielding a contradiction. Thus the relation (18) must hold.

We now prove the relation in (19). Define the set

Let $x^{*}\in X^{*}$ and define the sequence $\hat{x}_{k}$ as follows:

Thus, the process $\{\hat{x}_{k}\}$ is identical to the process $\{x_{k}\},$ until $\{x_{k}\}$ enters the set $L_{N}.$ Define

Let us first consider the case when $\hat{x}_{k}\in L_{N}.$ Since $\hat{x}_{k}=x^{*}$ and $\hat{x}_{k+1}=x^{*}$, we have $\hat{d}_{k}(x^{*})=0$ and $\hat{d}_{k+1}(x^{*})=0,$ yielding

When $\hat{x}_{k}\notin L_{N},$ $\hat{x}_{k}=x_{k}$ and $\hat{x}_{k+1}=x_{k+1}.$ Using relation (21), we conclude that

Observe that when $\hat{x}_{k}\notin L_{N},$

Therefore, by combining the preceding two relations, we obtain for $\hat{x}_{k}\notin L_{N},$

Therefore, from (22) and (23), we can write

Observe that (24) satisfies the conditions of Lemma 2 with $u_{k}=\|\hat{d}_{k}(x^{*})\|^{2},$ $\mathcal{F}_{k}=F_{k}^{m},$ $q_{k}=0,$ $v_{k}=\Delta_{k+1}$ and $w_{k}=0.$ Therefore, it follows that with probability 1,

However, this is possible only if $\Delta_{k}=0$ for all $k$ sufficiently large. Therefore, with probability 1, we have $x_{k}\in L_{N}$ for all sufficiently large $k$. By letting $N\to\infty,$ we obtain (19). ∎

As seen from relation (19) of Theorem 4, the error bound on the “best function” value $\inf_{k}f(x_{k})$ depends on the step-size $\alpha$, and the bounds $\mu$ and $\nu$ for the moments of the subgradient errors $\epsilon_{i,k}$. When the errors $\epsilon_{i,k}$ have zero mean, the results of Theorem 4 hold with $\mu=0$. The resulting error bound is $\frac{\alpha}{2}\left(\sum_{i=1}^{m}C_{i}+m\nu\right)^{2}$, which can be controlled with the step-size $\alpha$. However, this result also holds when the boundedness of $X$ is relaxed by requiring subgradient boundedness instead, as seen in the following theorem. The proof of this theorem is similar to that of Theorem 4, with some extra details to account for the possibility that the optimal set $X^{*}$ may be empty.

All the assumptions of Lemma 1 are satisfied. Since $\mu_{k}=0$ and $\nu_{k}\leq\nu$ for all $k$, according to the relation of Lemma 1, we have for any $y\in X$,

By taking the total expectation, we obtain for all $y\in X$ and all $k$,

Assume now that the relation (25) is not valid. Then there will exist a $\gamma>0$ and an index $k_{\gamma}$ such that for all $k>k_{\gamma}$,

Let $y_{\gamma}\in X$ be such that $f(y_{\gamma})\leq f^{*}+\gamma$. Therefore, for $k\geq k_{\gamma}$, we have

Fix $y=y_{\gamma}$ in (28) and in a manner identical to the proof of Theorem 4 we can obtain a contradiction.

To prove the relation in (26), we use a line of analysis similar to that of the proof of Theorem 4, where we define the set

and consider the sequence $\hat{x}_{k}$ defined as follows:

As in the proof of Theorem 4, we can show that the sequence $\{x_{k}\}$ enters the set $L_{N},$ for any $N.$ We then obtain the result by taking the limit $N\to\infty.$ ∎

In the absence of errors ($\nu=0$), the error bound of Theorem 5 reduces to

which coincides with the error bound for the cyclic incremental subgradient method (without errors) established in , Proposition 2.1.

Markov Randomized Incremental Subgradient Method

While the method of Section 3 is implementable in networks with a ring structure (the agents form a cycle), the method of this section is implementable in networks with an arbitrary connectivity structure. The idea is to implement the incremental algorithm by allowing agents to communicate only with their neighbors. In particular, suppose at time $k$, an agent $j$ updates and generates the estimate $x_{k}$. Then, agent $j$ may pass this estimate to his neighboring agent $i$ with probability $[P(k)]_{i,j}$. If agent $j$ is not a neighbor of $i$, then this probability is . Formally, the update rule for this method is given by

where $x_{0}\in X$ is some random initial vector, $\epsilon_{s(k+1),k+1}$ is a random noise vector and $\alpha_{k+1}>0$ is the step-size. The sequence of indices of agents updating in time evolves according to a a time non-homogeneous Markov chain with states $1,\dots,m.$ We let $P(k)$ denote the transition matrix of this chain at time $k,$ i.e.,

In the absence of subgradient errors ($\epsilon_{s(k),k}=0$), when the probabilities $[P(k)]_{i,j}$ are all equal, i.e., $[P(k)]_{i,j}=\frac{1}{m}$ for all $i,j$ and all $k$, the method reduces to the incremental method with randomization proposed in , which is applicable only to the agent networks that are fully connected.

We note here that the time non-homogeneous Markov chain models networks where the set of neighbors of an agent may change in time (as the network may be mobile or for other reasons). We will also assume that the agents decide the probabilities with which they communicate with their neighbors, i.e., at time $k$, the agent $j$ chooses the probabilities $[P(k)]_{i,j}\geq 0$ for his neighbors $i.$

The main difficulty in the analysis of the method in (29) comes from the dependence between the random agent index $s(k+1)$ and the iterate $x_{k}$. Assuming that the Markov chain is ergodic with the uniform steady-state distribution, in the absence of the errors $\epsilon_{i,k}$ (i.e., $\epsilon_{i,k}=0$), it is intuitively possible that the method uses directions that approximate the subgradient $\frac{1}{m}\sum_{i=1}^{m}\nabla f_{i}(x_{k})$ in the steady state. This is the basic underlying idea that we exploit in our analysis.

To ensure the desired limiting behavior of the Markov chain probabilities, we use the following two assumptions on the matrices $[P(k)]$.

Let $V=\{1,\ldots,m\}$. Let $E(k)$ be the set of edges $(j,i)$ induced by the positive entries of the probability matrix $P(k)$, i.e.,

Generally speaking, Assumption 4 ensures that each agent has a “chance” to update the estimate $x_{k}$ once within a finite time interval. It would guarantee that each agent updates the estimate $x_{k}$ with the same frequency in a long run. This is ensured by the following assumption.

The diagonal entries of $P(k)$ are all positive for each $k$.

All positive entries of $[P(k)]$ are uniformly bounded away from zero, i.e., there exists a scalar $\eta>0$ such that for all $i,j\in\{1,\ldots,m\}$ and all $k$,

The matrix $P(k)$ is doubly stochastic for each $k$, i.e., the sum of the entries in every row and every column is equal to $1.$

Assumptions 5(a) and (b) ensure that the information from each and every agent is persistent in time. Assumption 5(c), ensures that the limiting Markov chain probability distribution (if one exists) is uniform. Assumptions 4 and 5 together guarantee the existence of the uniform limiting distribution, as shown in . We state this result in the next section.

Note that the cyclic incremental algorithm (2) does not satisfy Assumption 5. The transition probability matrix corresponding to the cyclic incremental method is a permutation matrix with the $(i,i)$-th entry being zero when agent $i$ updates at time $k$. Thus, Assumption 5(c) is violated.

We now provide some examples of transition matrices $[P(k)]$ satisfying Assumption 5. The second and third examples are variations of the Metropolis-Hasting weights , defined in terms of the agent neighbors. We let $N_{i}(k)\subset\{1,\ldots,m\}$ be the set of neighbors of an agent $i$ at time $k$, and let $|N_{i}(k)|$ be the cardinality of this set. Consider the following rules:

Equal probability scheme. The probabilities that agent $i$ uses at time $k$ are

Min-equal neighbor scheme. The probabilities that agent $i$ uses at time $k$ are

Weighted Metropolis-Hastings scheme. The probabilities that agent $i$ uses at time $k$ are given by

where the scalar $\eta_{i}>0$ is known only to agent $i$.

In the first example, the parameter $\eta$ can be defined as $\eta=\frac{1}{m}.$ In the second example, $\eta$ can be defined as

while in the third example, it can be defined as

Furthermore, note that in the first example, each agent knows the size of the network and no additional coordination with the other agents is needed. In the other two examples, an agent must be aware of the number of the neighbors each of his neighbors has at any time.

Assume the matrices $P(k)$ satisfy Assumptions 4 and 5. Then:

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

The convergence is geometric and the rate of convergence is given by

We use the estimate of Lemma 6 to establish a key relation in Lemma 7, which is repeatedly invoked in our subsequent analysis. The idea behind Lemma 7 is the observation that when there are no errors ($\epsilon_{s(k),k}=0$) and the Markov chain has a uniform steady state distribution, the directions $\nabla f_{s(k+1)}(x_{k})$ used in (29) are approximate subgradients of the function $\frac{1}{m}\sum_{i=1}^{m}\nabla f_{i}(x)$ at points $x_{n(k)}$ far away from $x_{k}$ in the past [i.e., $k>>n(k)$]. However, even though $x_{n}(k)$ are far away from $x_{k}$ in time, their Euclidean distance $\|x_{k}-x_{n(k)}\|$ can be small when the step-size is selected appropriately. Overall, this means that each iterate of method in (29) can be viewed as an approximation of the iteration

with correlated errors $\xi_{k}$ depending on current and past iterates.

In the forthcoming lemma and thereafter, we let $G_{k}$ denote the entire history of the method up to time $k$, i.e., the $\sigma$-field generated by the initial vector $x_{0}$ and $\left\{s(n),\epsilon_{s(n),n};0\leq n\leq k\right\}.$

Let Assumptions 1–5 hold. Then, the iterates generated by algorithm (29) are such that for any step-size rule, for any $y\in X,$ and any non-negative integer sequence $\{n(k)\},$ $n(k)\leq k,$ we have

where $d_{k}(y)=x_{k}-y$ and $C=\max_{1\leq i\leq m}C_{i}.$

Using the iterate update rule in (29) and the non-expansive property of the Euclidean projection, we obtain for any $y\in X$ and $k\geq 0$,

Using the subgradient inequality in (4) to bound $d_{k}(y)^{T}\nabla f_{s(k+1)}\left(x_{k}\right),$ we get

Taking conditional expectations with respect to the $\sigma$-field $G_{n(k)}$, we obtain

We next use the subgradient inequality in (4) to estimate the second term in the preceding relation.

In the last step we have used the subgradient boundedness from Assumption 3 to bound the subgradient norms $\left\|\nabla f_{s(k+1)}\left(x_{n(k)}\right)\right\|$ by $C=\max_{1\leq i\leq m}C_{i}.$ We estimate $\mathsf{E}\!\left[\left\|x_{n(k)}-x_{k}\right\|\mid G_{n(k)}\right]$ from the iterate update rule (29) and the non-expansive property of the Euclidean projection as follows:

where in the last step we have used the boundedness of subgradients and of the second moments of $\epsilon_{i,k}$ [cf. Eq. (6)]. From the preceding relation and Eq. (31), we obtain

By substituting the preceding estimate in (30), we further obtain

We estimate the last term in (32) by using the subgradient boundedness of Assumption 3 and the boundedness of the second moments of $\epsilon_{i,k}$ [cf. Eq. (6)], as follows:

Substituting the preceding estimate in Eq. (32), we have

We next estimate the term $\mathsf{E}\!\left[d_{k}(y)^{T}\epsilon_{s(k+1),k+1}\mid G_{n(k)}\right].$ Since $G_{n(k)}\subset G_{k}$ and $d_{k}(y)$ is $G_{k}$-measurable

where the first equality follows from the law of iterated conditioning. Using the preceding estimate in (33), we obtain

Finally, we consider the term $\mathsf{E}\!\left[f_{s(k+1)}\left(x_{n(k)}\right)-f_{s(k+1)}\left(y\right)\mid G_{n(k)}\right]$, and we use the fact that the probability transition matrix for the Markov chain $\{s(k)\}$ from time $n(k)$ to time $k$ is $\Phi(k+1,n(k))=P(n(k))\cdots P(k)$. We have

where at the last step we have used Lemma 6. Using the subgradient inequality (4), we further have

The result now follows by combining the relations in Eqs. (34), (35) and (36). ∎

2 Convergence for diminishing step-size

In this section, we establish the convergence of the Markov randomized method in (29) for a diminishing step-size. Recall that in Theorem 3 for the cyclic incremental method, we showed an almost sure convergence result for a diminishing step-size $\alpha_{k}$ subject to some conditions that coordinate the choice of the step-size, and the bounds $\mu_{k}$ and $\nu_{k}$ on the moments of the errors $\epsilon_{i,k}$. To obtain an analogous result for the Markov randomized method, we use boundedness of the set $X$ and more restricted step-size. In particular, we consider a step-size of the form $\alpha_{k}=\frac{a}{k^{p}}$ for a range of values of $p,$ as seen in the following.

Let Assumptions 1, 2, 4 and 5 hold. Assume that the step-size is $\alpha_{k}=\frac{a}{k^{p}},$ where $a$ and $p$ are positive scalars with $\frac{2}{3}<p\leq 1.$ In addition, assume that the bounds $\mu_{k}$ and $\nu_{k}$ on the error moments satisfy

Furthermore, let the set $X$ be bounded. Then, with probability 1, we have

Since the set $X$ is compact and $f_{i}$ is convex over $\Re^{n}$, it follows that the subgradients of $f_{i}$ are bounded over $X$ for each $i$. Thus, Assumption 3 is satisfied, and we can use Lemma 7.

Since $X$ is compact and $f$ is convex over $\Re^{n}$ (therefore, also continuous), the optimal set $X^{*}$ is nonempty, closed and convex. Let $x^{*}_{k}$ be the projection of $x_{k}$ on the set $X^{*}$. In Lemma 7, we let $y=x_{k}^{*}$ and let $n(k)=k+1-\left\lceil k^{\gamma}\right\rceil,$ where $\gamma>0$ (to be specified more precisely later on). Note that $n(k)\leq k$ for all $k\geq 1$. Using this and the relation $\mathsf{dist}\left(x_{k+1},X^{*}\right)\leq\|x_{k+1}-x_{k}^{*}\|$, from Lemma 7, we obtain for all $k>1$The equivalent expression for the case when $k=1$ is obtain by setting the fourth term to 0.,

Taking expectations and using $\sup_{k\geq 1}\nu_{k}=\nu$, we obtain for all $k>1$,

We next show that $\sum_{k=2}^{\infty}\tau_{k+1}<\infty$. Since $\alpha_{k}=\frac{a}{k^{p}}$, we have $\alpha_{k+1}<\alpha_{k}$ for all $k\geq 1.$ Furthermore, since $\beta<1$, we have $\beta^{\left\lceil k^{\gamma}\right\rceil}<\beta^{k^{\gamma}}.$ Therefore, $\alpha_{k+1}\beta^{\left\lceil k^{\gamma}\right\rceil}<\frac{a\beta^{k^{\gamma}}}{k^{p}}.$ By choosing $\gamma>0$ such that $\gamma\geq 1-p$, we see that $\frac{1}{k^{p}}\leq\frac{1}{k^{1-\gamma}}$ for all $k>1.$ Hence, for all $k>1$,

Since the set $X$ is bounded, it follows that

Next, since $\left\lceil k^{\gamma}\right\rceil-2<k^{\gamma}$ for all $k\geq 2,$ and since $\alpha_{k+1}<\alpha_{k}$, $\alpha_{k}=\frac{1}{k^{p}}$ and $n(k)=k+1-\left\lceil k^{\gamma}\right\rceil$, it follows that for all $k\geq 2,$

By choosing $\gamma>0$ such that it also satisfies $\gamma<2p-1$ (in addition to $\gamma\geq 1-p$), we have $\gamma<1$ (in view of $p\leq 1$). Therefore, for all $k\geq 2$,

By combining the preceding two relations, we have

where the finiteness of the last sum follows from $2p-\gamma>1$.

Finally, as a consequence of our assumptions, we also have

Thus, from Eqs. (37) and (38), and the preceding two relations, we see that $\sum_{k=2}^{\infty}\tau_{k+1}<\infty.$

From the deterministic analog of Lemma 2 we conclude that $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k},X^{*}\right)^{2}\right]$ converges to a non-negative scalar and

Since $p<1,$ we have $\sum_{k=2}^{\infty}\alpha_{k+1}=\infty$. Further, since $f\left(x_{n(k)}\right)\geq f^{*},$ it follows that

The function $f$ is convex over $\Re^{n}$ and, hence, continuous. Since the set $X$ is bounded, the function $f(x)$ is also bounded on $X.$ Therefore, from Fatou’s lemma it follows that

implying that $\liminf_{k\to\infty}f\left(x_{k}\right)=f^{*}$ with probability 1. Moreover, from this relation, by the continuity of $f$ and boundedness of $X$, it follows that $\liminf_{k\to\infty}\mathsf{dist}\left(x_{k},X^{*}\right)=0$ with probability 1. ∎

As seen in the proof of Theorem 8, $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k},X^{*}\right)^{2}\right]$ converges to a nonnegative scalar, but we have no guarantee that its limit is zero. However, this can be shown, for example, for a function with a sharp set of minima, i.e., $f$ satisfying

for some positive scalars $\zeta$ and $\xi.$ Under the assumptions of Theorem 8, we have that $\liminf_{k\to\infty}\mathsf{E}\!\left[f\left(x_{k}\right)\right]=f^{*}$ [cf. Eq. (39)] and therefore,

Hence, $\liminf_{k\to\infty}\mathsf{E}\!\left[\mathsf{dist}\left(x_{k},X^{*}\right)^{\xi}\right]=0,$ and since $\mathsf{E}\!\left[\mathsf{dist}\left(x_{k},X^{*}\right)^{2}\right]$ converges, it has to converge to $0.$

3 Error bounds for constant step-size

We now establish error bounds when the Markov randomized incremental method is used with a constant step-size.

Let Assumptions 1, 2, 4 and 5 hold. Let the sequence $\{x_{k}\}$ be generated by the method (29) with a constant step-size rule, i.e., $\alpha_{k}=\alpha$ for all $k$. Also, assume that the set $X$ is bounded, and

where $\beta=\left(1-\frac{\eta}{4m^{2}}\right)^{\frac{1}{Q}}$ and $C=\max_{1\leq i\leq m}C_{i}.$ Furthermore, with probability 1, the same estimate holds for $\inf_{k}f(x_{k})$.

Since $X$ is compact and each $f_{i}$ is convex over $\Re^{n}$, the subgradients of $f_{i}$ are bounded over $X$ for each $i$. Thus, all the assumptions of Lemma 7 are satisfied. Let $T$ be a nonnegative integer and let $n(k)=k-T$. Since $\mu_{k}\leq\mu$ and $\nu_{k}\leq\nu$ for all $k$, and $\|d_{k}(y)\|\leq\max_{x,y\in X}\|x-y\|,$ according to Lemma 7, we have for $y=x^{*}\in X^{*}$ and $k\geq T,$

By taking the total expectation, we obtain for all $x^{*}\in X^{*}$ and all $k\geq T$,

Now assume that the relation (40) does not hold. Then, there will exist a $\gamma>0$ and an index $k_{\gamma}\geq T$ such that for all $k\geq k_{\gamma}$,

Therefore, for $k\geq k_{\gamma}+T$, we have

For sufficiently large $k,$ the right hand side of the preceding relation is negative, yielding a contradiction. Thus, the relation (40) must hold for all $T\geq 0.$

Let $x^{*}\in X^{*}$ and define the sequence $\hat{x}_{k}$ as follows:

Thus, the process $\{\hat{x}_{k}\}$ is identical to the process $\{x_{k}\}$ until $\{x_{k}\}$ enters the set $L_{N}.$ Define

Let $k\geq T.$ Consider the case when $\hat{x}_{k}\in L_{N}.$ Then, $\hat{x}_{k}=x^{*}$ and $\hat{x}_{k+1}=x^{*}$, so that $\hat{d}_{k}(x^{*})=0$ and $\hat{d}_{k+1}(x^{*})=0,$ yielding

Consider now the case when $\hat{x}_{k}\notin L_{N}.$ Then, $\hat{x}_{l}=x_{l}$ and $x_{l}\notin L_{N}$ for all $l\leq k+1$. Therefore, by the definition of the set $L_{N}$, we have

By using relations (41) and (44), we conclude that for $\hat{x}_{k}\notin L_{N},$

Therefore, from (43) and (45), we can write

Observe that (46) satisfies the conditions of Lemma 2 with $u_{k}=\mathsf{E}\!\left[\|\hat{d}_{k}(x^{*})\|^{2}\mid G_{n(k)}\right],$ $\mathcal{F}_{k}=G_{n(k)},$ $q_{k}=0,$ $w_{k}=2\Delta_{k+1}$ and $v_{k}=0.$ Thus, it follows that with probability 1,

However, this is possible only if $\Delta_{k}=0$ for all $k$ sufficiently large. Therefore, with probability 1, we have $x_{k}\in L_{N}$ for all sufficiently large $k$. By letting $N\to\infty,$ we obtain (42). ∎

Under Assumptions of Theorem 9, the function $f$ is bounded over the set $X$, and by Fatou’s lemma, we have

It follows that the estimate of Theorem 9 also holds for $\mathsf{E}\!\left[\liminf_{k\to\infty}f(x_{k})\right].$

In the absence of errors ($\mu_{k}=0$ and $\nu_{k}=0$), the error bound in Theorem 9 reduces to

With respect to the parameter $\beta$, the error bound is obviously smallest when $\beta=0$. This corresponds to uniform transition matrices $P(k)$, i.e., $P(k)=\frac{1}{m}ee^{T}$ for all $k$ (see Lemma 6). As mentioned, the Markov randomized method with uniform transition probability matrices $P(k)$ reduces to the incremental method with randomization in . In this case, choosing $T=0$ in (47) is optimal and the resulting bound is $f^{*}+\frac{\alpha}{2}C^{2}$, with $C=\max_{1\leq i\leq m}C_{i}$. We note that this bound is better by a factor of $m$ than the corresponding bound for the incremental method with randomization given in Proposition 3.1 in.

When transition matrices are non-uniform ($\beta>0$), and good estimates of the bounds $C_{i}$ on subgradient norms and the diameter of the set $X$ are available, one may optimize the error bound in (47) with respect to integer $T$ for $T\geq 0$. In particular, one may optimize the term $\alpha TC^{2}+b\left(\sum_{i=1}^{m}C_{i}\right)\beta^{T+1}\max_{x,y\in X}\|x-y\|$ over integers $T\geq 0$. It can be seen that the optimal integer $T^{*}$ is given by

where $C_{0}=b\,\left(\sum_{i=1}^{m}C_{i}\right)\max_{x,y\in X}\|x-y\|$.

A similar expression for optimal $T^{*}$ in the presence of subgradient errors can be obtained, but it is rather cumbersome. Furthermore such an expression (as well as the preceding one) may not be of practical importance when the bounds $C_{i}$, the diameter of the set $X$, and the bounds $\mu$ and $\nu$ on the error moments are “roughly” known. In this case, a simpler bound can be obtained by just comparing the values $\alpha$ and $\beta$, as given in the following.

Let the conditions of Theorem 9 hold. Then,

Furthermore, with probability 1, the same estimate holds for $\inf_{k}f(x_{k})$.

When $\alpha>\beta$ choose $T=0.$ In this case, from (Theorem 9) we get

When $\alpha<\beta$ we can choose $T=\left\lceil\frac{\ln(\alpha)}{\ln(\beta)}\right\rceil-1.$ Then, from (Theorem 9),

It can be seen that the error bounds in (48) and Corollary 10 converge to zero as $\alpha\to 0$. This is not surprising in view of the convergence of the method with a diminishing step-size.

As discussed earlier, the error bound in is obtained assuming that there are no errors in subgradient evaluations and that the sequence of computing agents form a homogeneous Markov chain. Here, while we relax these assumptions, we make the additional assumption that the set $X$ is bounded.

A direct comparison between the bound in Corollary (10) and the results in is not possible. However, some qualitative comparisons on the nature of the bounds can be made. The bound in is obtained for each individual agent’s sequence of iterates (by sampling the iterates). This is a stronger result than our results in (48) and Corollary 10, which provide guarantees only on the entire iterate sequence (and not on the sequence of iterates at an individual agent). However, the bound in depends on the entire network topology, through the probability transition matrix $P$ of the Markov chain. Thus, the bound can be evaluated only when the complete network topology is available. In contrast, our bounds given in (48) and Corollary 10 can be evaluated without knowing the network topology. We require that the topology satisfies a connectivity assumption, as specified by Assumption 4, but we do not assume the knowledge of the exact network topology.

Discussion

Incremental algorithms form the middle ground between selfish agent behavior and complete network cooperation. Each agent can be viewed to be selfish, as it adjusts the iterate only using its own cost function. At the same time, the agents also cooperate by passing the iterate to a neighbor so that he may factor in his opinion by adjusting the iterate using his cost function. Through Theorems 3 and 8, it was observed that a system level global optimum could still be obtained through some amount of cooperation. This can be construed as a statement of Adam Smith’s invisible hand hypothesis in a more semi-cooperative market setting.

The results we have obtained are asymptotic in nature. The key step in dealing with both the incremental algorithms was to obtain the basic iterate equation (Lemmas 1 and 7). This was then combined with standard stochastic analysis techniques to obtain asymptotic results. While we have restricted ourselves to establishing only convergence results, it is possible to combine the techniques in with the basic iterate relation to obtain bounds on the expected rate of convergence of the algorithms. Finally, we have only listed a few possible applications for the results in this paper. The problem of aligning and coordinating mobile agents can also be cast in the optimization framework studied in this paper and the results in this paper, especially the results on Markov stochastic sub-gradient algorithm, can be used to design suitable alignment algorithms.

References